퀵 정렬

 

퀵 정렬(Quick Sort)

 

버블 정렬, 선택 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지기 때문에 데이터의 개수가 많을수록 사용하기 힘든 알고리즘입니다. 더욱 빠른 정렬 알고리즘이 필요한데 그중 하나인 퀵 정렬입니다.

퀵 정렬은 말 그대로 엄청나게 빠른 정렬 기법입니다. 이 퀵 정렬은 분할 정복(Divide and Conquer)에 근거하며,

퀵 정렬은 다른 정렬과는 달리 기준값을 하나 택하고 순회를 돌면서 기준값보다 작은 데이터는 좌측에, 기준값보다 큰 데이터는 우측으로 분할하고 다시 퀵 정렬을 적용합니다.

 

이러한 기준값을 피벗(Pivot)이라고도 하는데 보통  첫 번째 원소를 피벗 값으로 설정하고 사용합니다.

 

 

위 그림에서의 과정을 글로 나타내면 아래와 같습니다.

 

 5를 기준값으로 선택하여 그보다 작은 값은 왼쪽으로 큰 값들은 오른쪽으로 정렬한다.

 

맨 처음에 기준값을 택하고 작은 값은 좌측에 큰 값은 우측에 배치함으로써 작은 값과 큰 값으로 분할하고 분할된 두 영역이 A, B라고 한다면 A 영역에서 분할할 수 없을 때까지 기준값을 택하고 분할되며 B 영역도 마찬가지로 B 영역에서 분할할 수 없을 때까지 기준값을 택하고 분할되는 과정을 반복합니다. 이러한 퀵 정렬의 평균 복잡도는 아래와 같습니다.

퀵 정렬의 평균 복잡도:

최악의 경우 퀵 정렬의 복잡도:

퀵 정렬은 보통 재귀 함수를 이용하여 구현합니다.

 

import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {
	

	public static void main(String[] args) {
		
		System.out.println("퀵정렬");
		
		Scanner scan = new Scanner(System.in);
		String value = scan.nextLine();
		
		
		String[] arr = value.split(" ");
		int[] array = new int[arr.length];
		
		for(int i = 0; i < arr.length; i++) {
			
			array[i] = Integer.parseInt(arr[i]);
			
		}
		
		
		long startTime = System.nanoTime();
		quickSort(0,array.length-1,array);
		long endTime = System.nanoTime();
		
		System.out.println(endTime - startTime);
		System.out.println(Arrays.toString(array));
	}
	
	public static void quickSort(int start,int end,int[] data) {
		//start는 정렬을 수행하는 첫번째 부분집합
		//end는 정렬을 수행하는 두번째 부분집합
		
		if(start >= end) {
			//원소가 한개인경우
			return;
		}
		int key = start; //키는 첫번째 원소
		int i = start + 1; //왼쪽부터 하나씩 키값보가 큰값을 찾을때 그 인덱스
		int j = end; //오른쪽 부터 하나씩 키값보다 작은값을 찾을때 그 인덱스
		int temp;
		
		while(j >= i) {
				//엇갈릴 때 까지 반복하며 엇갈린다면 왼쪽의 요소를 피벗값과 변경한다.
			while(i <= end && data[i] <= data[key]) { //피벗값보다 큰값을 찾는다.
				i++;
			}
			while(data[j] >= data[key] && j > start ) {//피벗값보다 작은값을 찾는다.
				j--;
			}
			
			if(j < i) { //엇갈렸다면
				temp = data[j]; 
				data[j] = data[key];
				data[key] = temp;
			}else {
				temp = data[j];
				data[j] = data[i];
				data[i] = temp;
			}
		}
		//j는 현재 인덱스 
		//start는 정렬된 배열의 첫번째 요소값
		quickSort(start, j-1,data);
		quickSort(j+1,end,data);
	}

}

 

퀵정렬에도 치명적인 단점이 존재합니다. 이미 정렬이 되어 있는 경우에는 분할 정복의 이점을 사용하지 못하기 때문에 n^2의 시간 복잡도를 나타냅니다.