[정렬] 퀵 정렬 (Quick Sort) - 개념, 시간복잡도, 구현

퀵 정렬 개념

원소(pivot(기둥/중심))를 하나 정하여, 해당 원소보다 작은 수들과 큰 수들로 나눈다.

1. pivot의 위치는 확정된 것

2. pivot의 왼쪽과 오른쪽의 자리는 바뀌지 않는다. (= 왼쪽과 오른쪽을 따로 정렬해도 된다.)

퀵 정렬의 시간복잡도

재귀적으로 구해야 한다.

1. pivot을 정한다. = O(1)

2. 작거나 같은 값과 큰 값을 분류한다. = O(n)

3. 각각을 퀵정렬 한다. 

* T(n) = n개의 숫자를 퀵 정렬로 정렬하는데 걸리는 시간

* T(n) = T(left) + T(right) + O(n)  // 점화식

  // left = pivot보다 작거나 같은 원소의 개수

  // right = pivot보다 큰 원소의 개수

* pivot이 원소의 개수를 절반으로 나눈다고 가정하자

* T(n) = 2T(n/2) + O(n) => 합병 정렬과 같음

* 퀵 정렬은 평균적으로 걸린다고 말함

* 퀵 정렬은 최악의 경우에는 이 걸림

  (pivot을 어떤 식으로 결정하느냐에 따라 시간복잡도가 달라짐)

 

퀵 정렬 구현 코드

import java.util.Scanner;

public class SortQuick {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] data = new int [100];
		
		for(int i=0; i<n; i++){ // 데이터 입력
			data[i] = sc.nextInt();
		}		
		quickSort(data, 0, n-1); // 퀵 정렬
		for(int i=0; i<n; i++){ // 데이터 출력
			System.out.print(data[i]+" ");
		}
	}
	
	// data[]를 start부터 end까지 퀵 정렬하는 함수
	private static void quickSort(int[] data, int start, int end) {
		if(start >= end) // 기저조건 => 숫자가 하나밖에 남아 있지 않은 경우
			return;
		
		int pivot = data[start]; // 데이터의 맨 앞의 숫자
		int[] left = new int[100];
		int[] right = new int[100];
		
		// pivot 다음 숫자(start+1) ~ 끝까지(end) 중 pivot보다 같거나 작은 값
		int leftCnt = getLeft(data, start+1, end, pivot, left); // left 값 개수 반환받음
		// pivot 다음 숫자(start+1) ~ 끝까지(end) 중 pivot보다 큰 값
		int rightCnt = getRight(data, start+1, end, pivot, right);  // right 값 개수 반환받음
		
		for(int i=0; i<leftCnt; i++){ // 정렬된 왼쪽 값 삽입
			data[start+i] = left[i];
		}
		data[start+leftCnt] = pivot; // pivot 삽입
		for(int i=0; i<rightCnt; i++){ // 정렬된 오른쪽 값 삽입
			data[start+leftCnt+1+i] = right[i];
		}
		
		quickSort(data, start, start+leftCnt-1); // 왼쪽 퀵 정렬
		quickSort(data, start+leftCnt+1, end); // 오른쪽 퀵 정렬
	}
	
	// data[]의 start부터 end까지 숫자들 중에서 
	// pivot보다 작거나 같은 값을 result[]에 채우고 개수 반환하는 함수
	private static int getLeft(int[] data, int start, int end, int pivot, int[] result) {
		int index = 0;
		for(int i=start; i<=end; i++){
			if(data[i] <= pivot){
				result[index++] = data[i];
			}
		}
		return index;
	}
	
	// data[]의 start부터 end까지 숫자들 중에서
	// pivot보다 큰 값을 result[]에 채우고 개수 반환하는 함수
	private static int getRight(int[] data, int start, int end, int pivot, int[] result) {
		int index = 0;
		for(int i=start; i<=end; i++){
			if(data[i] > pivot){
				result[index++] = data[i];
			}
		}		
		return index;
	}
}