퀵 정렬

퀵 정렬은 분할 정복 알고리즘의 일종이다.

 

퀵 정렬은 key값을 정하고 key값을 기준으로 왼쪽은 작은 값 오른쪽은 큰 값을 모은 뒤, 

 

key값을 알맞은 위치에 삽입하고 이 위치를 기준으로 분할하여 퀵 정렬을 수행한다.

 

말로만 보면 복잡하여 이해하기가 어렵다.

 

void quickSort(int* arr, int start, int end) {
    if (start >= end) return;
    
    int key = start;
    int i = start + 1;
    int j = end;
    int temp;

    while (i <= j) {
        while (arr[key] >= arr[i]) i++;
        while (arr[key] <= arr[j] && key < j) j--;

        if (j < i) {
            temp = arr[j];
            arr[j] = arr[key];
            arr[key] = temp;
        }
        else {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }

    quickSort(arr, start, j - 1);
    quickSort(arr, j+1, end);
}

코드를 보면 반복문을 통해 i, j 값을 변화 시키는 부분이 있다. 

 

여기서 key값보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시키게 된다.

 

그러다 i와 j가 엇갈리면 key값의 알맞은 자리가 생긴 것이다. 

 

그러면 전체 반복문이 종료되고 분할 된 부분에 퀵 정렬이 시작된다.