QuickSort (퀵 정렬)

퀵정렬은 Merge Sort와 마찬가지로 Divide and Quenquer(분할정복) 방식으로 접근해볼 수 있다.

 

분할 : 배열을 특정 값(= Pivot)을 기준으로 pivot 보다 작은 부분, 큰 부분으로 나눈다.

 

정복 : 각 부분을 순환적으로 정렬시킨다.

 

합병 : 퀵정렬은 합칠게 없다.

 

쉽게 말하자면

 

1. 어떤 배열이 존재할 때, 배열의 첫번째 값이나 마지막 값을 pivot으로 선택한다.

(여기서 pivot을 선택하는 것에 대해서는 뒤에서 더 자세하게 이야기 하겠다)

 

2. pivot을 기준으로 왼편에는 작은 값들이 위치하게 하고 큰 값은 오른쪽에 위치하게 시킨다

(이 때 각 값들은 정렬될 필요가 없으며, 오름차순,내림차순에 따라 오른쪽,왼쪽은 바뀔 수 있다)

-> 이러한 행위를 Partition 이라고 한다.

 

3. 이걸 나눠진 두 부분을 대상으로 1부터 반복한다(재귀)

 

4. 정렬 성공!

 

- 맨오른쪽을 피봇으로 선택시

import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int i = sc.nextInt();

        int[] arr = new int[i];
        for (int j = 0; j < i; j++) {
            arr[j] = sc.nextInt();
        }
        cur(arr, 0, i-1);

        for (int a : arr) {
            System.out.println(a);
        };

    }


    public static void cur(int[] arr,int front,int pivot) {
        if (front < pivot) {
            int p = partition(arr, front, pivot);
            cur(arr, front, p - 1);
            cur(arr, p + 1, pivot);
        }
    }

    public static int partition(int[] arr,int p,int r) {

        int cursor = p-1;

        for (int i = p; i < r; i++) {
            if (arr[r] >= arr[i]) {
                cursor++;
                swap(cursor, i, arr);
            }
        }
        swap(cursor + 1, r, arr);

        return cursor+1;
    }

    public static void swap(int a, int b, int[] arr) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

 

- 맨왼쪽을 피봇으로 선택 시 (위를 거꾸로하면 되는데 이번엔 다른 방식을 써봤다)

/**
 * Quick Sort(퀵 정렬)
 * - 임의의 기준 값 (= pivot)을 정하고 그 값을 기준으로 좌우 분할하며 정렬하는 방식
 * -
 * - 장점
 * - 특정한 경우를 제외하고는 O(nlogn)이며, 다른 O(nlogn) 알고리즘 보다 대체적으로 빠르다.(merge의 2~3배)
 * - in-place sort 이다
 * - 재귀호출로 인한 공간 복잡도가 logN으로 메모리를 적게 소비한다.
 * -
 * - 단점
 * - 특정한 경우 , 최악의 시간인 O(n^2)가 발생한다.
 * - 재귀를 사용하기 때문에 재귀를 사용하지 못하는 환경일 때 구현이 복잡해진다.
 */

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;
        int j = right;

        // 양쪽 끝에서부터 pivot값과 비교
        while (i < j) {
            // 오른쪽 끝에서부터 pivot값보다 작은 인덱스를 찾기
            // pivot보다 크면 다음 인덱스를 찾아야 하니 j--;
            while (arr[j] > pivot && i < j) {
                j--;
            }

            // 왼쪽부터 pivot 값 보다 큰 인덱스를 찾기
            // pivot보다 작으면 다음 인덱스를 확인해야하니 i++
            while (arr[i] <= pivot && i < j) {
                i++;
            }

            // 양쪽 끝에서부터 서로 걸린 값끼리 교환
            swap(arr, i, j);
        }

        // 맨처음이 pivot값이였으니 그것과 현재 i와j가 만난 부분을 교체(pivot을 기준으로 좌우로 나뉘어야 하므로)
        swap(arr, left, i);

        // 새로운 pivot 값 반환
        return i;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

Pivot선택 시 첫번째 값이나 마지막 값을 피봇으로 선택하는 것은 좋은 경우가 아니다

-> 이미 정렬된 데이터인 경우 최악의 경우인 O(N^2)이 나와버린다. 그런데 현실의 경우 랜덤하지 않고 정렬된 데이터가 입력으로 들어올 가능성이 매우 높으므로 좋은 방법이라 할 수 없다.

 

위의 상황을 토대로 중간값을 Pivot으로 선택하는 경우 현실적인 선택이라고 볼 수 있다. 그러나 최악의 경우 시간복잡도가 달라지는 것은 아니다.(그래도 중간값으로 구하는 것을 사용하자, 구글링 해보면 많이 나온다.)

 

랜덤으로 피봇을 정할 수도 있는데, 이 경우 어차피 운으로 정렬된 데이터가 들어오건 말걸 운으로 정해지는 것이기 때문에 평균 시간복잡도 O(NlogN)으로 볼 수 있다. 그래도 운안좋으면 O(N^2)가 나올 수도 있다.