[12] 심화 정렬 ( SORT ) - Quick Sort

분할 정복법(divide and conquer) : Merge Sort, Quick Sort

분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

정복 : 각각의 작은 문제를 순환적으로해결

 

 

Merge Sort 는 그냥 배열을 반씩 쪼개는데 반해, Quick Sort 는 Pivot 을 기준으로 사용해서 분할함.

 

 

Pivot 을 가장 오른쪽 수 기준으로 한 퀵소트 예시

 

 

아래의 코드는 Pivot 을 배열의 가운데 수로 정했을 때 퀵소트 예시

import java.util.Scanner;

// Quick Sort

public class sort_2 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();

		int[] arr = new int[n];

		for (int i = 0; i < n; i++) arr[i] = scanner.nextInt();
		
		arr =quickSort(arr, 0, n-1);
		
		for(int i=0;i<n;i++) System.out.println(arr[i]);
	}
	
	static int[] swap(int[] arr, int start, int end) {
		int temp =0;
		
		temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;
		return arr;
 	}
	
	static int partition(int[] array, int start, int end) {
		int pivot = array[(start + end) / 2]; // pivot을 가운데 값으로 설정
		while (start <= end) {
			while (array[start] < pivot) start++; // pivot 의 왼쪽에서는 pivot 보다 큰 값을 찾음
			while (array[end] > pivot) end--; // pivot 의 오른쪽에서는 pivot 보다 작은 값을 찾음
			if (start <= end) { 
				array = swap(array,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;
	}

}

 시간 복잡도

 

Worst : O($n^2$)

Best : O($nlogn$)

Average : O($nlogn$)