[알고리즘 정렬] 퀵 정렬(Quick Sort)

  퀵 정렬(Quick Sort)이란 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식입니다. 알고리즘 복잡도는 기준 값이 최소값 또는 최대값으로 지정되는 경우에는 O(n^2)입니다. 그러나 평균적으로는 O(n log n)이며, 이보다 더 빠른 경우도 있습니다.

 

이미지 출처: 위키백과, 퀵 정렬 항목

 

  퀵 정렬 구현 코드

public class Main {
    public static void quickSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(array, left, right);
        quickSort(array, left, pivot - 1);
        quickSort(array, pivot + 1, right);
    }
    public static int partition(int[] array, int left, int right) {
        int pivot = array[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (array[j] > pivot && i < j) {
                j--;
            }
            while (array[i] <= pivot && i < j) {
                i++;
            }
            swap(array, i, j);
        }
        swap(array, left, i);
        return i;
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

  매개 변수로 배열 array, 정수형 left, 정수형 right를 받는 quickSort 메소드를 생성합니다.

  if문에서 left가 right보다 크거나 같을 때 반환합니다.

  변수 pivot은 partition 메소드를 호출하고 인자에 array, left, right를 받습니다.

  quickSort를 재귀적으로 호출하여 인자에 array, left, pivot -1을 받습니다. 다시 quickSort를 호출하여 인자에 array, pivot + 1, right를 받습니다. 이는 pivot을 기준으로 pivot을 제외한 좌우를 구분하여 정렬하는 것입니다.

  매개 변수로 배열 array, 정수형 left, 정수형 right를 받는 partition 메소드를 생성합니다.

  변수 pivot에 array의 left 번째 원소를 할당합니다. 변수 i와 변수 j에는 각각 left와 right를 할당합니다.

  바깥 while문은 i가 j보다 큰 동안 반복합니다. i와 j가 만날 때까지 반복하는 것입니다.

  안쪽 첫 번째 while문은 array의 j번째 원소가 pivot보다 크고 동시에 i가 J보다 작을 때 j가 반복하여 감소합니다.

  안쪽 두 번째 while문은 array의 i번째 원소가 pivot보다 작거나 같을 때 동시에 i가 j보다 작을 때 i가 반복하여 증가합니다.

  바깥 while문이 반복되는 동안 swap 메소드를 호출하고 앞서 찾은 인덱스를 이용하여 인자에 array, i, j를 받습니다.

  while문이 끝나면 swap 메소드를 호출하여 인자에 array, left, i를 받습니다. swap 하기 전 pivot은 left 위치에 있습니다. i의 위치가 j와 만나면 pivot과 i의 위치를 변경하는 것입니다.

  pivot의 위치가 i로 변경되므로 i를 반환합니다. 반환 값을 기준으로 다시 좌우를 분할하여 quickSort를 진행합니다.

  매개 변수로 배열 array, 정수형 i, 정수형 j를 받는 swap 메소드를 생성합니다.

  임시 변수 temp에 array의 i번째 원소를 할당합니다.

  array의 i번째 원소에 array의 j번째 원소를 할당합니다. array의 j번째 원소에 임시 변수 temp을 할당합니다. swap은 임시 변수를 이용하여 두 원소의 위치를 변경하는 기능을 합니다.