퀵정렬

의미>

특정한 값을 기준으로 배열을 해당 값보다 작은 쪽, 큰 쪽으로 가른다. 그렇게 가르면 하나의 배열이 두 개의 조각이 되는데 각 조각에서 또 특정 값을 기준으로 잡아 해당 값보다 작은 쪽, 큰 쪽으로 배열을 나눈다. 이런 행위를 재귀적으로 반복하여 결국 처음 타겟이었던 배열 본체를 정렬하는 정렬 방법이다.

지금까지 했던 어떤 배열보다도 시간복잡도가 낮다. 이유는 반복을 두 번 중복으로 사용하지 않고 한 번만 사용하기 때문이다.

​

​

코드예시>

#include <stdio.h>

int number = 10;
int array[10] = {5, 7, 8, 9, 4, 6, 1, 3, 2, 10};

int show(int* array){
    
    for(int i = 0; i < 10; i ++){
        printf("%d ", array[i]);
    }

}

void quickSort(int* array, int start, int end){

    if(start >= end){
        return;
    }

    int pivot = start;
    int left = start + 1;
    int right = end;
    int temp;

// left와 right가 엇갈릴 때까지 반복
while(left <= right){

        // 기준값보다 left원소 값이 작을 때까지 반복(=기준값이 더 크면 인덱스를 증가시킴)
        while(array[pivot] >= array[left]){
            left++;
        }

        // 기준값보다 right원소 값이 클 때까지 반복(=기준값이 더 작으면 인덱스를 감소시킴)
        // while(array[pivot] <= array[right]){ 
        // 위 처럼 (left <= right) 가 없으면 right가 한없이 left쪽으로 감소됨
        while((left <= right) && (array[pivot] <= array[right])){
            right--;
        }

        if(left > right){ // 엇갈린 경우에는 pivot값과 right를 스왑
            temp = array[pivot];
            array[pivot] = array[right];
            array[right] = temp;
        }else{ // 엇갈리지 않은 경우에는 left의 원소와 right의 원소를 스왑
            temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }

    // 위 과정으로 한 번 정렬이 되어 pivot 원소가 제자리를 찾아갔든 안갔든
    // 그대로 이 array상태로 다시 재귀적으로 quickSort() 호출

    // 위 과정을 통해 right가 변화했는데
    // pivot과 스왑이 되었든, left와 스왑이 되었든 right을 기준으로
    // 그 상태 그대로 좌, 우로 나누어서 quickSort 처리
    quickSort(array, start , right - 1);
    quickSort(array, right + 1, end);

    }

}

int main(void){
    quickSort(array, 0, 9);
    show(array);
}

​

​

시간복잡도>

O(N * logN)