[Algorithm] 정렬(3) - 퀵 정렬 with Java

 

퀵 정렬

퀵 정렬은 앞서 배웠던 선택 정렬, 삽입 정렬과 같은 정렬 알고리즘들 중에서 가장 많이 사용되는 알고리즘이다.

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작이 이루어진다.

 

이 퀵 정렬엔 피벗(Pivot)이 사용된다. 이 피벗이라는 것은 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'에 해당하는 것이다.

 

퀵 정렬을 수행하는 데 있어서 피벗을 어떻게 설정할 것인지 미리 명시를 해야 한다.

 

피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 여기서는 호어 분할 방식을 기준으로 퀵 정렬을 설명 한다.

 

호어 분할 방식

먼저 다음 규칙으로 피벗을 설정한다.

 

- 리스트에서 첫 번째 데이터를 피벗으로 정한다.

 

그 뒤에 왼쪽에서 피벗보다 큰 데이터를 찾고, 오른쪽에서 피벗보다 작은 데이터를 찾는다. 그 후에 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.

 

다음 단계 부터는 그림을 통해 자세히 알아보자.

 

 

리스트의 첫 번째 데이터를 피벗으로 설정하는 기준으로 피벗은 '4'이다. 이후에 왼쪽에서 '4'보다 큰 데이터를 선택하면 '7'이 선택 되고, 오른 쪽에서 '4'보다 작은 데이터를 선택하면 '3' 이 선택된다. 다음으로 이 선택된 두 데이터의 자리를 바꿔준다.

 

 

1단계 실행 결과 '3'과 '7'의 자리가 바뀌었다. 다음은 마찬가지로 왼쪽에서 '4'보다 큰 데이터, 오른쪽에서 '4'보다 작은 데이터를 선택한 후 자리를 바꾼다. 여기서 '5'와 '1'이다.

 

마찬가지로 '6'과 '0'의 자리도 바꿔준다.

 

 

이 부분이 상당히 중요하다. 이제 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 서로 엇갈린다.

 

이때 '작은 데이터'와 '피벗'의 위치를 서로 변경한다. 즉 여기서 '4'와 '0'의 위치를 서로 변경하여 분할을 수행한다.

 

분할 작업을 완료한 후에 보면 피벗이였던 '4'의 왼쪽의 데이터는 '4'보다 작고 오른쪽 데이터는 '4'보다 크다. 이러한 작업을 분할 혹은 파티션이라고 한다.

 

• 5단계

이와 같이 분할 작업을 한 이후에 왼쪽 데이터인 '0'과 오른쪽 데이터인 '6'을 다시 피벗으로 설정하여 각각의 정렬 작업을 진행해주면 정렬이 이루어지게 된다.

 

퀵 정렬의 경우 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다!

 

그러면 재귀 함수로 작성을 했는데 끝나는 조건을 어떻게 설정해야 하는가?

 

public class QuickSort {

    static int[] array = new int[] { 4, 7, 2, 5, 6, 0, 1, 3 };

    public static void main(String[] args) {
        quick_sort(0, array.length - 1);

        System.out.println(Arrays.toString(array));
    }

    public static void quick_sort(int left, int right) {

        if (left >= right) {
            return;
        }

        int pivot = partition(left, right);

        quick_sort(left, pivot - 1);
        quick_sort(pivot + 1, right);
    }

    public static int partition(int left, int right) {

        int low = left;
        int high = right;
        int pivot = array[left];

        while (low < high) {

            while (low < high && array[high] > pivot) {
                high--;
            }

            while (low < high && array[low] < pivot) {
                low++;
            }

            swap(low, high);
        }

        swap(pivot, low);

        return low;
    }

    public static void swap(int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}

 

 

시간 복잡도

	최선	평균	최악
퀵정렬	O(NlogN)	O(NlogN)	O(N^2)

 

퀵 정렬의 평균 시간 복잡도 -> O(NlogN)으로 선택 정렬, 삽입 정렬=O(N^2)에 비해 매우 빠른 편

 

퀵 정렬의 최악 시간 복잡도 -> O(N^2)

 

'이미 데이터가 정렬되어 있는 경우' 매우 느리게 동작하고, 오히려 데이터가 무작위로 입력되어 있는 경우에 빠르게 동작 할 확률이 높다.