정렬 - 6) 퀵 정렬 (quick sort)

 

📍 퀵 정렬: 분할정복방법론

• N 개의 값이 있고, 특정 값(pivot) 이상/미만으로 분류
• pivot을 중심으로 왼쪽에는 더 작은 숫자들, 오른쪽에는 더 큰 숫자들이 오도록 만들어준다.
• 시간복잡도: 평균적으로 O(NlogN) / 최악의 경우 O(N^2)
  • 병합 정렬은 정확히 logN회 분할이 되지만, 퀵 정렬은 평균적으로 logN회 분할 수행
  • 퀵 정렬의 성능은 pivot을 무엇으로 잡느냐에 따라 결정됨
  • pivot은 맨 왼쪽, 맨 오른쪽, 가운데 값 중 중앙값을 선택

---

 

---

 

💬 python 코드 

• n 개의 원소가 주어졌을 때, 퀵 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬

n = int(input())
arr = list(map(int, input().split()))
# arr = [17, 21, 15, 29, 81, 19, 10, 35, 20]

def partition(low, high):
    pivot = arr[high]
    i = low-1 # 파란색 화살표 (pivot보다 같거나 큰)

    for j in range(low, high): # 빨간색 화살표 (pivot보다 작은)
        if arr[j] < pivot: 
            i += 1
            arr[i], arr[j] = arr[j], arr[i] 
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

def quick_sort(low, high):
    if low < high:
        pos = partition(low, high)
        
        quick_sort(low, pos-1) # pivot 기준으로 왼쪽 정렬
        quick_sort(pos+1, high) # pivot 기준으로 오른쪽 정렬

quick_sort(0, len(arr)-1)
print(*arr)