퀵 정렬

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

- 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot 이라고 불린다.)로 설정한다.

 

 

동작 예시

0) 0번째 원소 '5'가 피벗이다. 1번째 원소인 '7'은 '5'보다 크고, 마지막 원소인 '8'은 '5'보다 크다. 대신 '8' 앞의 원소인 '4'가 '5'보다 작다. 

- 따라서 '7'과 '4'의 위치를 바꾼다.

 

1) 피벗은 그대로 '5'다. 왼쪽에서부터 '5'보다 큰 데이터를 선택한다. 원소 '9'와 오른쪽의 '5'보다 작은 '2'를 바꾼다.

 

2) 왼쪽에서부터 피벗 '5'보다 큰 데이터는 '6'이고, 오른쪽에서부터 '5'보다 작은 데이터는 '1'이다. 

- 위치가 엇가리게 되었을 경우 피벗 '5'와 작은 데이터 '1'을 바꾼다.

 

3) 분할 작업이 완료되어, 피벗보다 작은 원소와 큰 원소가 분리되었다.

- 분할(Divide) : 피벗을 기준으로 데이터 묶음을 나누는 작업

 

4) 왼쪽 데이터 묶음 정렬도 위의 과정을 수행한다.

 

5) 오른쪽 데이터 묶음 정렬도 위의 과정을 수행한다.

 

시간복잡도

- 이상적인 경우 분할이 절반씩 일어난다면 O(NlogN)을 기대할 수 있다.

- 최악의 경우 O(N제곱)의 시간복잡도를 가질 수 있다. (이미 정렬된 배열에서 발생한다.)

 

 

 

예제코드

public class M11_퀵정렬 {
    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] + " ");
        }
    }

    public static void quickSort(int[] arr, int start, int end) {
        // 원소가 1개인 경우 종료
        if (start >= end) {
            return;
        }

        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);
    }
}