[Algorithm] 퀵정렬(Quick Sort)

설명

• 분할 정복 기법으로 정렬하는 방식
• 거의 정렬된 상태에서는 분할 정복 기법의 장점을 활용할 수 없어 시간 복잡도가 높아질 수 있음
• 시간 복잡도 : 일반적으로는 O(N * logN), 최악에는 O(N^2)
• 참고
  • https://youtu.be/gBcUO_6JXIA

예시

1. 초기 데이터

• 3 7 8 1 5 9 6

2. 첫 요소를 피벗(p)으로 지정, 피벗보다 큰 값을 왼쪽(l)부터 탐색, 피벗보다 작은 값을 오른쪽(r)부터 탐색

• 3(p) 7(l) 8 1(r) 5 9 6

3. r이 l보다 오른쪽에 있기 때문에 r과 l 위치 변경

• 3(p) 1(l) 8 7(r) 5 9 6

4. 2과정과 동일하게 수행

• 3(p) 1(r) 8(l) 7 5 9 6

5. r이 l보다 왼쪽에 있기 때문에 r과 p 위치 변경

• 1(p) 3(r) 8(l) 7 5 9 6

6. r 기준으로 왼쪽 그룹과 오른쪽 그룹으로 나눠 위와 동일한 과정을 반복

코드

public class Solution {
    public static int[] sort(int[] data) {
        quickSort(data, 0, data.length - 1);

        return data;
    }

    private static void quickSort(int[] data, int start, int end) {
        // 원소가 1개인 경우 종료
        if (start >= end) {
            return;
        }

        // pivot : 첫 번째 원소를 피벗으로 지정
        // left : pivot보다 큰 값을 찾을 인덱스
        // right : pivot보다 작은 값을 찾을 인덱스
        int pivot = start;
        int left = start + 1;
        int right = end;

        // 엇갈릴 때 까지 반복
        while (left <= right) {
            // pivot보다 큰 값 찾기
            while (left <= right && data[left] <= data[pivot]) {
                left++;
            }

            // pivot보다 작은 값 찾기
            while (left <= right && data[right] >= data[pivot]) {
                right--;
            }

            // 엇갈리지 않은 경우 두 값 변경
            if (left < right) {
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
            }
        }

        int temp = data[right];
        data[right] = data[pivot];
        data[pivot] = temp;

        quickSort(data, start, right - 1);
        quickSort(data, right + 1, end);
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#array -> #result"() {
        expect:
        Solution.sort(array as int[]) == result

        where:
        array                           | result
        [1, 10, 5, 8, 7, 6, 4, 3, 2, 9] | [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    }
}