퀵 정렬(Quick Sort)에 대해 알아보자 (feat. JAVA)

 

 

퀵 정렬(Quick Sort) ?

 

 

퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하기 때문에 비교 정렬에 속한다.

퀵 정렬은 평균적으로 O(n log n)번의 비교를 수행하지만 최악의 경우 O(n²)번의 비교를 수행한다.

원소들 중에 같은 값이 있는 경우 같은 값들은 정렬 이후 초기와 순서가 달라질 수 있기 때문에 불안정 정렬이다.

( 예 : 5₁, 5₂, 3, 2, 1를 정렬하면 1, 2, 3, 5₁, 5₂ 이 된다. )

실제 임상 자료(real-world data) 정렬 시 가장 빠른 알고리즘이다.

 

* 퀵 정렬은 일반적인 보편적으로 가장 빠른 정렬 속도를 보여주는 분할-정복 알고리즘 중 하나이지만 오름차순, 내림차순 등 이미 정렬되어 있는 배열의 재정열에 사용 시 최악의 성능을 보여주고 일반적으로 우리가 푸는 코딩 테스트 문제는 퀵 정렬을 저격하는 테스트 케이스가 포함되어 있는 경우가 많기 때문에 알고리즘 문제풀이에 퀵 정렬을 시도하는 것은 시간 낭비일 수 있다. 

( 짤이 저런 이유는 알고리즘 풀이를 위해 퀵 정렬을 시도하며 날린 나의 시간 때문이다 ^^~~ )

 

 

 

퀵 정렬은 어떻게 동작하는가?

 

 

퀵 정렬은 기본적으로 재귀에 대한 최소한의 이해가 필요하다.

또한 피벗이 시작되는 위치에 따라 코드 작성 방식도 다르다.

사실 유튜브로 보는 게 낫다. 유튜브로 배우자.

 

퀵 정렬에서는 우선 피벗(Pivot)이라고 불리는 기준점이 필요하다. 위 예제에서는 7번 인덱스(6)을 피벗으로 삼고 있다.

첫 정렬 시 정렬 과정은 다음과 같다.

 

1. 피벗을 정한다.

2. 시작 인덱스부터 체크하는 반복문과 끝나는 지점에서부터 체크하는 반복문을 만든다.

3. 우측에서 출발한 포인터는 5보다 작은 숫자를 만나면 좌측 포인터가 5보다 큰 숫자를 만날 때까지 대기하고, 좌측에서 출발한 포인터는 5보다 큰 숫자를 만나면 우측에서 출발한 포인터가 5보다 작은 수를 만날 때까지 대기한다.

4. 서로 대기 상태에 놓이면 값을 교환하고 맞닥뜨리는 순간까지 이 과정을 반복한다.

5. 이제 정렬한 배열을 반으로 나누어 pivot보다 작은 정렬과 큰 정렬로 나눈다.

6. 재귀를 이용해 이 과정을 반복한다.

 

동작 원리를 알았으니 왜 오름차순이나 내림차순 정렬에서 최악의 성능을 보여주는지 알 것이다.

만약 1, 2, 3, 4, 5가 있는 배열을 1이나 5를 피벗으로 잡고 반대 순서로 정렬한다면 파티션을 몇 번 나눠야하는 지 생각해보자.

 

 

 

 

 

 

퀵 정렬 코드 예제

 

위 예제와 조금 다른 방식으로 구현했다.

큰 차이는 없기 때문에 아래 예제를 보고 위 예제를 구현하는 것도 어렵지 않을 것이다.

 

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

 

우선 배열 인덱스 값 교환을 쉽게 해주기 위해 swap 메서드를 만들었다.

 

public static void quickSort(int[] arr, int left, int right) {
    if ( left < right ) {
        int p = partition(arr, left, right);

        quickSort(arr, left, p-1);
        quickSort(arr, p+1, right);
    }
}

 

배열의 시작 인덱스와 마지막 인덱스를 받아 메서드 호출 시 partition 메서드로 피벗의 위치를 구하고, 구한 피벗의 위치로 새롭게 생성된 배열의 인덱스 값을 구해 재귀호출하여 배열을 정렬한다.

 

 

public static Integer partition(int[] arr, int left, int pivot) {
    int i = left-1;

    for (int j=left; j<pivot; j++) {
        if (arr[j] < arr[pivot]) {
            i++;
            swap(arr, arr[j], arr[i]);
        }
    }

    swap(arr, pivot, i+1);
    return i+1;
}

 

재귀 내에서 실질적으로 값을 정렬하는 메서드이다.

일반적인 방법은 left부터 ++, 그리고 rigth부터 --로 움직이는 for문 두개를 만들어서 둘의 인덱스가 겹칠 때까지 비교하며 교환하는 것이 보통의 예제인데.

이건 일단 피벗보다 작은 값은 무시하고 지나간 뒤 피벗보다 큰 값을 만나면 해당 값을 제일 앞으로 보내버리는 방식으로 피벗보다 큰 값이 들어가는 배열과 작은 값이 들어가는 배열을 분할한다.

둘 다 사용해봤으나 걸리는 시간이 별 차이가 없고 오히려 이게 더 직관적인 것 같다.

 

알고리즘 풀이에 도움은 안된다고 하지만 교양을 쌓은 것으로 만족하자.. ^^~~