퀵 정렬

핵심요약

• 시간 복잡도가 평균 O(nlogn)인 정렬 알고리즘들 중 가장 빠르다.
• 분할 정복 알고리즘
• 피벗의 선택이 효율에 큰 영향을 준다.

시간복잡도

• 평균적으로 O(nlogn)의 복잡도를 가진다.
• 모든 수가 역순으로 배열되어 있는 경우에 O(N^2)의 복잡도를 가지지만 정렬 기준을 맨 앞 값 대신 아무거나 하나 골라 잡는 방법으로 해결하면 거의 대부분의 경우에 의 성능을 보장받을 수 있다.
• 퀵 정렬은 피벗의 선택에 따라 효율성에 영향을 많이 준다.

기본 흐름

1. pivot 기준이 되는 값을 정한다
2. pivot을 기준으로 왼쪽에는 보다 작은값, 오른쪽에는 보다 큰 값이 모이게 한다. - partition
3. 모든 값이 정렬될때까지 partition이 반복되게 한다.

• 배열을 내부를 나누어 pivot과의 대소관계에 따라 정렬하는 partition / 전체가 정렬될 수 있도록 배열 자체를 분할하하여 분할범위마다 quickSort
  이 두 역할이 다 필요함에 유의

사진출처

코드 구현

🔽 배열을 나누는 부분 먼저 구현

// 배열을 나눈다.
public class Partition {

    // 배열 요소값을 서로 바꾼다.
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 배열을 나눈다.
    static void partition(int[] a, int n) {
        int pl = 0; // 왼쪽커서
        int pr = n-1; // 오른쪽커서
        int x = a[n/2]; // 피벗, 가운데 값

        do {
            while (a[pl] < x) pl++; // pl에 있어서 pivot보다 작은 값은 고려 대상이 아니다.
            while (a[pr] > x) pr--; // pr에 있어서 pivot보다 큰 값은 고려 대상이 아니다.
            if (pl <= pr)
                swap(a, pl++, pr--); // 1회전 : 스왑이 필요한 pl과 pr에서 멈추고 (while문)
                                    //         if문에서 swap하되, 교차를 예방해서 pl이 pr보다 작거나 같을때로 조건한다.
        } while (pl <= pr);
    }


}

🔽 QuickSort.java

public class QuickSort {

    static void swap (int[]a, int idx1, int idx2) {
        int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
    }

    static void quickSort(int[]a, int left, int right) {
        int pl = left;
        int pr = right;
        int x = a[(pl+pr)/2];

        // 퀵정렬 분할 과정 출력해보기 (확인용)
        System.out.printf("a[%d]~a[%d] : { ", left, right);
        for (int i = left; i < right ; i++) {
            System.out.printf("%d, ", a[i]);
        }
        System.out.printf("%d}\n",a[right]);

        do {
            while (a[pl] < x) pl++;
            while (a[pr] > x) pr--;
            if (pl <= pr)
                swap(a, pl++, pr--);
        } while ( pl <= pr );

	// 배열 분할 조건, 분할 배열마다 정렬적용
    // 가운데 그룹은 나눌 필요 없다. (= 이 없는이유)
    // `left < pr` `pl < right` 의 의미는 요소의 개수가 2개 이상인 그룹만이 나누기 위한 조건
        if (left < pr) quickSort(a,left,pr); 
        if (pl < right) quickSort(a,pl,right);

    }

}

참고

• Libre
• https://en.wikipedia.org/wiki/Quicksort
• 도서 [ Doit 자료구조와 함께 배우는 알고리즘 입문 ]