[알고리즘] 퀵 정렬 (quick sort)

 1. 퀵 정렬(quick sort) 이란?

기준점 (pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성하는 것이다.

각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위의 작업을 반복한다.

함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)를 리턴한다.

 

2. 퀵정렬 정렬 순서를 알아보자!

3. 자바 구현 코드

package Concept;

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

public class QuickSortCode {
	
	public static void quickSort(int[] arr, int left, int right) { //arr[left ... right]를 정렬한다.
		if (left < right) {
			int q = partition(arr, left, right); // 분할 
			quickSort(arr, 0, q - 1); // 왼쪽 배열 정렬
			quickSort(arr, q + 1, right); //오른쪽 배열 정렬
		}
	}
	
	public static int partition(int[] arr, int left, int right) {
		int pivot = arr[right];
		
		int i = left - 1; //1구역 마지막 인덱스 (기준보다 작은 값의 배열)
		
		for (int j = left; j < right; j++) { // j는 2구역 시작 지점(기준보다 큰 값의 배열)
			if (pivot > arr[j]) {
				int temp = arr[++i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		
		arr[right] = arr[i + 1]; //pivot을 제자리로
		arr[i + 1] = pivot;
		
		return i + 1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		int[] arr = new int[num];
		
		for (int i = 0; i < num; i++) {
			arr[i] = sc.nextInt();
		}
		
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}
}

4. 시간복잡도

분할은 배열을 왼쪽부터 오른쪽까지 한번 훑어야하므로 O(n)의 시간이 든다.

퀵정렬에서 가장 이상적인 경우는 분할이 반반씩 균등될 때인데, 이때 시간은 O(nlogn)이 된다.

단, 최악의 경우 맨 처음 pivot의 값이 가장 크거나, 가장 작다면 모든 데이터를 비교하기 때문에 O(n^2)이 된다.

 

퀵정렬의 수행시간은 분할이 얼마나 균형잡히게 잘 되어있느냐에 달려있다.