[정렬 알고리즘] 두 배열의 원소 교체 3. 퀵 정렬로 풀어보기

📝 퀵 정렬 (Quick Sort)

기준(pivot)을 설정하고,
그 기준보다 큰지 작은지 판별하여 위치를 바꾸는 분할 정복 알고리즘이다.
분할 방법이 여러가지 존재하기 때문에 반드시 먼저 명시해야한다.
이번엔 첫번째 데이터를 기준으로 정하는 호어 분할(Hoare Partition)로 설정하여 진행해보자.

1️⃣ 순서

var data = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
1. 탐색할 범위를 설정한다.
2. 피봇을 설정한다.
	data[1] 부터 탐색 -> data[2] = 9
3. 값을 비교하여 피봇 보다 큰지 작은지 여부를 판단한다.
	data[9] 부터 탐색 -> data[8] = 4
4. 피봇보다 큰 데이터와 작은 데이터의 위치를 Swap한다.
	data[2] = 4, data[8] = 9
5. 위의 과정을 재귀로 반복하여 pivot의 왼쪽과 오른쪽을 분할하여 계속 정렬해나간다.

2️⃣ 코드

var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

func quickSort(_ array: inout [Int], start: Int, end: Int) {
    print("<< quickSort() 실행 >> ")
    print("0. start: \(start), end: \(end)")
    print("실행 전 : \(array)")
    print()
    if start >= end { return }          // -  원소가 1개인 경우 종료
    
    let pivot = start                   // 0. 기준  : 첫 번째 원소
    var left = start + 1                // 1. 왼쪽  : 시작위치 + 1
    var right = end                     // 2. 오른쪽 : 맨 끝
    print(">> pivot : \(pivot)")
    print(">> left : \(left)")
    print(">> right : \(right)")
    print()
    
    while left <= right {               // 3. 왼쪽 인덱스가 오른쪽 인덱스와 작거나 같다면 반복
        print(">> array[left] : \(array[left])")
        print(">> array[right] : \(array[right])")
        print()
        while (left <= end) && (array[left] <= array[pivot]) {
            left += 1                   // 4. 왼쪽부터 기준보다 큰 원소 찾기
            print("4. left += 1 >> \(left)")
        }
        while (right > start) && (array[right] >= array[pivot]) {
            right -= 1                  // 5. 오른쪽부터 기준보다 작은 원소 찾기
            print("5. right -= 1 >> \(right)")
        }
        if left > right {
            array.swapAt(right, pivot)  // 6. 엇갈렸다면 작은 데이터와 pivot 교체
            print("6. left가 right보다 커서 right, pivot 스왑 = \(pivot 기준 왼쪽은 작고, 오른쪽은 크도록 정렬 완료)")
        } else {
            array.swapAt(left, right)   // 7. 엇갈리지 않았다면 작은 데이터와 큰 데이터 교체
        }
        print(">> 분할 탐색 시작하기 전 : \(array)")
        print()
        print("------------------------------------------------------------")
        print()
        quickSort(&array, start: start, end: right - 1) // 8. 나머지 왼쪽 탐색
        quickSort(&array, start: right + 1, end: end)   // 9. 나머지 오른쪽 탐색
    }
}

quickSort(&array, start: 0, end: array.count - 1)
print(array)

• 손으로 그리다가 너무 오래걸려서 그냥 print를 다 찍어버렸다.
• 아마 눈으로 보는게 가장 빠를 것 같으니 그대로 실행해보길 권장한다.

3️⃣ 정리

• 안정성 : Unstable Sort
  - 동일한 원소에 대한 우선순위가 유지되지 않는다.
• 제자리성 : In-place
  - 기존 배열 이외의 메모리를 거의 사용하지 않는다.
• 시간 복잡도
  - 최선 : 𝛰(𝛮 𝑙𝑜𝑔 𝛮)
  - 최악 : 𝛰(𝛮 ²)

[문제] 두 배열의 원소 교체

N개의 원소로 이뤄진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 할 수 있다. 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 원소 합의 최댓값을 구하여라.

입력 조건
1. 첫째줄에는 N, K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
2. 둘째줄부터 각각 배열 A, B의 원소들이 주어진다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예

5 3
1 2 5 4 3
5 5 6 6 5

출력 예

26

🌀 풀이

글의 복잡성을 줄이기 위해 공통 input과, K번 바꾸기 연산은 첫 글에만 명시했습니다. 궁금하다면 여기를 눌러주세요.

// 퀵 정렬
private func ascendingQuickSort(_ array: inout [Int], start: Int, end: Int) {
    if start >= end { return }
    
    let pivot = start
    var left = start + 1
    var right = end
    
    while left <= right {
        while (left <= end) && (array[left] <= array[pivot]) {
            left += 1
        }
        while (right > start) && (array[right] >= array[pivot]) {
            right -= 1
        }
        if left > right {
            array.swapAt(right, pivot)
        } else {
            array.swapAt(left, right)
        }
        ascendingQuickSort(&array, start: start, end: right - 1)
        ascendingQuickSort(&array, start: right + 1, end: end)
    }
}

private func descendingQuickSort(_ array: inout [Int], start: Int, end: Int) {
    if start >= end { return }
    
    let pivot = start
    var left = start + 1
    var right = end
    
    while left <= right {
        while (left <= end) && (array[left] >= array[pivot]) {
            left += 1
        }
        while (right > start) && (array[right] <= array[pivot]) {
            right -= 1
        }
        if left > right {
            array.swapAt(right, pivot)
        } else {
            array.swapAt(left, right)
        }
        descendingQuickSort(&array, start: start, end: right - 1)
        descendingQuickSort(&array, start: right + 1, end: end)
    }
}

이번엔 그냥 함수자체를 나누어주었다!
이제 마지막 계수 정렬로 넘어가보자..!

🫥 글의 복잡성을 줄이기 위해 공통 input과, K번 바꾸기 연산은 첫 글에만 명시했습니다! 궁금하다면 여기를 눌러주세요.