[이코테 with Java] 퀵 정렬

퀵 정렬이란?

---

퀵 정렬이란 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식이다. 

퀵 정렬에서는 피벗(Pivot)이 사용되는 것이 특징이다. 

큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 "피벗"이라고 표현한다. 

 

책에서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)을 기준으로 퀵 정렬을 설명하고 있다. 

우선 리스트에서 "첫 번째 데이터"를 피벗으로 설정한다.

그 다음 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.

그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.

 

예를 들어 초기 데이터가 5 7 9 0 3 1 6 2 4 5라고 가정해보자.

5 7 9 0 3 1 6 2 4 5 

 

첫 번째 데이터가 피벗이기 때문에, "5"가 피벗이다.

 

그 다음, I, II, III 파트로 나누어 보겠다

 

I 파트

step 0

 

리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 '5'이다. 이후에 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경해준다. 

         5    7   9 0 3 1 6 2 4 8
         ^    ^                      ^
      피벗 피벗 Big      피벗 Small

 

        5 4 9 0 3 1 6 2 7 8

 

step 1

 

그다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데, 현재 '9'와 '2'가 선택되었으므로 두 데이터의 위치를 서로 변경한다.

       5 7   9   0 3 1 6 2 4 8
       ^      ^                ^
     피벗 피벗 Big     피벗 Small

 

       5 7 2 0 3 1 6 9 4 8

 

step 2

 

그다음 다시 피벗보다 큰 데이터와 작은 데이터를 찾는다. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있다. 이렇게 두 값이 엇갈린 경우에는 '작은 데이터'와 '피벗'의 위치를 서로 변경한다. 

즉, 작은 데이터인 '1'과 피벗인 '5'의 위치를 서로 변경하여 분할을 수행한다. 

        5 7 2 0 3 1                6 9 4 8 
        ^              ^                ^
      피벗    피벗 Small   피벗 Big

 

        1 7 2 0 3 5 6 9 4 8 

 

step 3 - 분할 완료

 

이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보자. 이제 '5'의 왼쪽에 있는 데이터는 모두 '5'보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 "분할(Divide)" 혹은 "파티션(Partition)"이라고 한다. 

  1 4 2 0 3        5         6 9 7 8
--피벗small---피벗----피벗big-

 

 

II 파트

지금부터는 피벗보다 작은 리스트(왼쪽 리스트)에서 정렬을 실행해주면 된다.

step 0

 

리스트의 첫 번째 데이터를 피벗으로 설정하므로, 피벗은 '1'이다.

이후 왼쪽에서부터 피벗보다 큰 값을, 오른쪽에서부터 피벗보다 작은 값을 선택하여 바꿔주면 된다. 

즉, 4와 0을 바꾸어주면 된다.

1 4 2 0 3                            5 6 9 7 8

1 0 2 4 3                            5 6 9 7 8

 

step 1

 

그다음 왼쪽에서 피벗보다 큰 값을, 오른쪽에서 피벗보다 작은 값을 선택해야 하는데,

왼쪽에 피벗보다 작은 값이, 오른쪽에 피벗보다 큰 값이 있는 것을 확인할 수 있다.

따라서 피벗과 작은 데이터를 변경해준다.

최종적으로 0과 1을 변경해주면 된다. 

1 0      2 4 3                           5 6 9 7 8
   ^       ^
small big

 

0 1 2 4 3                               5 6 9 7 8

 

step 2 - 최종

 

이제 왼쪽에는 피벗보다 작은 값이, 오른쪽에는 피벗보다 큰 값이 나열되어 있다.

따라서 다시 한 번 더 정렬을 해준다.

0 1은 제대로 정렬되어 있으므로, 2 4 3을 정렬해주면 된다.

1) 첫 번째 값이 피벗이므로 2가 피벗이다.

2) 피벗보다 큰 값들이 이미 정렬되어 있으므로, 그 다음 수를 피벗으로 설정해준다.

3) 그 다음 수인 4를 피벗으로 선택한 후, 피벗보다 큰 값을 왼쪽에서부터 찾고, 작은 값을 오른쪽에서부터 찾는다.

이때 작은 데이터가 3이므로, 피벗과 4를 변경해준다. 

0 1 2 3 4 5 6 9 7 8

 

III 파트

지금부터는 피벗보다 큰 리스트(오른쪽 리스트)를 정렬해주면 된다.

따라서 5보다 오른쪽에 있는 6 9 7 8을 나열해줘야 하는데, 6 옆에는 6보다 큰 값만 있으므로, 그 다음 수인 9를 피벗으로 한다. 

step 0

 

리스트의 가장 첫 번째 데이터를 피벗으로 설정하기 때문에 9를 피벗으로 설정한다.

그 다음 왼쪽에서는 피벗보다 큰 값, 오른쪽에서는 피벗보다 작은 값을 찾아준다.

이때, 피벗보다 큰 값이 없기 때문에 오른쪽 첫 번째에 있는 8과 피벗인 9를 변경해준다.

그러면 9를 기준으로 피벗보다 작은 값만이 피벗의 왼쪽에 남아 정렬된다.

0 1 2 3 4 5 6          9 7 8
                             ^      ^
                           피벗 피벗 small

0 1 2 3 4 5 8 7 9

step 1

 

이제 9를 기준으로 피벗보다 작은 값들이 나열되었으니, 8을 피벗으로 설정해준다.

오른쪽부터 작은 수를 찾으면 7이므로, 8과 7을 교환해준다.

0 1 2 3 4 5 6         8 7     9
                             ^ ^
                     피벗 피벗 small  

 

0 1 2 3 4 5 6 7 8 9

 

이렇게 정렬이 완료된다.

퀵 정렬에서는 이처럼 특정한 리스트에서 피벗을 설정하여 정렬을 수행한 이후에 피벗을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 

이는 '재귀 함수'와 동작 원리가 비슷하다. 따라서 종료 조건도 있어야 한다.

퀵 정렬이 끝나는 조건은 무엇일까? 바로 "현재 리스트의 데이터 개수가 1개"인 경우이다.

리스트의 개수가 1개라면 이미 정렬이 되어 있다고 간주할 수 있으며 분할이 불가능하다. 

 

코드

import java.util.*;

public class Main {

    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 원소가 1개인 경우 종료
        int pivot = start; // 피벗은 첫 번째 원소
        int left = start + 1;
        int right = end;
        while (left <= right) {
            // 피벗보다 큰 데이터를 찾을 때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) left++;
            // 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) right--;
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            if (left > right) {
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            }
            // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }

    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        quickSort(arr, 0, n - 1);

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

 

퀵 정렬의 시간 복잡도

---

퀵 정렬은 선택 정렬과 삽입 정렬에 비해 속도가 빠르다.

선택 정렬과 삽입 정렬은 O(N^2)이지만, 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 

 

데이터의 개수가 8개라고 가정하고 다음과 같이 정확히 절반씩 나눈다고 도식화 해보자.

이때 '높이'를 확인해보면, 데이터의 개수가 N개일 때 높이는 약 logN이라고 판단할 수 있다.

 

퀵 정렬은 '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다. 

삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작한다고 했는데, 

퀵 정렬은 그와 반대된다고 이해할 수 있다.