[자료구조/Java] 퀵 정렬(Quick Sort)

 

youtu.be/7BDzle2n47c

 

시간 복잡도

한 값을 기준으로(pivot) 왼쪽은 그보다 작은 것, 오른 쪽은 그보다 큰 것으로 정렬한다.

시간 복잡도는 평균적으로는 O(nlogn), 최악의 경우 O(n^2)이다.

O(nlogn)

   - 배열이 1개가 될 때까지 계속 나눈다. (n번)

   - 나눌 때마다 데이터가 절반씩 줄어든다. (logn)

O(n^2)

   - 정한 pivot이 맨 끝의 값만 선택할 경우이다.

 

코드 설명

pivot을 기준으로 start point인 s, end point인 e를 정한다.

변수 s

   - pivot보다 작을 경우 hold

   - pivot보다 클 경우, e가 pivot보다 작을 경우 swap

   - pivot보다 클 경우, e가 pivot보다 클 경우 e의 위치를 하나 앞으로 당긴다. (e가 pivot보다 작은게 있을 때까지 반복)

이 과정은 s가 e보다 커질 때까지 반복한다.

 

코드

public class Test{
	privae static void quickSort(int[] arr){
    	quickSort(arr, 0, arr.length-1);
    }
    private static void quickSort(int[] arr, int start, int end){
    	//오른쪽 파티션의 시작점
        int part2 = partition(arr,start,end);
        //시작점이 오른쪽 시작점보다 둘 이상 차이가 날 때만
        //왼쪽 파티션 퀵소트
        if(start < part2 -1){
        	quickSort(arr, start, part2-1);
        }
        //오른쪽 시작점이 끝점보다 작을 때
        //오른쪽 파티션 퀵소트
        if(part2<end){
        	quickSort(arr, part2, end);
        }
    }
    private static int partition(int[] arr, int start, int end){
    	int pivot = arr[(start+end)/2];
        while(start <= end){
        	while(arr[start] < pivot)
         		start++;
        	while(arr[end] > pivot)
         		end--;
         	if(start <= end){
            	swap(arr, start, end);
                start++;
                end--;
            }
        }
        return start;
    }
    private static void swap(int[] arr, int start, int end){
    	int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    private static void printArray(int[] arr){
    	for(int data : arr){
        	System.out.print(data + ", ");
        }
        System.out.println();
    }
    public static void main(String[] args){
    	int[] arr = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
        printArray(arr);
        quickSort(arr);
        printArray(arr);
    }
}