01. 요약

  • 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법입니다.
  • 불안전 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
  • 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법이다.
  • 합병 정렬과는 달리 리스트를 비균등하게 분할한다.
  • 포인트는 퀵 정렬 단계와 partition 함수

02. 원리 (작동 방식)

퀵 정렬 원리

  • 퀵 정렬의 각 단계
    1. 분할 (Divide) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 (피벗을 중심으로 “왼쪽은 피벗보다 작은 요소”, “오른쪽은 피벗보다 큰 요소”)로 분할한다.
    2. 정복 (Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 기법을 적용한다.
    3. 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
      • 순환 호출이 한 번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적인 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

partition 함수 동작 과정

  • partition 함수
    • 간단한 구현을 위해 피벗을 리스트의 첫 번째 데이터로 하자, 이 경우 피벗은 5이다.
    • 2개의 인덱스 변수 low와 high를 이용한다. (low는 왼쪽 부분 리스트를 만드는 데 사용 / high는 오른쪽 부분 리스트를 만드는 데 사용)
    • low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터를 찾으면 멈춘다.
    • high는 오른쪽에서 왼쪽으로 탐색해가다가 피벗보다 작은 데이터를 찾으면 멈춘다.
    • low와 high가 가리키는 두 데이터를 서로 교환한다. (이러한 탐색-교환 과정은 low와 high가 엇갈릴 때까지 반복한다.)
    • low와 high가 엇갈리게 되면 high가 가리키는 값과 pivot의 값을 서로 교환한다.
    • 이러면 pivot을 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값이 있게 된다.

03. 순서도 (알고리즘)

// partition 함수
const partition = (array, left, right) => {
	// 간단한 구현을 위해 피벗을 리스트의 첫 번째 데이터로
	let pivot = array[left]; // pivot에는 실제 값, low와 high에는 index 값

	// left 와 right 는 기준값으로 써야하기 때문에 low 와 high 변수를 별도로 생성하는 것
	let [low, high] = [left, right + 1]; // do-while이라서 +1 진행

	do {
		do {
			low++;
		} while (low <= right && array[low] < pivot); // pivot 보다 큰 수가 있으면 멈춤

		do {
			high--;
		} while (high >= left && array[high] > pivot); // pivot 보다 작은 수가 있으면 멈춤

		if (low < high) {
			// low와 high가 엇갈리지 않았다면 SWAP!!
			[array[low], array[high]] = [array[high], array[low]];
		}
	} while (low < high); // low와 high가 엇갈리면 종료

	// low와 high가 엇갈렸으므로 high와 pivot을 SWAP!!
	[array[high], array[left]] = [array[left], array[high]];

	return high; // pivot의 index 리턴
};

// QuickSort 함수
const QuickSort = (array, left, right) => {
	if (left < right) {
		// 하나가 아닌 둘 이상일때
		const pivotIdx = partition(array, left, right);

		QuickSort(array, left, pivotIdx - 1); // pivot 기준 작은 값들로 정렬된 왼쪽 리스트
		QuickSort(array, pivotIdx + 1, right); // pivot 기준 큰 값들로 정렬된 오른쪽 리스트
	}
};

const array = [5, 3, 8, 4, 9, 1, 6, 2, 7];

// 배열의 시작 인덱스와 끝 인덱스를 넣어준다.
QuickSort(array, 0, 8);
console.log(array);
  • partition 함수와 QuickSort 함수를 구현합니다.
  • partition 함수는 왼쪽 끝(low)과 오른쪽 끝(high)에서 오면서 pivot 기준 그 위치에 있으면 안되는 값을 서로 교환해가며 엇갈릴 때 까지 반복합니다. 엇갈리면 pivot값과 high 값을 교환해주고, high 값을 리턴합니다.
  • QuickSort 함수는 배열의 크기가 2 이상이라면 partition함수를 호출해 pivot 값을 얻어서 다시 pivot 값 기준 왼쪽과 오른쪽을 QuickSort 함수를 호출합니다.

04. 특징

  • 장점
    • 속도가 빠르다. (같은 O(nlogn)인 정렬 알고리즘과 비교했을 때도 가장 빠르다.)
      • 불필요한 데이터 이동은 줄이고, 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗은 추후 연산에서 제외되는 특성 때문
    • 추가 메모리 공간을 필요로 하지 않는다. (퀵 정렬은 O(logn)만큼 메모리를 필요로 한다.)
  • 단점
    • 정렬된 리스트에 오히려 수행시간이 더 많이 걸린다. (이는 불균형 분할이 발생하기 때문)
  • 불균형 분할을 방지하기 위해 피벗을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 것이 아닌 보다 리스트의 중앙 부분을 분할할 수 있는 데이터를 선택한다.
    • ex) 리스트 내의 몇 개의 데이터 중에서 크기 순으로 중간 값을 피벗으로 선택한다.

05. 복잡도

  • 시간 복잡도
    • 최선의 경우
      • 비교 연산은 순환 호출의 깊이(logn) * 각 순환 단계의 비교 연산의 수(n) ⇒ nlogn
      • 이동 연산은 비교 연산보다 적어서 무시할 수 있다.
    • 최악의 경우 (리스트가 계속 불균형 분할되는 경우, 이미 정렬된 리스트인 경우)
      • 비교 연산은 순환 호출의 깊이(n) * 각 순환 단계의 비교 연산의 수(n) ⇒ n^2
      • 이동 연산은 비교 연산보다 적어서 무시할 수 있다.
    • 평균
      • O(nlogn)

06. 시간 복잡도 더 자세히 알아보기!

최선의 경우 시간복잡도

  • 최선의 경우 (균형 분할)
    • 순환 호출의 깊이
      • 레코드의 개수 n이 2의 거듭제곱이라고 가정 (n = 2^k) 했을 때, n = 2^3인 경우
      • 2^3 ⇒ 2^2 ⇒ 2^1 ⇒ 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.
      • 이것을 일반화 하면 n = 2^k인 경우, 깊이가 k(logn)임을 알 수 있다.
    • 각 순환 호출 단계의 비교 연산
      • 각 순환 호출에서 전체 리스트의 대부분의 레코드를 비교해야 하므로, 평균 n번 정도의 비교가 이루어진다.
    • 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 ⇒ nlogn
    • 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.
    • T(n) = O(nlogn)

최악의 경우 시간복잡도

  • 최악의 경우 (불균형 분할, 이미 정렬된 리스트)
    • 순환 호출의 깊이
      • 레코드의 개수 n이 2의 거듭제곱이라고 가정 (n = 2^k) 했을 때, 순환 호출의 깊이는 n이다.
    • 각 순환 호출 단계의 비교 연산
      • 각 순환 호출에서 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
    • 비교 횟수 = 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 ⇒ n^2
    • 이동 횟수
      • 비교 횟수보다 적으므로 무시할 수 있다.
    • T(n) = O(n^2)
  • 평균의 경우
    • T(n) = O(nlogn)

07. 참고