[자료구조] 퀵 정렬(Quick Sort) with JAVA

[자료구조] 퀵 정렬 with JAVA

 

 

* 퀵 정렬이란?

 - 퀵 정렬(Quick Sort)은 정렬할 전체 값들을 정렬을 수행하지 않고 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.

 - 왼쪽 부분 집합에는 기준값보다 작은 원소들을, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동.

 - 이 때 사용하는 기준값 = Pivot(피봇) 이라고 칭한다.

 

*퀵 정렬의 핵심

 1) 분할 : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할한다.

 2) 정복 : 기준보다 작은 값은 왼쪽, 기준보다 큰 값은 오른쪽 부분집합으로 정렬, 부분집합의 크기가 1 이하가 아니면 순환 호출을 이용해 다시 분할.

 

*퀵 정렬 방법 

Pivot을 중심으로 L 과 R 값을 지정해준다. L은 Pivot보다 큰 값, R은 Pivot보다 작은 값을 지정한다. 두 개 모두 선택됐다면 자리교환을 해주면 된다.

만약 한쪽이 선택된 L이나 R이 없다면 선택된 값과 Pivot을 교환하도록 한다.

 

* 퀵 정렬의 시간 복잡도

퀵 정렬 알고리즘에서 실행 성능은 Pivot에 의해 결정된다. 성능이 가장 좋은 경우는 정확히 n/2로 나뉘었을 때 이다. 이 때, 최소이기 때문이다. 반대로 n, n-1개로 나뉠 경우 한 쪽으로 치우쳐 수행 단계가 최대로 올라갈 경우 실행 성능이 최저로 떨어진다. 평균 시간 복잡도는 아래와 같다.

 

덧붙이자면, 다른 정렬 방법에 비해 뛰어난 실행 시간 성능을 갖고 있다.  

 

 

[참조] c언어로 배우는 쉬운 자료구조, 한빛미디어, 이지영 저

 

*퀵 정렬 코드

 

public class QuickSort {
    static int partition(int[] array,int start, int end) {
        int pivot = array[(start+end)/2];
        while(start<=end) {
            while(array[start]<pivot) start++;
            while(array[end]>pivot) end--;
            if(start<=end) {
                int tmp = array[start];
                array[start]=array[end];
                array[end]=tmp;
                start++;
                end--;
            }
        }
        return start;
    }
    static int[] quickSort(int[] array,int start, int end) {
        int p = partition(array, start, end);
        if(start<p-1)
            quickSort(array,start,p-1);
        if(p<end)
            quickSort(array,p,end);
        return array;
    }
    public static void main(String[] args) {
        int[] array = {4,2,3,5,9};
        array = quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}