Quicksort이란

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 범용 정렬 알고리즘이다.
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

우리가 지금껏 배워온 버블정렬이랑 선택정렬 이런것들에 비해서는 굉장히 빠르다.
파이썬의 sorted도 이 퀵정렬로 만들어졌을정도로 자주 쓰인다.

Quicksort을 어떻게 할까요?

1. 리스트 안에 있는 한 요소를 피벗으로 선택
2. 피벗보다 작은 요소들을 왼쪽으로 옮기고 피벗보다 큰 요소들을 오른쪽으로 옮김
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬됨

이것만 들어보면 뭔말인지 모르겠죠?
제가 쉽게 그림으로 설명해 드릴게요.

1. 첫번째 인덱스를 left, 마지막 인덱스를 right로 지정해줘요.

2. 배열의 left값을 피벗이라고 지정을 해줘요.

3. low는 left, high는 right+1로 지정을 해줘요.

4. low는 피벗과 비교하여 큰지 확인해주고 high는 작은지 확인을 해줘요.

5. 만약 둘다 확인을 하여 멈췄다면 둘이 스왑을 해주고 4번으로 돌아가요.

6. 만약 low와 high값이 바뀌었다면 멈추고 스왑을 진행해준뒤 high값을 리턴해주고 정렬이 될때까지 다시 1번으로 돌아가요.
   
   
   
   이런식으로 하는것이 Quicksort에요.
   이것을 계속 반복해주면 정렬이 되어있어요.

#include <stdio.h>

void swap(int *a, int *b);
int part(int list[], int left, int right);
void quicksort(int list[], int left, int right);

int main(void) {
    int a[6] = {3, 4, 214, 14, 1, 4};
    quicksort(a, 0, 5);
    for (int i = 0; i <= 5; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quicksort(int list[], int left, int right) {
    if (left < right) {
        int party = part(list, left, right);
        quicksort(list, left, party - 1);  
        quicksort(list, party + 1, right); 
    }
}

int part(int list[], int left, int right) {
    int low = left;
    int high = right + 1;
    int pivo = list[low];
    do {
        do {
            low++;
        } while (list[low] < pivo && low <= right);
        
        do {
            high--;
        } while (list[high] > pivo);
        
        if (low < high) {
            swap(&list[low], &list[high]); 
        }
    } while (low < high);
    
    swap(&list[left], &list[high]);
    return high;
}

저는 코드를 이런식으로 짰어요.
코드도 저 위에있는 설명을 보면서 이해를 하면 훨씬 편하게 이해할수 있어요.

팩트는 파이썬은 그냥 sorted딸깍 하면 된다는 사실이에요.

그냥 코테는 파이썬으로 하죠.