퀵 정렬과 퀵 선택

 

퀵 정렬 

개념

정해진 pivot을 기준으로 pivot보다 작은 것은 왼쪽 piviot보다 큰 거는 오른쪽으로 배치한다.

 

퀵 정렬은 크게 2가지 과정으로 이루워진다.

 

1. partition을 통해 pivot을 기준으로 정렬한다. 
2. 재귀적 반복을 통해 잘게 분할한다. 여기서 분할하는 기준은 pivot의 정렬된 이후 위치이다.

전체 적인 과정은 아래에서 살펴보자.

과정

1.  pviot을 고르 때 가장 오른쪽에 있는 값을 고른다.
2. 우리는 두가지 포인터를 사용한다.
   • i = 바뀜을 당할 위치 포인터 , i는 low부터 시작한다. [ 왼쪽 끝에서 시작 ]
   • j = arr를 순회할 포인터 pivot가 비교될  값들 
3.  arr[j] <= pivot 일 때
   
   • pivot 이하라는 것은 왼쪽에 위치해야하므로, i를 증가 즉, 바뀔 공간을 확보한다.
   • 이후 j와 i 값을 바꿈 , swap(i,j) 이후 다음 순회를 반복
4. 이후 j가 끝가지 순회를 맞추면 pivot값을 알맞은 위치에 넣어준다.
   • 그 위치는 바로 i이 된다. 이유는 pivot보다 작은 값들이 i번째까지 모두 채워졌기 때문에 pivot은 i+1 위치가 된다.
5. 이후 partition함수는 정렬된 이후 piviot위치인 i를 리턴하여 다음 분할에는 피벗을 기준으로
   왼쪽과 오른쪽으로 나눠질 수 있게한다.

한번 예를 통해 알아보자.

 

arr = [33, 10, 59, 27, 42, 77, 15, 19] 일 때 첫번 째 partition을 끝내면 다음과 같이 정리된다. 

Partition 결과:

• 피벗 19는 정렬된 상태로 제 위치에 놓인다.
• 다음 분할은 왼쪽 [10, 15], 오른쪽은 [27, 42, 77, 33, 59]이 됩다

코드

func quicksort(_ arr: inout [Int], _ low: Int, _ high: Int) {
    if low < high {
        // 배열을 분할하고 피벗 위치를 받음
        let pivotIndex = partition(&arr, low, high)
        
        // 피벗을 기준으로 좌우 배열을 재귀적으로 정렬
        quicksort(&arr, low, pivotIndex - 1)  // 피벗보다 작은 부분
        quicksort(&arr, pivotIndex + 1, high) // 피벗보다 큰 부분
    }
}

func partition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
    // 피벗을 배열의 마지막 요소로 설정
    let pivot = arr[high]
    var i = low // 왼쪽에 배치될 공간
    
    for j in low..<high {
        // 현재 요소가 피벗보다 작거나 같으면 i를 증가시키고 교환
        if arr[j] <= pivot {
            arr.swapAt(i, j)
            i += 1
        }
    }
    
    // 피벗을 중앙 위치로 이동
    arr.swapAt(i, high)
    return i
}

 

장점

1. Divide & Conquer
   • 특정 상태(정렬된 상태)가 아닌 이상 평균 시간 복잡도는 O(NlogN)이며, 다른 O(NlogN) 알고리즘에 비해 대체적으로 속도가 매우 빠르다.
   • 유사하게 O(NlogN) 정렬 알고리즘 중 분할정복 방식인 merge sort에 비해 2~3배 정도 빠르다.
   • 이유는 오직 피벗을 기준으로 위치에 구애받지 않고 움직일 있기 때문에 멀리있는 요소끼리도 교환이 가능하다.
2. in-place-sort
   • 추가적인 별도의 메모리를 필요로 하지 않으며 재귀 호출 Stack 프레임에 의한 공간 복잡도는 logN으로 메모리를 적게 소비함

단점

1. worst case
   • RANDOMIZE가 추가로 필요할 수 있음
   • 특정 조건[ 정렬된 상태 ] 하에 성능이 급격하게 떨어진다. O(n^2)
2. 재귀를 사용
   • 재귀를 사용하지 못하는 환경일 경우 그 구현이 매우 복잡해진다.
3. UnStableSort
   • 순서는 보장되지 않는다.

---

퀵 선택

퀵 선택은 정렬을 하지 않고도 빠르게 해당 원소가 몇번째로 작은지 또는 큰지 알아낼 수 있다.

 

우리는 배열에서 k번째 작은 값을 알고 싶다고 하자.

개념

파티션 함수를 이용해보자.

파티션 함수는 piviot을 보다 작거나 같은 값들을 왼쪽에 배치한다. 

이후 정렬이 끝난 후 piviot의 위치를 리턴한다. 여기서 정렬이 끝난 piviot의 위치에 주목해보자.

 

piviot의 위치 = piviot이 현재 조건으로 정렬 시 몇번 째에 위치하는 지를 가르키는 값 

 

그렇가면 piviot의 위치를 통해 우리는 몇번째로 작은값 또는 큰값을 알아낼 수 있다?

 

코드

let n = [1, 3, 2, 5, 7, 6, 4].count
let k = 2

var arr: [Int] = [1, 3, 2, 5, 7, 6, 4]

func quickSelection(_ arr: inout [Int], k: Int) -> Int {
    
    func partition(_ low: Int, _ high: Int) -> Int {
        // 피벗을 배열의 마지막 요소로 설정
        let pivot = arr[high]
        var i = low // 왼쪽에 배치될 공간
        
        for j in low..<high {
            // 현재 요소가 피벗보다 작거나 같으면 i를 증가시키고 교환
            if arr[j] <= pivot {
                arr.swapAt(i, j)
                i += 1
            }
        }
        
        // 피벗을 중앙 위치로 이동
        arr.swapAt(i, high)
        return i
    }
    
    func select(_ low: Int, _ high: Int) -> Int {
        let piviotIndex = partition(low, high)
        if k < piviotIndex { // piviot이 더 크다면 , 오른쪽 부분 버림
            return select(low, piviotIndex-1) // 왼쪽 부분
        } else if k > piviotIndex { // piviot이 더 작다면 , 왼쪽 부분 버림 
            return select(piviotIndex+1, high) // 오른쪽 부분만 
        }
     
        return arr[k] // 만약 같다면 숫자 찾음 리턴
    }
    
    return select(0, n-1)
}

print(quickSelection(&arr, k: k-1))

 

장점

이상적인 경우 piviot의 값이 계속 중간에 위치할 때  n + n/2 + n/4 ...  = O(n)

단점

역시 마찬가지로 정렬이 이미 되어있다면 piviot이 항상 끝에 위치하여 O(n^2)

---

참고

 

빠른 선택 (Quick Select) 알고리즘