퀵정렬 (Quick Sort)

퀵정렬은 분할 정복 기법과 재귀를 사용한 정렬 알고리즘으로, 이름에서도 나와 있듯 평균적으로 매우 빠른 정렬속도를 보여주는 알고리즘입니다.

퀵정렬은 빠른 속도를 장점으로 다음과 같이 기본적인 정렬 알고리즘에서 많이 사용되고 있습니다.

• C++의 Algorithm STL의 sort() 함수
• 자바의 Arrays.sort()
• 파이썬의 list.sort()

특징

• 매우 빠르다
  • 퀵정렬은 정렬 알고리즘으로 많이 사용하는 병합정렬, 힙 정렬과 비교해서도 이상적인 환경에서 평균적으로 매우 빠른 속도를 보여줍니다.
  • 하지만 최악의 경우 (분할이 계속 불균등하게 이루어질 경우) O(N^2)라는 느린 속도를 보입니다.
• 분할 정복 기법 (Divide and Conquer)
  • 분할 정복은 하나의 문제를 여러개의 작은 문제로 단순화 하여 해결한 후, 이를 다시 합쳐 문제를 해결하는 기법입니다.
• 불안정 정렬 (Unstable Sort)
  • 불안정 정렬은 같은 우선순위를 가진 데이터에 대하여 입력된 순서를 유지하지 않는 정렬을 의미합니다.

동작 방식

1. 분할

먼저 하나의 기준을 정하고, 기준 양 옆으로 기준보다 작은수와 큰 수로 나누어 2등분 합니다.

• step1 : pivot의 위치를 선정합니다. 다음, low는 pivot보다 큰 숫자가 나올 때까지 오른쪽으로 이동하고, high는 pivot보다 작은 숫자가 나올 때까지 왼쪽으로 이동합니다

• step2 : low와 high pointer가 멈추면 서로 교환하고, low와 high pointer를 다시 이동시킵니다

• step3 : low와 high가 엇갈릴 때까지 같은 조건으로 low와 high pointer를 이동시킵니다

• step4 : low와 high가 엇갈리면, pointer의 이동을 멈추고 pivot과 high를 교환합니다

• step5 : step 4 이후 pivot을 기준으로 왼쪽에는 작은 숫자들, 오른쪽에는 큰 숫자들이 위치하며 나눠집니다

위 스텝을 진행했을 때 pivot을 기준으로 왼쪽은 작은 수, 오른쪽은 큰 수로 나누어지며 pivot은 왼쪽보다는 크지만 오른쪽보다는 작은 값 이므로 위치가 고정이 됩니다.

2. 정복

분할 과정을 1회 진행하면 하나의 고정된 값과 양쪽으로 두 개의 값 집합이 나타납니다. 이제 각각의 집합에 대하여 분할 과정을 다시 재귀적으로 시행하며, 최종적으로 집합의 크기가 1일 될때까지 반복 시행합니다.

분할 과정을 진행하여 집합의 크기가 1이되면, 각각의 집합들은 pivot이 되며, 이는 정렬된 위치를 가지게 됩니다. 따라서 이들을 다시 합치므로써 정렬이 완료됩니다.

구현

package sort;

public class QuickSort {
	
	public static void sort(int[] arr) {
		quickSort(arr, 0, arr.length - 1);
	}
	
	/**
	 * @param arr	정렬할 배열
	 * @param low	현재 부분배열의 왼쪽
	 * @param high	현재 부분배열의 오른쪽
	 */
	private static void quickSort(int[] arr, int low, int high) {
		
		/*
		 *  low가 high보다 크거나 같다면 정렬 할 원소가 
		 *  1개 이하이므로 정렬하지 않고 return한다.
		 */
		if(low >= high) {
			return;
		}
		
		/*
		 * 피벗을 기준으로 요소들이 왼쪽과 오른쪽으로 약하게 정렬 된 상태로
		 * 만들어 준 뒤, 최종적으로 pivot의 위치를 얻는다.
		 * 
		 * 그리고나서 해당 피벗을 기준으로 왼쪽 부분리스트와 오른쪽 부분리스트로 나누어
		 * 분할 정복을 해준다.
		 */
	
		int pivot = partition(arr, low, high);	
		
		quickSort(arr, low, pivot - 1);
		quickSort(arr, pivot + 1, high);
	}
	
	/**
	 * pivot을 기준으로 왼쪽과 오른쪽으로 파티션을 나누기 위한 약한 정렬 메소드
	 * 
	 * @param arr		정렬 할 배열 
	 * @param left	현재 배열의 가장 왼쪽 부분
	 * @param right	현재 배열의 가장 오른쪽 부분
	 * @return		최종적으로 위치한 피벗의 위치(low)를 반환
	 */
	private static int partition(int[] arr, int left, int right) {
		
		int low = left;
		int high = right;
		int pivot = arr[left];		// 부분리스트의 왼쪽 요소를 피벗으로 설정
		
		// low가 high보다 작을 때 까지만 반복한다.
		while(low < high) {
			
			/*
			 * high가 low보다 크면서, low의 요소가 pivot보다 큰 원소를
			 * 찾을 떄 까지 low를 증가시킨다.
			 */
			while(arr[low] <= pivot && low < high) {
				low++;
			}
			
			/*
			 * high가 low보다 크면서, high의 요소가 pivot보다 작거나 같은 원소를
			 * 찾을 떄 까지 high를 감소시킨다.
			 */
			while(arr[high] > pivot && low < high) {
				high--;
			}
			
			// 교환 될 두 요소를 찾았으면 두 요소를 바꾼다.
			swap(arr, low, high);
		}
		
		/*
		 *  마지막으로 pivot의 원소와 
		 *  low가 가리키는 원소를 바꾼다.
		 */
		swap(arr, left, low);
		
		// 두 요소가 교환되었다면 피벗이었던 요소는 low에 위치하므로 low를 반환한다.
		return low;
	}
 
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

참고

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
https://en.wikipedia.org/wiki/File:Sorting_quicksort_anim.gif