Quick Sort (퀵 소트)

Quick Sort는 전형적인 분할 정복(divide and conquer) 알고리즘의 하나입니다. 이름만큼 평균적으로 매우 빠른 수행 속도를 자랑하며 시간복잡도 O(n log n)을 가지고, 추가 메모리 공간을 필요로 하지 않기 때문에 O(log n)만큼의 메모리를 필요로 합니다.

Merge Sort와 달리 Quick Sort는 비균등 분할을 합니다.

 

1. 리스트 안에 있는 한 요소를 선택하는데, 이때 이 원소를 pivot이라 합니다.
2. 입력 배열을 pivot을 기준으로 비균등하게 2개의 부분 배열로 분할합니다. 이 때, pivot의 왼쪽은 pivot보다 작은 요소들로, pivot의 오른쪽은 pivot보다 큰 요소로 이루어지게 됩니다. (divide)
3. 이렇게 분할한 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용합니다. (conquer)
4. 정렬된 부분 배열들을 하나의 배열에 병합합니다. (combine)

 

순환 호출이 한 번 진행될 때마다 최소한 하나의 원소(pivot)는 최종적으로 위치가 정해지므로, 이 알고리즘은 언젠가 반드시 끝난다는 것을 보장할 수 있습니다.

 

코드 동작 방식은 다음과 같습니다.

1. pivot보다 큰 low가 나올 때까지 low++
2. pivot보다 작은 high가 나올 때까지 high--
3. low < high 라면 arr[low]와 arr[high]를 swap하고 low++, high--
4. low >= high 라면 arr[pivot]과 arr[high]를 swap 하고 왼쪽 오른쪽 부분 배열을 다시 분할합니다. (1번으로)

 

아래는 swift로 작성한 Quick Sort 코드입니다.

 

var input: [Int] = [~] // 정렬할 배열

divide(0, input.count - 1)



func divide(_ start: Int,_ end: Int) {
    if start >= end { return } // 원소가 1개일 경우
    
    let pivot = start
    var low = start+1
    var high = end
    while low < high {
        while low <= end && input[low] <= input[pivot] { low += 1}
        while high > start && input[high] >= input[pivot] { high -= 1 }
        
        if low < high { input.swapAt(low, high) }
        else { input.swapAt(pivot, high) }
    }
    
    divide(start, high-1)
    divide(high+1, end)
}

 

 

 

 

 

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog