[알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때

퀵 정렬

퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다.

가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다.

시간복잡도는 평균적으로 O(nlogn)이고, 추가적인 공간을 거의 사용하지 않는다.

실제 가장 많이 사용하는 정렬 알고리즘이기도 하다.

비교 기반 정렬 알고리즘은 O(nlogn)보다 빠를 수 없다.

 

퀵 정렬의 과정

1. 배열 안에 있는 요소 중 하나를 피벗(pivot)으로 고른다.

2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮겨 분할한다.

3. 분할된 왼쪽 배열과 오른쪽 배열에서 다시 pivot을 정하고 재귀를 이용하여 더 이상 나눠지지 않을 때까지 분할을 반복한다.

4. 더 이상 분할이 되지 않는다면, 양쪽 배열을 정렬 및 합병한다.

 

다음과 같은 배열이있다고 하자.

이 배열을 오름차순으로 퀵 정렬을 한다고 할 때, 

우선 pivot을 설정해야 한다.

pivot을 설정하는 방법은 여러 가지가 있다. 

가장 앞의 원소를 고를 수도 있고, 중간 원소 또는 가장 뒤의 원소, 랜덤으로 pivot을 뽑는 방법이 있다.

 

우선 중앙에 피벗을 잡아보자.

• 중앙에 pivot을 설정했다면 가장 왼쪽은 left, 오른쪽을 right로 잡는다.
• left는 pivot보다 큰 수를 만나거나, pivot을 만나면 멈추게 된다.
• right는 pivot보다 작은 수를 만나거나, pivot을 만나면 멈추게 된다.
• 이 배열에서 left는 5가 4보다 크므로 움직이지 않고, right는 2가 4보다 작으므로 멈춘다.
• 두 값을 바꿔준다.

• 이 과정을 left가 right보다 오른쪽으로 올 때까지 반복을 할 것이다.

• 이제 맨 처음부터 right까지와 left부터 맨 끝까지의 배열로 분할을 하여 위의 과정을 재귀적으로 반복을 한다.

• 왼쪽 배열 정렬 과정
  • left가 2로 1보다 크므로 움직이지 않는다.
  • right는 pivot을 만나 1에서 멈춘다.
  • left와 right를 swap한다.
  • left와 right가 한 칸씩 움직이고, 이때 left가 right보다 오른쪽으로 가게 되므로 종료한다.
  • right가 왼쪽 끝에 도달했으므로 또 한 번 재귀적으로 정렬할 필요가 없다.
• 오른쪽 배열 정렬 과정
  • left는 6으로 5보다 크므로 움직이지 않는다.
  • right는 pivot을 만나 멈춘다.
  • left와 right를 swap한다.
  • left와 right가 한 칸씩 움직이고, 이때 left가 right보다 오른쪽으로 가게 되므로 종료한다.
  • 왼쪽 배열과 마찬가지로 right가 끝에 도달하므로 재귀적으로 정렬할 필요가 없다.
• 이와 같이 모든 정렬이 끝났다면 오름차순으로 정렬된 배열을 발견할 수 있다.

퀵 정렬의 특징

• 시간 복잡도는 최선의 경우 O(nlogn)이고, 최악의 경우 O(n2)이다.
• 퀵 정렬은 재귀적으로 정의되어 재귀 호출에 따른 스택이 사용된다.
  이때 스택의 깊이는 n개의 원소에 대해 logn에 비례하여 공간복잡도가 O(nlogn)이다.
• 평균적으로 가장 빠른 정렬 알고리즘이다.
• 정렬하고자 하는 배열 내에서 교환하는 방식이므로 별도의 메모리 공간을 필요로 하지 않는다.
• 불안정 정렬이다.
• 정렬된 배열에 대해서 불균형 분할에 의해 오히려 수행 시간이 더 걸린다.

퀵 정렬 코드

public class quickSort {
    public static void main(String[] args) {
        int[] arr = {5, 1, 6, 4, 3, 2, 7};
        System.out.println("정렬 전: ");
        for(int i=0; i<arr.length; i++) System.out.print(arr[i] + " ");
        System.out.println();
        quickSort(arr, 0, arr.length-1);
        System.out.println("정렬 후: ");
        for(int i=0; i<arr.length; i++) System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void quickSort(int[] arr, int l, int r) {
        int left = l;
        int right = r;
        int mid = (l + r) / 2;
        int pivot = arr[mid];
        while(left <= right) {
            while(arr[left] < pivot) left++;
            while(arr[right] > pivot) right--;
            if(left <= right) {
                swap(arr, left, right);
                left++;
                right--;
            }
        }
        if(l < right) quickSort(arr, l, right);
        if(left < r) quickSort(arr, left, r);
    }
    public static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}