C++ / Swift ) 퀵정렬 (Quick Sort)

퀵 정렬은 분할정복 기법으로 pivot값을 이용해 정렬하는 알고리즘입니다.

한 번 수행할 때 마다 크기가 반씩 줄어들며, pivot 값을 기준으로 왼쪽은 pivot 보다 작은 수, 오른쪽은 pivot보다 큰 수들이 모이게 됩니다.

퀵 정렬은 평균적으로 O(NlogN)의 시간복잡도로 수행되지만 최악의 경우 O(N^2)의 시간복잡도를 가집니다.

---

C++ 소스 코드

#include <cstdio>
using namespace std;
int nums[] = {3,6,1,2,9,7,4,4,10,8};
void quickSort(int s,int e){
    if (s>=e) return;
    int p = s;
    int i = s+1;
    int j = e;
    while(i <= j) {
        while(i<=e && nums[i]<= nums[p]) i++;
        while(j>s && nums[j]>= nums[p]) j--;
        if (i>j){
            // 인덱스가 엇갈렸으면 작은 수, pivot swap
            int temp = nums[j];
            nums[j] = nums[p];
            nums[p] = temp;
        } else {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    quickSort(s,j-1);
    quickSort(j+1,e);
}
int main(){
    quickSort(0,9);
    for(int i=0;i<10;i++){
        printf("%d ", nums[i]);
    }
    return 0;
}

---

Swift 소스 코드

import Foundation

var nums = [3,6,1,2,9,7,4,5,10,8]

func quickSort(s: Int, e: Int) {
    if s >= e { return }
    var p = s
    var i = s + 1
    var j = e
    while i <= j {
        while i <= e && nums[i] <= nums[p] {
            i+=1
        }
        while j > s && nums[j] >= nums[p] {
            j-=1
        }
        if i > j {
            let temp = nums[j]
            nums[j] = nums[p]
            nums[p] = temp
        } else {
            let temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp
        }
    }
    quickSort(s: s, e: j-1)
    quickSort(s: j+1, e: e)
}

quickSort(s: 0, e: 9)
for num in nums {
    print(num)
}