퀵 정렬

 

 퀵정렬은 병합 정렬처럼 분할 정복 알고리즘에 속하지만 병합 정렬과는 달리 불안정 정렬이다. 배열에 있는 값중 아무거나 하나를 pivot으로 정한다. 이를 값을 기준으로 pivot보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 정렬한다.(오름차순 정렬) 이렇게 pivot을 기준으로 왼쪽과 오른쪽으로 분할된 배열로 위의 과정을 반복한다.

 퀵 정렬의 시간 복잡도는 O(nlogn)으로 병합 정렬과 동일하다.

출처 : javaguides

import java.util.Random;

public class Quick {
    public static void quickSort(int[] a,int p,int r) {
        int q;

        if(p<r){
            q = partition(a,p,r); //pivot값 기준으로 정렬
            quickSort(a,p,q-1);//왼쪽 배열 정렬
            quickSort(a,q+1,r);//오른쪽 배열 정렬
        }
    }
    public static int partition(int[] a, int p,int r){
        int i = p-1;//작은 값의 인덱스
        int pivot = a[r];//기준값
        
        for(int j = p;j<r;j++){
            if(a[j]<=pivot){
                i++;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;//pivot보다 작으면 왼쪽으로 swap
            }
        }
        int temp = a[i + 1];
        a[i + 1] = a[r];
        a[r] = temp;//pivot값의 자리를 찾아서 swap
        return i+1;//pivot의 인덱스 return
    }


    public static void main(String[] args) {
        int[] a= {8,31,48,73,3,65,20,29,11,15};
        quickSort(a,0,9);
        
         for(int i:a){
            System.out.printf("%d ",i);
        }
    }
}

위의 소스 코드에서는 pivot값을 배열의 마지막 원소로 지정해주었다. 10000개의 데이터를 실행해본 결과

0초가 나온다. 밀리초로 표현하게해도 0이 나올정도로 매우 빠른 속도를 자랑한다.