[자료구조] Quick Sort 개념 및 Java로 구현하기

퀵 정렬 (Quick Sort)

:분할 정복 (Divide and Conquer)방식을 이용한 알고리즘.

---

pivot point 라는 기준점을 설정하여 왼쪽은 이 값보다 작은 값, 큰 값은 오른쪽으로 옮기면서 정렬을 진행,

따라서, 분할과 동시에 정렬을 진행하는 알고리즘이다.

보통 pivot을 맨 앞이나 맨 뒤, 혹은 중간에 위치한 값을 선택거나

전체 배열 값 중 중간값, 랜덤값으로 설정한다.

 

각 정렬은 배열의 크기 N만큼 비교하고, 이를 총 분할 깊이인 logN 만큼 실행한다.

즉, O(NlogN)의 시간 복잡도를 가진다.

이미 배열이 정렬이 되어 있는 경우(pivot이 항상 그 배열의 최솟값 혹은 최대값인 경우)는

최악의 시간 복잡도를 나타낸다.

`(unbalanced-partition)` 이 경우에는, 분할이 N만큼 진행되게 된다.(한 쪽에 쏠리니까?)

따라서 시간 복잡도는 O(N^2)가 된다.

-> 이를 방지하기 위해서 pivot point를 전체 배열 값 중 중간 값이나 랜덤 값으로 설정하는 방법을 쓴다.

 

퀵 정렬은 최악의 경우에는 O(N^2)로 얼핏 비효율적이여 보일 수 있지만, 그 경우는 드문 경우이며 일반적으로 합병 정렬보다 20%이상 빠르다고 한다.

---

구현 코드

import java.util.*;

public class Solv {

	public static int partition(int[] arr, int left, int right) {

		int pivot = (left + right) / 2;
		
		// 작은 거는 pivot의 왼쪽, 큰 거는 오른쪽
		while (left < right) {
			while (left <= right && arr[left] <= arr[pivot])
				++left;
			while (left <= right && arr[right] > arr[pivot])
				--right;

			if (left <= right) {
				int temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
				// 오른쪽 검사가 다 끝난 경우는 right=pivot
				// right은 arr[pivot]과 같은 값도 멈추기 때문
				if (right == pivot) {
					// left 와 pivot을 swap 한 경우이므로
					// 기준 점을 left로 수정
					return left;
				}
			}
		}
		// left는 검사가 끝났는데, right는 안 끝난 경우
		// pivot의 기준점을 right으로 바꾸기
		if (right != pivot) {
			int temp = arr[right];
			arr[right] = arr[pivot];
			arr[pivot] = temp;
		}
		return right;

	}

	public static void quickSort(int[] ori, int left, int right) {

		if (left < right) {
			
			int newPivot = partition(ori, left, right);
			// 기준의 왼쪽 배열들
			quickSort(ori, left, newPivot - 1);
			// 기준의 오른쪽 값들
			quickSort(ori, newPivot + 1, right);
			
		}
	}
	
	// 정렬 실행해보기
	public static void main(String[] args) {

		int[] a = { 1, 3, 56, 8, 9, 3, 2, 1, 23, 11, 10 };
		quickSort(a, 0, a.length - 1);
		System.out.println(Arrays.toString(a));

	}
}