[APS] 13. 퀵 정렬(Quick Sort)

1. 퀵 소트?

---

• 퀵소트는 주어진 배열을 분할하고 - 각각은 정렬한다.

• 분할한다는 점에서 merge sort와 닮아 보이지만, 다른 점은 ‘병합’ 과정이 필요하지 않다는 것이다!!

• why? ⇒ merge sort는 각각을 분할하고 끝! 이지만, quick sort는 pivot을 중심으로 작은 것은 왼편, 큰것은 오른편에 두는 과정을 거치기 때문이다.

2. pivot 고르기

---

• 결국 quick sort의 핵심은 pivot 고르기! 라고 할 수 있겠다.

• 시간복잡도는 $O(nlogn)$ 이지만, 최악의 경우 $O(n^2)$ 가 될 수 있다.

• 예를 들어 이미 정렬이 되어있는 리스트에, 리스트의 첫 원소를 pivot으로 설정하면?? → 최악의 경우가 발생하여 문제 풀이시에 시간초과를 경험할 수 있다!! (경험담)

3. python 으로 구현하기

---

# quick sort 연습
def quicksort(array, start, end):
    if start >= end:
        return

    pivot = start
    left = start + 1
    right = end

    while left <= right : # 찾을 데이터가 남은 상태

        # 왼쪽에는 피벗보다 작은 데이터만 남아야 한다 -> 피벗보다 크면 스탑
        while left <= end and array[left] <= array[pivot] :
            left += 1

        # 오른쪽에는 피벗보다 큰 데이터만 남아야 한다 -> 피벗보다 작으면 스탑
        while right > start and array[right] >= array[pivot]:
            right -= 1

        # 엇갈렸다면 => right, pivot을 교체한다
        if left > right :
            array[right], array[pivot] = array[pivot], array[right]

        # 엇갈린게 아니라면 => left, right을 교체한다
        else:
            array[left], array[right] = array[right], array[left]

    # 분할 이후 오른쪽을 기준으로 다시 정렬 수행한다.
    quicksort(array, start, right-1)
    quicksort(array, right+1, end)

a = [ 3, 4, 7, 1, 2, 10, 5, 6, 9 ]
quicksort(a, 0, len(a)-1)
print(a) #[1, 2, 3, 4, 5, 6, 7, 9, 10]

Uploaded by N2T