[Data Structure] 퀵 정렬 - Quick Sort

퀵 정렬 (Quick Sort)

Unstable Sort

• 분할 정복(Divide and Conquer) 알고리즘
• 다른 원소들과의 비교만으로 정렬 수행
• Merge Sort와 다르게, Quick Sort는 비균등하게 분할
• 평균적으로 매우 빠른 수행 속도

> C에서는 라이브러리 함수로 qsort가 주어진다

> Java의 Arrays.sort는 quick sort로 구현되어있다

 

시간복잡도

- 최선/평균 : O(n log n) 

- 최악 : O(n²) 

 

장점

- 속도가 빠르다

- O(n log n)을 가지는 다른 정렬 알고리즘과 비교해도 가장 빠르다

- 추가 메모리 공간이 필요없다

 

단점

- 정렬된 리스트에 대해 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다

• pivot을 선택할 때 리스트를 균등하게 분할할 수 있는 요소를 선택 (크기순으로 중간 값)

 

과정

1. 리스트 안에 있는 하나의 요소(피벗 pivot) 선택
2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽, pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮기기
3. pivot을 제외한 양쪽의 부분 리스트를 다시 정렬 (순환 호출) → 양쪽의 부분 리스트들도 각자 pivot을 정해서 (2) 반복
4. 부분 리스트 크기가 0 or 1이 될 때까지 반복

 

 

※ Example

5(pivot)	3	8	4	9	1	6	2	7
low								high

- 맨 왼쪽을 pivot으로 선택 / low = 0, high = 리스트.length - 1

- low < high를 전제로

• → low : pivot보다 작은 값이면 low++
• → high : pivot보다 큰 값이면 high--

 

5(pivot)	3	8	4	9	1	6	2	7
		low					high

• 8은 5보다 크기 때문에 low 정지 / 2는 5보다 작기 때문에 high 정지
• low 값, high 값 swap

 

5(pivot)	3	2	4	9	1	6	8	7
				low	high

• 9, 1 swap

 

5(pivot)	3	2	4	1	9	6	8	7
				low high

• low < high의 전제가 깨졌기 때문에 stop
• pivot과 low의 값 swap

 

1	3	2	4	5(pivot)	9	6	8	7
				low high

• pivot을 기준으로 2개의 부분리스트 {1, 3, 2, 4}, {9, 6, 8, 7} 생성
• 2개의 부분 리스트에 대해서 똑같이 pivot을 기준으로 값 swap

 

 

▶ Quick Sort Code

static void quick_sort(int[] list, int left, int right) {
        if(left >= right) return;
        int pivot = partition(list, left, right); // pivot의 위치 알아내기
        quick_sort(list, left, pivot-1); // 처음 ~ pivot전까지 부분 리스트1
        quick_sort(list, pivot+1, right); // pivot다음 ~ 끝까지 부분 리스트2
    }

    static int partition(int[] list, int left, int right) {
        // 선택한 pivot 최종 위치 return
        int pivot = list[left]; // 왼쪽 요소를 pivot으로 선택
        int low = left; // pivot보다 작은 요소 찾기
        int high = right; // pivot보다 큰 요소 찾기

        while(low<high){
            while(pivot < list[high] && low<high)
                high--; // pivot보다 high쪽 값이 더 크면 high--
            while(pivot >= list[low] && low<high)
                low++; // pivot보다 low쪽 값이 더 작으면 low++
            swap(list, low, high);
            /*
            high = pivot보다 작은 값
            low = pivot보다 큰 값
            high와 low를 서로 swap
             */
        }
        swap(list, left, low);
        /*
        low는 최종적인 pivot의 위치니까 pivot의 값을 low쪽의 값과 swap
         */


        return low;
    }

    static void swap(int [] list, int a, int b){
        int tmp = list[a];
        list[a] = list[b];
        list[b] = tmp;
    }

 

 

▶ Full Code

package Sort;

import java.util.Calendar;

public class Quick_Sort_7 {
    public static void main(String[] args) {
        int[] A = {5, 3, 8, 4, 9, 1, 6, 2, 7}; // 정렬할 배열 A

        // 정렬 전 A 출력
        System.out.print("A []");
        for (int i = 0; i < A.length; i++) {
            if (i % 20 == 0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println();

        Calendar before = Calendar.getInstance();
        quick_sort(A, 0, A.length-1);
        Calendar after = Calendar.getInstance();

        // 정렬 후 최종 result 배열 출력
        System.out.print("\nresult []");
        for(int i=0; i<A.length; i++){
            if(i%20==0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println("\n");

        int time = after.get(Calendar.MILLISECOND) - before.get(Calendar.MILLISECOND);
        System.out.println("걸린 시간 : " + time + "ms");
    }

    static void quick_sort(int[] list, int left, int right) {
        if(left >= right) return;
        int pivot = partition(list, left, right); // pivot의 위치 알아내기
        quick_sort(list, left, pivot-1); // 처음 ~ pivot전까지 부분 리스트1
        quick_sort(list, pivot+1, right); // pivot다음 ~ 끝까지 부분 리스트2
    }

    static int partition(int[] list, int left, int right) {
        // 선택한 pivot 최종 위치 return
        int pivot = list[left]; // 왼쪽 요소를 pivot으로 선택
        int low = left; // pivot보다 작은 요소 찾기
        int high = right; // pivot보다 큰 요소 찾기

        while(low<high){
            while(pivot < list[high] && low<high)
                high--; // pivot보다 high쪽 값이 더 크면 high--
            while(pivot >= list[low] && low<high)
                low++; // pivot보다 low쪽 값이 더 작으면 low++
            swap(list, low, high);
            /*
            high = pivot보다 작은 값
            low = pivot보다 큰 값
            high와 low를 서로 swap
             */
        }
        swap(list, left, low);
        /*
        low는 최종적인 pivot의 위치니까 pivot의 값을 low쪽의 값과 swap
         */

        System.out.println("-> pivot : " + pivot);
        for(int i=0; i<list.length; i++){
            if(i%20==0) System.out.println();
            System.out.print(list[i] + "\t");
        }
        System.out.println();

        return low;
    }

    static void swap(int [] list, int a, int b){
        int tmp = list[a];
        list[a] = list[b];
        list[b] = tmp;
    }
}