[Algorithm] 퀵 정렬(Quick Sort) 알고리즘 톺아보기

퀵 정렬 알고리즘 개념

---

퀵 정렬은 분할 정복 알고리즘(문제를 더 작은 2개의 문제로 분리해서 해결한 후 결과를 모아서 원래 문제를 해결하는 방법)의 하나로 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)기사가 개발했다. 가장 자주 사용하는 정렬 알고리즘으로 빠른 수행 속도가 특징이다. 기본적인 퀵 정렬은 아래 3단계를 반복하며 정렬한다.

 

1. 기준(Pivot; 피벗) 요소 선택 — 주로 배열의 중간 요소를 기준으로함
2. 기준 요소보다 작은 요소는 왼쪽으로 이동, 기준 요소보다 큰 요소는 오른쪽으로 이동
3. 이동시킨 왼쪽 / 오른쪽 요소들에 대해 1~2번 작업 반복

 

구현

---

Basic Quick Sort

💡 구현하기 쉽지만 항상 새로운 left / right 배열을 생성해 비교한 요소를 추가하므로 메모리 낭비 심함

Not in place 방식 : 추가 메모리 공간 필요 / 입력값 클수록 메모리 낭비 심함
Stable 방식 : 중복 데이터 순서 안바꿈

 

진행 과정 분석

---

⑴f([85, 24, 63, 45, 17, 31, 96, 50])
=======================================
pivot = 45, arr = [85, 24, 63, 17, 31, 96, 50]
left = [24, 17, 31], right = [85, 63, 96, 50]
concat ⑵f([24, 17, 31]) + 45 + ⑺f([85, 63, 96, 50])
---------------------------------------
return [17, 24, 31, 45, 50, 63, 85, 96]

⑵f([24, 17, 31])
=======================================
pivot = 17, arr = [24, 31]
left = [], right = [24, 31]
concat ⑶[] + 17 + ⑷f([24, 31])
---------------------------------------
return [17, 24, 31]

⑷f([24, 31])
=======================================
pivot = 24, arr = [31]
left = [], right = [31]
concat ⑸[] + 24 + ⑹f([31])
---------------------------------------
return [24, 31]

⑺f([85, 63, 96, 50])
=======================================
pivot = 63, arr = [85, 96, 50]
left = [50], right = [85, 96]
concat ⑻f([50]) + 63 + ⑼f([85, 96])
---------------------------------------
return [50, 63, 85, 96]

⑼f([85, 96]
=======================================
pivot = 85, arr = [96]
left = [], right = [96]
concat ⑽[] + 85 + ⑾f([96])
---------------------------------------
return [85, 96]

 

1. 기준(Pivot; 피벗) 요소 선택
2. 기준 요소보다 작은 요소는 left 배열에 추가, 기준 요소보다 큰 요소는 right 배열에 추가
3. 배열 길이가 1이 될때까지 left, right 배열에 1~2번 작업 반복

 

전체 코드

// 코드 참고 GitHub @dragon-liu
const quickSort = (array) => {
  if (array.length <= 1) return array; // Base Case

  // 배열 분할을 위한 기준 요소 선택 및 left, right 하위 배열 생성
  const pivotIndex = Math.floor(array.length / 2);
  const pivot = array.splice(pivotIndex, 1)[0]; // 피벗 요소
  const left = [];
  const right = [];

  // 피벗 요소보다 작으면 left 하위 배열에 추가, 피벗 요소보다 크면 right 하위 배열에 추가
  for (let i = 0; i < array.length; i++) {
    if (array[i] < pivot) left.push(array[i]);
    else right.push(array[i]);
  }

  // 정렬된 배열을 얻기 위해 재귀 호출로 위 과정 반복
  return quickSort(left).concat(pivot, quickSort(right));
};

const sorted = quickSort([85, 24, 63, 45, 17, 31, 96, 50]);
console.log(sorted); // [17, 24, 31, 45, 50, 63, 85, 96]

 

In Place Quick Sort ⭐️

In place 방식 : 제자리 정렬 / 추가 메모리 공간 필요 없음
Unstable 방식 : 중복 데이터 순서 바뀔 수 있음

 

진행 과정 분석

quickSort 함수 ▼

⑴ Q([85, 24, 63, 45, 17, 31, 96, 50], 0, 7)
===========================================
b = P([85, 24, 63, 45, 17, 31, 96, 50], 0, 7) -> [P-1] = 4 | [31, 24, 17, 45, 63, 85, 96, 50]
⑵ Q([31, 24, 17, 45, 63, 85, 96, 50], 0, 3) -> [17, 24, 31, 45, 63, 85, 96, 50]
⑼ Q([17, 24, 31, 45, 63, 85, 96, 50], 4, 7) -> [17, 24, 31, 45, 50, 63, 85, 96]
---------------------------------------
return [17, 24, 31, 45, 50, 63, 85, 96]

⑵ Q([31, 24, 17, 45, 63, 85, 96, 50], 0, 3)
===========================================
b = P([31, 24, 17, 45, 63, 85, 96, 50], 0, 3) -> [P-2] = 2 | [17, 24, 31, 45, 63, 85, 96, 50]
⑶ Q([17, 24, 31, 45, 63, 85, 96, 50], 0, 1) -> [17, 24, 31, 45, 63, 85, 96, 50]
⑹ Q([17, 24, 31, 45, 63, 85, 96, 50], 2, 3) -> [17, 24, 31, 45, 63, 85, 96, 50]
---------------------------------------
return [17, 24, 31, 45, 63, 85, 96, 50]

⑶ Q([17, 24, 31, 45, 63, 85, 96, 50], 0, 1)
===========================================
b = P([17, 24, 31, 45, 63, 85, 96, 50], 0, 1) -> [P-3] = 1 | Swap 없음
⑷ Q([17, 24, 31, 45, 63, 85, 96, 50], 0, 0) -> Base case return
⑸ Q([17, 24, 31, 45, 63, 85, 96, 50], 1, 1) -> Base case return
---------------------------------------
return [17, 24, 31, 45, 63, 85, 96, 50] 

⑹ Q([17, 24, 31, 45, 63, 85, 96, 50], 2, 3)
===========================================
b = P([17, 24, 31, 45, 63, 85, 96, 50], 2, 3) -> [P-4] = 3 | Swap 없음
⑺ Q([17, 24, 31, 45, 63, 85, 96, 50], 2, 2) -> Base case return
⑻ Q([17, 24, 31, 45, 63, 85, 96, 50], 3, 3) -> Base case return
---------------------------------------
return [17, 24, 31, 45, 63, 85, 96, 50]

⑼ Q([17, 24, 31, 45, 63, 85, 96, 50], 4, 7)
===========================================
b = P([17, 24, 31, 45, 63, 85, 96, 50], 4, 7) -> [P-5] = 6 | [17, 24, 31, 45, 63, 50, 96, 85]
⑽ Q([17, 24, 31, 45, 63, 50, 96, 85], 4, 5) -> [17, 24, 31, 45, 50, 63, 96, 85]
⒀ Q([17, 24, 31, 45, 50, 63, 96, 85], 6, 7) -> [17, 24, 31, 45, 50, 63, 85, 96]
---------------------------------------
return [17, 24, 31, 45, 50, 63, 85, 96]

⑽ Q([17, 24, 31, 45, 63, 50, 96, 85], 4, 5)
===========================================
b = P([17, 24, 31, 45, 63, 50, 96, 85], 4, 5) -> [P-6] = 5 | [17, 24, 31, 45, 50, 63, 96, 85]
⑾ Q([17, 24, 31, 45, 50, 63, 96, 85], 4, 4) -> Base case return
⑿ Q([17, 24, 31, 45, 50, 63, 96, 85], 5, 5) -> Base case return
---------------------------------------
return [17, 24, 31, 45, 50, 63, 96, 85]

⒀ Q([17, 24, 31, 45, 50, 63, 96, 85], 6, 7)
===========================================
b = P([17, 24, 31, 45, 50, 63, 96, 85], 6, 7) -> [P-7] = 7 | [17, 24, 31, 45, 50, 63, 85, 96]
⒁ Q([17, 24, 31, 45, 50, 63, 85, 96], 6, 6) -> Base case return
⒂ Q([17, 24, 31, 45, 50, 63, 85, 96], 7, 7) -> Base case return
---------------------------------------
return [17, 24, 31, 45, 50, 63, 85, 96]

 

배열을 나누는 기준 인덱스를 반환하는 partition 함수 / start, end 범위 내에서 정렬도 이뤄짐 ▼

[P-1] P([85, 24, 63, 45, 17, 31, 96, 50], 0, 7)
===============================================
pivot = 45, i = 0, j = 7
------------------------
while (0 <= 7)
85 < 45 (x) : i = 0
50 > 45 (-1) -> 96 > 45 (-1) -> 31 > 45 (x) : j = 5
if (0 <= 5) -> swap 85/31 -> [31, 24, 63, 45, 17, 85, 96, 50] -> i = 1, j = 4
------------------------
while (1 <= 4)
24 < 45 (+1) -> 63 < 45 (x) : i = 2
17 > 45 (x) : j = 4
if (2 <= 4) -> swap 63/17 -> [31, 24, 17, 45, 63, 85, 96, 50] -> i = 3, j = 3
------------------------
while (3 <= 3)
45 < 45 (x) : i = 3
45 > 45 (x) : j = 3
if (3 <= 3) -> swap 45/45 -> [31, 24, 17, 45, 63, 85, 96, 50] -> i = 4, j = 2
------------------------
return 4

[P-2] P([31, 24, 17, 45, 63, 85, 96, 50], 0, 3)
===============================================
pivot = 24, i = 0, j = 3
------------------------
while (0 <= 3)
31 < 24 (x) : i = 0
45 > 24 (-1) -> 17 > 24 (x) : j = 2
if (0 <= 2) -> swap 31/17 -> [17, 24, 31, 45, 63, 85, 96, 50] -> i = 1, j = 1
------------------------
while (1 <= 1)
24 < 24 (x) : i = 1
24 > 24 (x) : j = 1
if (1 <= 1) -> swap 24/24 -> [17, 24, 31, 45, 63, 85, 96, 50] -> i = 2, j = 0
------------------------
return 2

[P-3] P([17, 24, 31, 45, 63, 85, 96, 50], 0, 1)
===============================================
pivot = 17, i = 0, j = 1
------------------------
while (0 <= 1)
17 < 17 (x) : i = 0
24 > 17 (-1) -> 17 > 17 (x) : j = 0
if (0 <= 0) -> swap 17/17 -> [17, 24, 31, 45, 63, 85, 96, 50] -> i = 1, j = -1
------------------------
return 1

[P-4] P([17, 24, 31, 45, 63, 85, 96, 50], 2, 3)
===============================================
pivot = 31, i = 2, j = 3
------------------------
while (2 <= 3)
31 < 31 (x) : i = 2
45 > 31 (-1) -> 31 > 31 (x) : j = 2
if (2 <= 2) -> swap 31/31 -> [17, 24, 31, 45, 63, 85, 96, 50] -> i = 3, j = 1
------------------------
return 3

[P-5] P([17, 24, 31, 45, 63, 85, 96, 50], 4, 7)
===============================================
pivot = 85, i = 4, j = 7
------------------------
while (4 <= 7)
63 < 85 (+1) -> 85 < 85 (x) : i = 5
50 > 85 (x) -> j = 7
if (5 <= 7) -> swap 85/50 -> [17, 24, 31, 45, 63, 50, 96, 85] -> i = 6, j = 6
------------------------
while (6 <= 6)
96 < 85 (x) : i = 6
96 > 85 (-1) -> 50 > 85 (x) : j = 5
------------------------
return 6

[P-6] P([17, 24, 31, 45, 63, 50, 96, 85], 4, 5)
===============================================
pivot = 63, i = 4, j = 5
------------------------
while (4 <= 5)
63 < 63 (x) : i = 4
50 > 63 (x) : j = 5
if (4 <= 5) -> swap 63/50 -> [17, 24, 31, 45, 50, 63, 96, 85] -> i = 5, j = 4
------------------------
return 5

[P-7] P([17, 24, 31, 45, 50, 63, 96, 85], 6, 7)
===============================================
pivot = 96, i = 6, j = 7
------------------------
while (6 <= 7)
96 < 96 (x) : i = 6
85 > 96 (x) : j = 7
if (6 <= 7) -> swap 96/85 -> [17, 24, 31, 45, 50, 63, 85, 96] -> i = 7, j = 6
------------------------
return 7

 

경계 인덱스 찾기 / 피벗 기준으로 정렬

 

1. 처음 호출할 땐 배열 첫번째 / 마지막 인덱스를 각각 left(i), right(j)로 설정
2. left, right 인덱스를 경계로 가운데 요소를 피벗으로 설정
   ex) const pivot = arr[Math.floor((start + end) / 2)]
3. left 포인터가 가리키는 요소와 피벗 요소 비교
   • left 포인터 요소가 피벗 요소보다 작으면 포인터 우측으로 이동 (left 인덱스 + 1)
   • 피벗 요소 보다 더 큰 값을 찾을때까지 반복
4. right 포인터가 가리키는 요소와 피벗 요소 비교
   • right 포인터 요소가 피벗 요소보다 크면 포인터 좌측으로 이동 (right 인덱스 - 1)
   • 피벗 요소 보다 더 작은 값을 찾을때까지 반복
5. left, right 포인터가 교차했는지 확인
   • 교차 전이면(left < right)
     • 피벗 왼쪽에 더 큰 값이 있는 상태므로 left ⇄ right 요소 교환(Swap)
     • 다음 검색을 위해 left + 1, right - 1
   • 이미 교차 했을 때도(left === right) 경계 인덱스 설정을 위해 조건 통과 후 인덱스 이동
6. left가 right 보다 커질때까지 3~5 과정 반복. 커졌다면 left 반환하고 경계 인덱스로 사용

 

경계 인덱스를 기준으로 배열 분할 후 순환 호출

💡 start와 end 인덱스가 같을때까지 작업 반복

 

右 partition 함수 호출 후 — start, end 범위안에서 정렬 및 다음 경계 인덱스 반환

좌측 배열 : start(항상 동일) ~ borderIndex - 1

// 경계 인덱스 좌측의 분할 과정
// start 0 | end 7 | bdx 4 (borderIndex)
[1, 2, 3, 4, 5, 6, 7, 8] 
// start 0 | end 3 (이전 bdx - 1) | bdx 2
[1, 2, 3, 4, (5), (6), (7), (8)] 
// start 0 | end 1 (이전 bdx - 1) | bdx 1
[1, 2, (3), (4), (5), (6), (7), (8)] 
// start 0 | end 0 (이전 bdx - 1) -> start === end
[1, (2), (3), (4), (5), (6), (7), (8)]

 

우측 배열 : borderIndex ~ end(항상 동일)

// 경계 인덱스 우측의 분할 과정
// start 0 | end 7 | bdx 4 (borderIndex)
[1, 2, 3, 4, 5, 6, 7, 8]
// start 4 (이전 bdx) | end 7 | bdx 6
[(1), (2), (3), (4), 5, 6, 7, 8] 
// start 6 (이전 bdx) | end 7 | bdx 7
[(1), (2), (3), (4), (5), (6), 7, 8] 
// start 7 (이전 bdx) | end 7 -> start === end
[(1), (2), (3), (4), (5), (6), (7), 8]

 

전체 코드

---

// 배열과 a, b 인덱스를 인자로 받아 배열[a] 배열[b] 순서를 바꾸는 함수
const swap = (arr, a, b) => {
  /* const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp; */
  [arr[a], arr[b]] = [arr[b], arr[a]];
};

// Hoare 분할 방법을 사용한 퀵 정렬 - 코드 참고 https://bit.ly/3QjduFC
function quickSort(arr, start = 0, end = arr.length - 1) {
  if (start >= end) return; // Base Case

  const borderIndex = partition(arr, start, end); // 배열을 나누는 경계 인덱스
  quickSort(arr, start, borderIndex - 1); // borderIndex 왼쪽 요소
  quickSort(arr, borderIndex, end); // borderIndex 오른쪽 요소

  return arr;
}

function partition(arr, start, end) {
  const pivot = arr[Math.floor((start + end) / 2)]; // 가운데 요소를 pivot으로 설정

  let i = start; // 왼쪽 포인터
  let j = end; // 오른쪽 포인터

  // i/j 포인터가 교차할 때까지 반복(교차 전이라면 pivot 왼쪽에 더 큰 값이 남아 있는 상태)
  while (i <= j) {
    while (arr[i] < pivot) i++; // 배열 왼쪽부터 pivot 값 보다 큰 요소의 인덱스 검색
    while (arr[j] > pivot) j--; // 배열 오른쪽부터 pivot 값 보다 작은 요소의 인덱스 검색

    // i/j 포인터가 교차전이라면
    if (i <= j) {
      // i < j : i 인덱스 요소가 j 인덱스 요소보다 보다 큰 값이므로 swap 후 인덱스 이동
      // i = j : 이미 교차 했을때도 다음 경계 인덱스를 위해 i/j swap 후 인덱스 이동
      swap(arr, i, j);
      i++; // 다음 검색을 위해 i + 1
      j--; // 다음 검색을 위해 i - 1
    }
  }

  return i; // 교차 후의 i 인덱스를 다음 경계 인덱스로 사용하기 위해 리턴
}

 

로그(Logarithm) 참고 내용

시간 복잡도에서 로그는 밑(base)을 표기하지 않지만, 밑이 2인 로그라고 생각하면 된다(log₂N).

 

• 로그는 지수(exponent)의 정반대 개념. 2를 몇 번 거듭제곱해야 32가 나오는지 계산하는게 지수, 32는 2를 몇 번 나눠야 1이 나오는지 계산하는게 로그. 참고로 로그는 지수 방정식으로 바꿔서 계산하면 편함(logₐ(b) → a를 몇 번 제곱해야 b가 나올지 계산해본다).
  • 지수 : 2ⁿ = 32 → 32는 2를 5번 거듭제곱해야 나오므로 n = 5
  • 로그 : log₂(32) = n → 32는 2를 5번 나눠야 1이 나오므로 n = 5
• 즉, O(logN)은 데이터 원소가 N개 있을 때 알고리즘이 log₂N 단계가 걸린다는 의미. 요소가 8개라면 log₂8 = 3 이므로 O(logN) 알고리즘은 3단계가 필요한 것으로 해석할 수 있다.

 

시간 복잡도

---

❶ Worst Case(이미 정렬된 배열에 최소 or 최대값을 피벗으로 사용했을 때) : O(n²)

 

이미 정렬된 배열에 최소 혹은 최대값을 피벗으로 지정하면, 배열을 나누는 경계 인덱스가 항상 첫번째 혹은 마지막이기 때문에 리스트의 불균형 분할로 인해 n번 만큼 순환호출한다. 각 순환호출마다 리스트의 모든 요소를 비교하므로 O(n²) 시간 복잡도를 갖는다.

 

재귀 호출의 깊이가 n과 동일한 최악의 시간 복잡도 ❘ 이미지 출처 rhtn

❷ Best / Average Case(정렬이 안됐을 때) : O(nlog₂n) 

 

순환 호출의 깊이 (재귀 호출의 깊이)

---

이미지 및 설명 출처 - gmlwjd9405

• 레코드의 개수 n이 2의 거듭제곱 n = 2^k 이라고 가정했을 때
• n = 2^3은  2^3, 2^2, 2^1, 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다
• 위를 토대로 n = 2^k을 일반화하면 k(k = log₂n)임을 알 수 있다 → k = log₂n

$k = log₂n$ (데이터 길이 n이 8이라고 가정, 8은 2를 3번 제곱해야 나오므로 재귀 호출의 깊이 k는 3)

 

병합 정렬 및 퀵 정렬은 데이터 길이가 1이 될때까지 절반씩 분할한다. 데이터 길이가 8이라면 4(8/2) → 2(4/2) → 1(2/2) 분할 과정을 거치므로 깊이는 3이 된다. [21, 10, 12, 20, 25, 13, 15, 22] 배열을 예를 들어보면…

 

• 1 depth : 8 / 2 = 4 → n / 2 크기의 부분 배열 1쌍 비교 (부분 배열 개수 2개)
  • ( [21, 10, 12, 20] — L
  • [25, 13, 15, 22] )① — R
• 2 depth : 4 / 2 = 2 → n / 4 크기의 부분 배열 2쌍 비교 (부분 배열 개수 4개)
  • ( [21, 10] [12, 20] )① — L
  • ( [25, 13] [15, 22] )② — R
• 3 depth : 2 / 2 = 1 → n / 8 크기의 부분 배열 4쌍 비교 (부분 배열 개수 8개)
  • ( [21] [10] )① ( [12] [20] )② — L
  • ( [25] [13] )③ ( [15] [22] )④ — R

 

순환 호출 단계의 비교 연산

각 순환(재귀) 호출 단계마다 리스트의 모든 요소를 피벗 요소와 비교하므로 총 n번의 비교가 이뤄진다.

각 순환 호출 단계마다 최대 n번의 비교 연산을 수행하므로 시간 복잡도는…
각 순환 호출 단계의 비교 연산(n) × 순환 호출 깊이(log₂n) = nlog₂n
데이터 길이가 8이라면 최대 24번의 작업 수행

 

장단점

---

Stable 정렬 : 중복 데이터는 순서를 바꾸지 않는 방식(Unstable 정렬은 중복 데이터도 순서 바꿈)
In-place 정렬 : 새로운 배열 생성 없이 기존 배열만 사용하거나, 충분히 무시할만한 저장 공간만 더 사용하는 정렬 방식(Not In-place 정렬은 요소 개수에 비례하는 저장공간을 더 사용함)

 

1. 장점 (In-place 정렬 방식 기준)
   • 빠른 정렬 속도 (O(nlog₂n) 시간 복잡도를 갖는 다른 정렬 알고리즘 중에서 가장 빠름)
   • 추가 메모리 사용 안함
2. 단점 (In-place 정렬 방식 기준)
   • 정렬된 리스트에 최소 or 최대값을 피벗으로 사용하면 수행시간 더 길어짐
   • Unstable 정렬 방식

 

레퍼런스

---

• [알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog
• QuickSort Algorithm in JavaScript
• 第18章 排序算法 | JavaScript 数据结构与算法
• [JS/Sorting] 퀵 정렬, 자바스크립트로 구현하기 (Quick Sort in JavaScript)
• JavaScript로 Quick Sort(퀵 정렬) 구현하기  

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요