퀵 정렬

지금까지 포스팅에서 다뤘던 정렬 알고리즘은 모두(삽입, 선택, 버블) O(N^2)의 시간복잡도를 갖는다.

 

O(N^2)의 시간복잡도는 데이터 수가 매우 클 때 잘 사용할 수 없는 알고리즘이다. 대부분의 문제들이 큰 데이터를 제공하고 시간제한을 짧게 두기 때문에 더 빠른 알고리즘이 필요하다.

 

정렬 알고리즘중 빠른 알고리즘으로 퀵 정렬이 있다. 

 

퀵 정렬은 분할 정복을 이용한 대표적인 알고리즘으로, 평균 시간복잡도가 O(N * logN) 이다!  

 

분할 정복이라는 이름에서 알 수 있듯, 퀵 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할해 정렬한다.

 

퀵정렬은 특정한  값(pivot, 피봇)을 기준으로 기준보다 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

 

---

퀵 정렬이 이루어지는 모습을 살펴보자!

3 7 8 1 5 9 6 10 2 4

 

퀵 정렬에는 기준값이 필요한데, 이를 피봇(pivot)이라 부르며, 보통 배열의 첫 원소를 피봇으로 설정한다. 여기서는 3을 피봇으로 설정해보자.

 

(3) 7 8 1 5 9 6 10 2 4

 

퀵 정렬은 3(피봇)보다 큰 숫자를 왼쪽에서 오른쪽으로 찾고, 3보다 작은수를 오른쪽 왼쪽으로 찾는다.

 

이 때 3보다 큰 숫자인 7을 바로 찾고, 3보다 작은수로 2를 찾는다.

 

다음으로 큰 값과 작은 값의 자리를 바꾸어준다.

 

(3) 2 8 1 5 9 6 10 7 4

 

다시 피벗을 3으로 유지한채 앞에서와 동일하게 큰 값과 작은 값을 찾는다.

 

이 때 3보다 큰 값으로 8, 작은 값으로 1을 찾아 다시 그 둘의 위치를 바꿔준다.

 

(3) 2 1 8 5 9 6 10 7 4

 

앞에서와 동일하게 큰 값과 작은 값을 찾는다. 다시 8과 1을 찾는데 이때는 작은값의 인덱스가 큰 값의 인덱스보다 작다. 이때는 피봇과 작은 값의 위치를 바꾸어준다.

 

1 2 (3) 8 5 9 6 10 7 4 

 

이 때 3은 정렬이 완료됐고, 피봇 3을 기준으로 왼쪽은 3보다 작은 값이 오른쪽은 3보다 큰 값이 오는 것을 확인할 수 있다.

 

다음으로 이전 피봇 왼쪽 숫자 집합에서 첫번째 원소를 다시 피벗으로 삼고 오른쪽 집합에서 첫번째 원소를 다시 피벗으로 삼는다.

 

(1) 2 3 (8) 5 9 6 10 7 4

 

 

이때 왼쪽 집합에서 위에서 했던것을 반복한다. 작은 값은 찾을수 없어 자기 자신이 되고 큰 값은 2이다.

 

이 때 큰 값의 인덱스는 작은 값의 인덱스보다 큰데, 작은값과 피봇의 위치를 바꿔준다. 그러나 피벗과 작은값이 동일하기에 위치엔 변동이 없다.

 

1 (2) 3 (8) 5 9 6 10 7 4

 

2가 포함된 숫자 집합은 원소가 하나 뿐임으로 정렬된 것으로 친다.

 

 

1 2 3 (8) 5 9 6 10 7 4

 

이젠 3의 오른쪽 집합에서 아까와 동일하게 진행해주면 퀵 정렬은 끝이나게 된다.

 

---

퀵 정렬의 코드는 다음과 같다.

/**
 * O(N * logN)
 */
public class 퀵정렬 {
    public static void main(String[] args) {
        int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
        quickSort(arr, 0, arr.length-1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    static void quickSort(int[] data, int start, int end) {
        // start가 end보다 크거나 같다는것은 피봇을 기준으로 분할한 배열의 원소가 1개인 경우를 의미함
        // {1} {2, 4, 5, ...}
        if (start >= end) {
            return;
        }

        // 피봇은 첫번째 원소
        int key = start;
        // 오른쪽으로 이동하면서 피봇보다 큰 값을 찾는 인덱스
        int i = start + 1;
        // 왼쪽으로 이동하면서 피봇보다 작은 값을 찾는 인덱스
        int j = end;

        // 값 변경을 위해 임시변수 temp설정
        int temp;

        // 엇갈릴 때 까지 반복, 엇갈리는 경우 피봇과 작은 값 arr[i]와 변경해준다.
        while (i <= j) {
            // 피봇보다 큰 값을 찾는 반복문, 큰 값을 찾으면 반복문 중단
            // 인덱스를 제한을 설정하지 않는 이유는
            // i와 j가 **엇갈리면 피봇과 인덱스 i의 값을 변경하기 떄문
            while (i <= end && data[i] <= data[key]) {
                i++;
            }

            // 피봇보다 작은 값을 찾는 반복문, 작은 값을 찾으면 반복문 중단
            // *** 중요: {1, 10, 4, ...} 1이 피봇이 된다면 오른쪽에서 출발한
            // 인덱스 j는 값을 못찾고 배열을 탈출.. -> j는 시작 인덱스보다 작아야한다.
            while (data[j] >= data[key] && j > start) {
                j--;
            }

            if (i > j) {    // 엇갈린경우 피봇과 작은 값의 자리를 바꿔준다
                temp = data[j];
                data[j] = data[key];
                data[key] = temp;
            } else {    // 엇갈리지 않은경우.
                        // (즉 피봇보다 작은값과 큰값의 자리를 변경(인덱스 안에서))
                temp = data[j];
                data[j] = data[i];
                data[i] = temp;
            }
        }
        // 피봇을 기준으로 양옆에서 각각 정렬을 다시함.
        quickSort(data, start, j - 1);
        quickSort(data, j + 1, end);
    }
}

 

---

퀵 정렬은 기본적으로 N번씩 탐색하되 반으로 쪼개 들어간다는 점에서 log N을 곱한 복잡도를 가진다. 따라서 N * log N의 시간 복잡도를 가진다.

 

하지만 일반적인 숫자 집합일때 빠른 연산속도를 자랑하지만 최악의 경우 O(N^2)의 시간 복잡도를 가진다.

 

그렇다면 최악의 경운는 어떤 때 일까?

 

1 2 3 4 5 6 7 8 9 10의 숫자 집합의 경우 정렬이 이미 끝나있는 상태다. 이 때 퀵 정렬을 사용해보자.

 

(1) 2 3 4 5 6 7 8 9 10

 

1보다 큰 숫자는 바로 2인 것을 찾을수 있지만 작은 값은 1, 자기 자신이 되어버린다.

 

때문에 큰 값과 작은 값의 인덱스가 서로 교차 함으로 작은값과 피봇의 위치를 바꿔주는데, 작은 값은 1 자기 자신이 되어 정렬이 일어나지 않는다.

 

그리고 피벗의 왼쪽에는 아무 집합도 안남아 있기 때문에 숫자 배열을 반으로 나눌 수 가 없다.

 

즉, 분할해서 처리하는 퀵 정렬의 장점을 사용할 수가 없고 시간복잡도는 O(N^2)에 가깝게 된다.

 

---

 

여타 정렬 문제에서 N log N 의 시간복잡도를 유도하면서 테스트 케이스에 정렬이 거의 끝난 숫자 배열을 넣는 경우가 있다.

 

이 때 퀵 정렬을 쓰면 O(N^2)에 가까운 시간복잡도 때문에 실패하는 경우가 생긴다.