퀵정렬(QuickSort)이란?

퀵 정렬(Quick Sort)

퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다.

평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다.

 

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot이라고 한다.
2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 povot의 오른쪽으로 옮긴다.
3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   3-1) 분할된 왼쪽 리스트와 오른쪽리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.
   3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반복한다.

위와 같은 배열을 오름차순으로 퀵정렬한다고 치자. 가장 먼저 pivot을 설정해야 하는데, pivot을 설정하는 것에는 여러가지 방법이 있다. 가장 앞의 원소, 중간 원소, 혹은 가장 뒤의 원소를 택하는 등의 방법이 있는데 여기서는 중간 원소를 pivot값으로 설정하는 것을 택하겠다.

 

• 중간 값을 pivot으로 설정했다면 가장 왼쪽의 값을 left, 오른쪽의 값을 right로 잡는다.
• left는 오른쪽으로, right는 왼쪽으로 이동하게 되는데 이때
• left는 pivot보다 큰 수를 만나거나 pivot을 만나면 멈추고
• right는 pivot보다 작은 수를 만나거나 pivot을 만나면 멈춘다.
• 따라서 5가 3보다 크므로 left는 5에서 멈추고, 2가 3보다 작으므로 right는 2에서 멈춘다.

• left와 right가 멈췄을 때, left가 right보다 왼쪽에 있다면 elft와 right값을 교환해준다.
• 이후 left를 오른쪽으로 한칸, right를 왼쪽으로 한 칸 이동해준다.
• 위 과정을 left가 right보다 오른쪽으로 올 때까지 반복한다.

• 6이 3보다 크므로 6에서 left가 멈춘다.
• right는 pivot을 만나서 멈춘다.
• 이 때 left가 right보다 왼쪽에 있으므로 left와 right값을 교환한다.
• left를 오른쪽으로 한 칸. right를 왼쪽으로 한 칸 이동한다.
• left가 right보다 오른쪽에 있으므로 종료한다.

right가 L보다 크다면 L부터 right까지 다시 위 과정을 재귀적으로 반복한다.

left가 R보다 작다면 left부터 R까지 다시 위 과정을 재귀적으로 반복한다.

 

 

왼쪽 부분 배열 정렬 과정

• LEFT는 2에서 멈춘다.
• RIGHT는 PIVOT에서 멈춘다.
• LEFT가 RIGHT보다 왼쪽에 있으므로 둘을 교환한다.
• LEFT를 오른쪽으로 한칸, RIGHT를 왼쪽으로 한칸 이동한다.
• LEFT가 RIGHT보다 오른쪽에 있으므로 종료한다.
• 이때 RIGHT가 L보다 크지 않으므로 왼쪽배열(L부터 RIGHT)는 다시 재귀적으로 정렬할 필요가 없다.
• LEFT는 R보다 작으므로 LEFT부터 R까지 다시 재귀적으로 정렬을 수행한다.

오른쪽 부분 배열 정렬 과정

• LEFT는 6에서 멈춘다.
• RIGHT는 PIVOT에서 멈춘다.
• LEFT가 RIGHT보다 왼쪽에 있으므로 둘을 교환한다.
• LEFT를 오른쪽으로 한 칸, RIGHT를 왼쪽으로 한칸 이동한다.
• LEFT가 RIGHT보다 오른쪽에 있으므로 종료한다.
• 이때 RIGHT가 L보다 크지 않으므로 왼쪽 배열 (L부터 RIGHT)은 재귀적으로 정렬할 필요가 없다.
• LEFT는 R보다 작으므로 LEFT부터 R까지 다시 재귀적으로 정렬을 수행한다.

퀵 정렬 특징

• 퀵정렬은 재귀적으로 정의되므로 재귀 호출에 따른 스택이 사용된다. 이때 스택의 깊이는 N개의 원소에 대해 logN에 비례하므로 공간복잡도는 O(NlogN)이다. 따라서 in-place 정렬이라고 하기 힘들지만, 실용적으로는 상대적으로 작은 메모리만을 사용하므로 흔히 in-place 정렬이라고 기술하기도 한다.
• 퀵정렬은 최악의 경우 pivot이 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설절된다면 원소 n개에 대해서 n번, (n-1), (n-2)...1번의 비교가 필요하므로 시간복잡도가 O(N^2)이 된다.
• 하지만 평균 시간복잡도는 O(NlogN)으로 매우 빠르다. pivot 값이 적절히 설정된다면 그 속도가 매우 빠르다. 따라서 pivot값을 잘 설정하는 것이 중요하다.
• 퀵정렬은 중복된 키값이 순서대로 바뀌지 않을 수 있어 not-stable하다.

---

퀵 정렬 코드

void quickSort(int arr[], int L, int R) {
    int left = L, right = R;
    int pivot = arr[(L + R) / 2];
    int temp;

    do {
        while (arr[left] < pivot) //left가 pivot 보다 큰 값을 만나거나 pivot을 만날 때 까지
            left++;
        while (arr[right] > pivot)//right가 pivot보다 작은 값을 만나거나 pivot을 만날 떄 까지
            right--;
        if (left <= right) { //left가 right보다 왼쪽에 있다면 교환
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            left++; //오른쪽으로 한칸
            right--;//왼쪽으로 한칸
        }
    } while (left <= right); //left가 right보다 오른쪽에 있을 떄 까지 반복

    if (L < right)
        quickSort(arr, L, right); //왼쪽배열 재귀적으로 반복

    if (left < R)
        quickSort(arr, left, R); // 오른쪽 배열 재귀적으로 반복
}