퀵 정렬 알고리즘 이해: JavaScript로 구현하기

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

웹 개발

대상자

- 대상자: JavaScript 알고리즘 구현을 배우고자 하는 중급 개발자

- 난이도: 재귀(Recursion) 개념을 이해한 상태에서의 알고리즘 학습

핵심 요약

• 평균 시간 복잡도: O(n log n), 인플레이스 정렬(메모리 효율적)**
• 피벗 선택 전략이 성능에 직접 영향 (예: Lomuto 방식 사용)
• 불안정한 정렬 알고리즘 (동일 값의 상대 순서 보존 X)

섹션별 세부 요약

1. 알고리즘 개요

• 분할 정복(Divide and Conquer) 방식 사용
• 피벗(Pivot) 기준으로 배열 분할 (작은 값 앞, 큰 값 뒤 배치)
• 재귀적 정렬 후 병합 단계 생략 (피벗 위치 고정)
• 예시 시각화: 책장 정리 비유로 설명 (피벗 기준으로 책 분류)

2. JavaScript 구현

• 피벗: 배열 마지막 요소 선택 (간단한 구현을 위해)
• 인플레이스 정렬: smallerItemsIndex 포인터로 배열 재구성
• 스왑 함수 사용: swap(arr, index1, index2)
• 코드 예시:

function quickSort(arr, start = 0, end = arr.length - 1) {
  if (start >= end) return;
  const pivotValue = arr[end];
  let smallerItemsIndex = start;
  // ...
}

3. 피벗 이동 과정

• 초기 상태: B (경계)는 0, P (피벗)은 배열 끝
• 스캔 중: 3 < 4 → 경계 이동, 2 < 4 → 경계 이동
• 최종: 피벗 4가 정렬된 위치로 이동 (예: [3, 2, 4, 8, 5])

4. 재귀 호출

• 왼쪽/오른쪽 서브배열 분리: [3, 2]와 [8, 5]에 재귀 호출
• 기저 조건: start >= end 시 재귀 종료 (0 또는 1 요소일 경우)

5. 안정성 문제

• 동일 값의 상대 순서 보존 X: 예: [3a, 1, 3b, 2] → [1, 2, 3b, 3a]
• 불안정 원인: 피벗 기준으로 비교 시 원래 위치 무시

6. 성능 분석

• 시간 복잡도:

- 최선: O(n log n) (피벗이 균형 잡힌 분할)

- 평균: O(n log n) (무작위 데이터)

- 최악: O(n²) (피벗이 항상 최소/최대일 때)

• 공간 복잡도: 평균 O(log n) (재귀 스택), 최악 O(n)

7. 장단점 요약

• 장점:

- 메모리 효율적 (인플레이스 정렬)

- 캐시 효율성 높음 (접근성 locality)

- 표준 라이브러리에서 널리 사용

• 단점:

- 불안정 (동일 요소 순서 변경)

- 최악의 경우 O(n²) (피벗 선택에 따라)

- 안정성 요구 시 Merge Sort 사용 권장

결론

• 피벗 선택 전략을 최적화 (예: 중앙값 선택)하여 성능 향상
• 안정성 요구 시 Merge Sort 대신 사용
• 재귀 기저 조건을 명확히 정의하여 무한 재귀 방지
• Lomuto 방식보다 Hoare 방식이 성능 향상 가능 (실무에서 고려)