퀵 정렬

https://unsplash.com/photos/G9eHjFC_230

퀵 정렬에 대해 알아보자.

 

 

 

 

---

얻어갈 지식

• 퀵 정렬 이해

 

 

 

 

 

퀵 정렬

 

병합 정렬과 마찬가지로 분할-정복 알고리즘이다. 대강의 순서는 아래와 같다.

 

1. 값의 기준점이 될 기준 데이터(pivot)를 정한다.
2. 기준 데이터(pivot)를 기준으로 작은 수는 왼쪽 큰 수는 오른쪽에 오도록 재배치한다.
3. 그렇게 나뉜 두 개의 배열 속에서 또 기준점을 잡고 2번을 반복한다. 해당 과정을 더 이상 분할할 수 없을 때까지 반복한다.

 

 

 

조금 더 자세히 설명하면 피벗 값을 x, 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때. pl은 인덱스 0부터 하나 씩 올라오며 x보다 큰 값을 찾고 반대로 pr은 오른쪽 끝 인덱스부터 x보다 작은 값을 찾는다. pl의 값이 pr보다 크지 않으면 서로의 값을 스왑하고 만약, pl의 값이 pr보타 크면(교차가 일어나면) 인덱스 0부터 pr까지는 피벗 값 이하의 값들로만 이루어져 있을 것이고 인덱스 pl부터 마지막 인덱스까지는 피벗 값 이상의 값들로만 이루어져 있을 것이니 스왑하지 않고 분할을 한 뒤 그것을 다시 정렬한다.

 

 

코드로 작성

def quick_sort(arr, start, end):
    pl = start
    pr = end
    pivot = arr[(start + end) // 2]

    while pl <= pr:
        while arr[pl] < pivot:
            pl += 1
        while arr[pr] > pivot:
            pr -= 1

        if pl <= pr:
            arr[pl], arr[pr] = arr[pr], arr[pl]
            pl += 1
            pr -= 1

    if start < pr:
        quick_sort(arr, start, pr)
    if end > pl:
        quick_sort(arr, pl, end)

 

 

 

시간 복잡도와 보조 공간

• 시간 복잡도는 O(N logN)이고 최악의 경우(피벗 값을 계속 최대 혹은 최소로 잡는 경우) O(N^2)이다.
  • 대부분의 병합 정렬은 어레이를 생성하고, 복사하는 등 내부 루프에서 더 많은 작업을 수행한다. 그와 대조적으로 퀵 정렬은 요소만 스왑하면 되므로 병합 정렬과 시간 복잡도는 같지만 보통의 경우 퀵 정렬이 더 빠르다.
    
    
• in-place 알고리즘으로 어레이 공간을 제외한 추가 공간은 거의 필요치 않다.

 

 

 

 

 

---

https://kururu.tistory.com/45

6일차 정리(퀵 정렬, 병합 정렬)

https://www.geeksforgeeks.org/quick-sort/

QuickSort - GeeksforGeeks

https://www.reddit.com/r/learnprogramming/comments/k793zg/why_my_results_show_quick_sort_faster_than_merge/

Why my results show Quick Sort faster than Merge Sort?