QUICK SORT 정리..[C]

퀵정렬

분할정복법(divide ans conquer) 사용한다.
O(NlogN) 시간 복잡도를 가진다.

오름차순 기준)
개념: 피봇값을 기준으로 더 작은 수를 왼쪽으로, 더 큰 수를 오른쪽으로 옮긴다.
왼쪽부터 하나씩 확인하며 피봇보다 큰 값을 찾고,
오른쪽부터 하나씩 확인하며 피봇보다 작은 값을 찾아,
이 둘의 위치를 바꾼다.
그러다 엇갈리게 되면, 피봇값과 엇갈린 앞에 값 위치를 바꾼다.
코드로 이해하는 게 제일 나을 듯 하다.

소스코드를 깔끔하게 하려면 재귀함수로 구현

#include<cstdio>
void quickSort(int *data, int start, int end) {
    printf("called! start: %d, end: %d\n", start, end);
    for(int i=start;i<end;i++) printf("%d ", data[i]);
    printf("\n");

    if(start >= end) return; // 원소가 1개인 경우 + 맨 왼쪽 최소값은 정렬한 경우 원소 0짜리도 나옴. 예) (1 2)

    int pivot = start; // 첫번째 값을 피봇으로 잡았다.
    int i = start+1;
    int j = end;
    int tmp;

    // 피봇값이 '한 번 움직일 때'까지 수행.
    while(i<=j) { // j가 i보다 크거나 같으면 계속 함. 즉 i가 j보다 더 커야지 끝남.
        while(data[pivot] >= data[i] && i < end+1) { // 피봇값이 i값보다 크면 계속 i를 증가시킴.
            // 일부러 end를 1 넘어가게 설계함. 밖에 나가더라도 접근하는것만으로는 문제가 없으므로. 어차피 pivot과 교환되는 값은 j값임.
            // 이렇게하지 않으면 맨왼쪽 pivot값이 가장 큰 수일 경우, i==j상태에서 교착이 됨. (예: 9 1 3 2 4)
            printf("first while: %d\n", i);
            i++; // 왼쪽부터 1씩 더해간다.
        }
        while(data[pivot] <= data[j] && j > start) { // j는 최소 피봇까지 --하면서 내려올 수 있음. 즉 j==start==pivot까지 내려옴.
            printf("second while: %d\n", j);
            j--; // 오른쪽부터 1씩 빼간다.
        }
        if(i>j) { // 엇갈린 상황이면 왼쪽 j와 pivot을 교체
            printf("inside if: %d %d\n", i, j);
            tmp = data[j];
            data[j] = data[pivot];
            data[pivot] = tmp;
        } else {
            printf("inside else: %d %d\n", i, j);
            tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }
    // 피봇이랑 j값이랑 바꾼 후. 즉 현재 피봇==j
    quickSort(data, start, j-1); // 피봇 기준 왼쪽
    quickSort(data, j+1, end); // 피봇 기준 오른쪽
}
int main() {
    int data[15] = {1,4,5,7,8, 11,2,3,6,10, 20,15,18,30,22};
    quickSort(data, 0, 14);

    for(int i=0;i<14;i++) {
        printf("%d ", data[i]);
    }
}

최악의 경우

피봇값을 잘못 설정하는 최악의 경우는 이미 정렬되어있는 경우다.
O(n^2)이 나올 수 있다.

분할정복법(divide-and-conquer)을 사용하여 문제를 작은 문제로 쪼개기 때문에 O(nlogn)이 나오는 것인데,
이미 정렬되어있다면 피봇을 설정할 때 문제가 작은 문제로 쪼개지지 않는다.
따라서 nlogn의 빅오가 나온다.