퀵 정렬

퀵 정렬(quick sort)

수열을 정렬하는 알고리즘 중 하나. 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 자랑하는 정렬 방법.
시간 복잡도: Worst - O(n²) / Best - O(nlog₂n)

처음 작업 대상은 모든 숫자다.
정렬 기준이 되는 숫자를 하나 선택한다. 이를 피봇(pivot)이라 한다.
피봇은 보통 하나의 숫자를 랜덤으로 선택한 것이다.
여기서는 편의상 가장 오른쪽에 있는 수를 피봇으로 선택한다.
알기 쉽게 피봇에 마커를 표시한다.
계속해서 가장 왼쪽 수에 왼쪽 마커, 오른쪽 수에 오른쪽 마커를 표시한다.
퀵 정렬은 이 마커들을 사용해서 일련의 작업을 재귀적으로 반복하는 알고리즘이다.

왼쪽 마커를 오른쪽으로 이동한다. 왼쪽 마커가 피봇 수 이상인 수에 도착하면 멈춘다.
오른쪽 마커를 왼쪽으로 이동한다. 오른쪽 마커는 피봇보다 작은 숫자에 도달하면 멈춘다.
좌우 마커가 멈춘 시점에 마커의 숫자를 교체한다.
이와 같이 왼쪽 마커의 역할은 피봇 이상인 수를 발견하는 것이고, 오른쪽 마커의 역할은 피봇보다 작은 수를 발견하는 것이다.

숫자를 바꾸므로 수열의 왼쪽에 피봇보다 작은 수, 오른쪽에 피봇 이상인 수를 모을 수 있다.
교체한 후에는 다시 왼쪽 마커를 오른쪽으로 이동한다.
마커들을 이동하는 중 오른쪽 마커가 왼쪽 마커와 만날 때도 동작을 멈춘다.
좌우 마커가 정지했을 때 동일한 위치인 경우 해당 수롤 피봇수와 교체한다.
죄우 마커가 있는 수(6)를 정렬 완료 상태로 둔다.
이로써 첫 작업이 완료된다.

둘로 나누어진 수열에 대해 앞서 했던 작업을 재귀적으로 반복한다.
다음은 왼쪽에 있는 수열([3, 5, 4, 1, 2])을 작업 대상으로 한다.
대상 수열의 수가 하나인 경우에는 정렬이 완료된다.
왼쪽 마커가 오른쪽 마커와 만나도 멈추지 않는다. 오른쪽 마커의 움직임과는 다르다.
이때에는 작업 대상 범위 내에서 피봇인 수가 가장 큰 수가 된다.
다음은 오른쪽 마커를 이동하지만 왼쪽 마커에 추월당한 경우에는 움직이지 않고 종료한다.
이후로는 동일한 작업을 모든 수가 정렬 완료 상태가 될 때까지 반복한다.

장단점

• 장점
  • 속도가 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.
• 단점
  • 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
  • 때문에, 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.

퀵 정렬(quick sort) js 코드

// stable한 Quick Sort
// 별도의 메모리 공간이 필요해 실제로는 잘 사용하지 않는 방법
const quickSort = (arr) => {
	if (arr.length < 2) {
		return arr;
	}
	const pivot = [arr[0]];
	const left = [];
	const right = [];

	for (let i = 1; i < arr.length; i++) {
		if (arr[i] < pivot) {
			left.push(arr[i]);
		} else if (arr[i] > pivot) {
			right.push(arr[i]);
		} else {
			pivot.push(arr[i]);
		}
	}
	return quickSort(left).concat(pivot, quickSort(right));
};

// in-place Quick Sort
// 가운데 요소를 pivot으로 설정하고 가장 왼쪽 요소와 가장 오른쪽 요소가 시작점
// unstable 하지만 메모리 공간이 절약할 수 있어서 대부분 사용하는 방법
const inPlaceQuickSort = (arr, left = 0, right = arr.length - 1) => {
	if (left >= right) {
		return;
	}
	const mid = Math.floor((left + right) / 2);
	const pivot = arr[mid];

	const divide = (arr, left, right, pivot) => {
		while (left <= right) {
			while (arr[left] < pivot) {
				left++;
			}

			while (arr[right] > pivot) {
				right--;
			}

			if (left <= right) {
				let swap = arr[left];
				arr[left] = arr[right];
				arr[right] = swap;
				left++;
				right--;
			}
		}
		return left;
	};

	const partition = divide(arr, left, right, pivot);

	inPlaceQuickSort(arr, left, partition - 1);
	inPlaceQuickSort(arr, partition, right);

	return arr;
};

ref

• gmlwjd9405- [알고리즘] 퀵 정렬(quick sort) 이란
• [JS/Sorting] 퀵 정렬, 자바스크립트로 구현하기(Quick Sort in JavaScript)
• 알고리즘 도감