퀵 정렬 [Quidck Sort]이란

알고리즘 스터디를 진행하면서 문제는 어떻게 풀어도 설명할수가 없어서 이론도 함께 하나씩 정리해 가려고 작성하는글

---

퀵정렬 알고리즘의 개념

• 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다.
• 합병 정렬과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
• 진행 과정
  1. 리스트 안에 있는 한 요소(피벗 pivot)를 선택한다.
  2. 피벗을 중심으로 피벗보다 작은 요소는 모두 피벗의 왼쪽으로, 큰 요소는 오른쪽으로 옮겨진다.
  3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정리한다.
  4. 부분 리스트들이 더 이상 분할이 불가능 할 때까지 반복한다.

퀵 정렬 Swift 예제 코드

func divide(_ list:[Element]) -> [Element] {
    if list.count < 2 { return list }
    var newList:[Element] = list
    let pivotIndex:Int = newList.count/2-1
    var leftIndex:Int = 0
    var rightIndex:Int = newList.count-1
    var isLeft:Bool = true

피봇의 왼쪽 오른쪽 인덱스 값을 정해주고, 현재 움직여야할 포인터가 왼쪽인이 오른쪽인지 알려줄 변수를 정한다.

만약 원소가 1개만 남았다면 원소들을 그대로 반환한다.

while leftIndex < rightIndex {
    if isLeft {
        if newList[leftIndex] < newList[pivotIndex] {
            leftIndex += 1
        }else {
            newList.swapAt(pivotIndex, leftIndex)
        }
    }else {
        if newList[rightIndex] > newList[pivotIndex] {
            rightIndex -= 1
        }else {
            newList.swapAt(pivotIndex, rightIndex)
        }
    }
    isLeft.toggle()
}

왼쪽 포인터와 오른쪽 포인터가 겹칠때까지 포인터를 움직여준다.

움직여야할 포인터가 왼쪽이라면, 피벗의 값과 비교해서 더 작다면 포인터를 +1 해주고, 더 크다면 피벗 값과 왼쪽 값을 바꿔준다.

오른쪽이라면, 피벗의 값과 비교해서 더 크다면 포인터를 +1 해주고, 더 작다면 피벗 값과 오른쪽 값을 바꿔준다.

그리고 마지막에 움직여야할 포인터를 toggle로 바꿔준다.

let left:[Element] = Array(newList[0...leftIndex])
let right:[Element] = Array(newList[leftIndex+1..<newList.count])
return merge(divide(left),divide(right))

func merge(_ left:[Element],_ right:[Element]) -> [Element] {
    return left + right
}

겹쳐진 포인터를 기준으로 나눈 후 재귀함수로 반복하고, 

원소가 하나 남을 때까지 모두 분할했다면 왼쪽과 오른쪽을 합쳐준다.

extension Array where Element == Int{
    
    mutating func sortByQuick() -> [Element] {
        return divide(self)
    }
    
    func divide(_ list:[Element]) -> [Element] {
        if list.count < 2 { return list }
        var newList:[Element] = list
        let pivotIndex:Int = newList.count/2-1
        var leftIndex:Int = 0
        var rightIndex:Int = newList.count-1
        var isLeft:Bool = true
        
        while leftIndex < rightIndex {
            if isLeft {
                if newList[leftIndex] < newList[pivotIndex] {
                    leftIndex += 1
                }else {
                    newList.swapAt(pivotIndex, leftIndex)
                }
            }else {
                if newList[rightIndex] > newList[pivotIndex] {
                    rightIndex -= 1
                }else {
                    newList.swapAt(pivotIndex, rightIndex)
                }
            }
            isLeft.toggle()
        }
     
        let left:[Element] = Array(newList[0...leftIndex])
        let right:[Element] = Array(newList[leftIndex+1..<newList.count])
        return merge(divide(left),divide(right))
    }
    
    func merge(_ left:[Element],_ right:[Element]) -> [Element] {
        return left + right
    }
}

퀵 정렬 알고리즘의 특징

- 장점

• 속도가 빠르다
• 추가 메모리 공간을 필요로 하지 않는다.

- 단점

• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 오래 걸린다.

퀵정렬의 불균형 분할을 방지하기 위해서 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.

퀵 정렬의 시간복잡도

최선의 경우	최악의 경우
순환 호출의 깊이
레코드의 개수 n이 2의 거듭제곱이라고 가정, (n=2^k)했을 때 n2^3의 경우 2^3 → 2^2 → 2^1 → 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. n=2^k의 경우, k(k=log₂n)임을 알 수 있다.	레코드의 개수 n이 2의 거듭제곱 이라고 가정(n=2^k)했을 때, 순환 호출의 깊이는 n임을 알 수 있다.
k=log₂n	n
각 순환 호출 단계의 비교 연산
전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다. ▶ 평균 n번	전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다. ▶ 평균 n번
순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = nlog₂n	순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2
이동 횟수
비교 횟수보다 적으므로 무시할 수 있다.	비교 횟수보다 적으므로 무시할 수 있다.
T(n) = O(nlog₂n)	T(n) = O(n^2)

평균

평균 T(n) = O(nlog₂n)
시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
퀵 정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문이다.

정렬 알고리즘 시간복잡도 비교

단순하지만 비효율적인 방법: 삽입 정렬, 선택 정렬, 버블 정렬

복잡하지만 효율적인 방법: 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬