[자료구조] 정렬 (Sort) - 병합 정렬, 퀵 정렬

1. 정렬이란?

정렬(Sorting)은 주어진 데이터를 특정 기준에 따라 순서대로 나열하는 과정이다.

• 예시
  • 숫자: 1, 2, 3, 4, 5 (오름차순)
  • 문자: a, b, c, d (사전식 순서)
• 기준: 오름차순(Ascending), 내림차순(Descending)
• 단일 키 정렬 : 하나의 정렬 기준
• 복합 키 정렬 : 두 개 이상의 정렬 기준

※ 정렬의 목표 : 정렬은 검색 속도를 빠르게 하거나, 데이터를 보기 좋게 정리하기 위해 사용된다.

---

2. 주요 용어 정리

용어	의미
키(Key)	정렬 기준이 되는 값
비교(Comparison)	두 원소의 키를 비교하는 동작
교환(Swap)	두 원소의 위치를 바꾸는 동작
이동(Move)	비교의 결과에 따라 위치 재조정
안정성(Stability)	같은 키의 원소 순서가 정렬 후에도 유지되는지 여부
In-Place	추가적인 메모리를 거의 사용하지 않는 정렬 방식
Comparison Sort	원소 간의 비교를 통해 정렬 (예: 버블, 삽입, 퀵)
Distribution Sort	비교 없이 분포 기반으로 정렬 (예: 카운팅, 버킷)
시간복잡도(time complexity)	알고리즘 수행에 필요한 연산 (비교, 교환, 재귀 호출 등) 의 수 (CPU Time)
공간복잡도(space complexity)	알고리즘 수행에 필요한 메모리의 크기 ( 입력 데이터 외에 임시 배열, 스택, 재귀 프레임 등을 더 사용할수록 커짐)

 

이미지 출처 : 위키피디아

---

3. 정렬 알고리즘 분류

분류 기준	예시
시간 복잡도	O(n²) 계열 vs O(n log n) 계열
동작 방식	비교 기반 vs 분포 기반
저장 공간	내부 정렬(메모리 내) vs 외부 정렬(디스크 등)

---

4. 정렬 알고리즘별 원리 & 특징

알고리즘	개념	특징	시간 복잡도
버블 정렬 (Bubble Sort)	인접한 두 개를 비교해서 자리를 바꿈	구현은 제일 쉬움, 하지만 느림	O(n²)
선택 정렬 (Selection Sort)	전체에서 가장 작은 값을 골라 앞으로 보냄	비교 횟수 많음, 교환은 적음	O(n²)
삽입 정렬 (Insertion Sort)	이미 정렬된 부분에 새 데이터를 “삽입”	데이터가 거의 정렬되어 있으면 빠름	O(n²)
병합 정렬 (Merge Sort)	반으로 나눈 뒤 각각 정렬하고 합침	“분할 정복” 개념 사용	O(n log n)
퀵 정렬 (Quick Sort)	기준(pivot)을 정하고 작은/큰 그룹으로 나눔	평균적으로 가장 빠름	평균 O(n log n), 최악 O(n²)
힙 정렬 (Heap Sort)	최대힙/최소힙 자료구조 이용	항상 O(n log n) 보장	O(n log n)

---

병합 정렬 (Merge Sort)

“Divide & Conquer” : 분할 → 정복 → 병합

개념

병합 정렬은 분할 정복(Divide & Conquer) 알고리즘의 대표적인 예시다.

배열을 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 배열을 병합하면서 전체 배열을 정렬한다.

※ 분할정복(Divide and conquer)알고리즘
- 하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘을 분할정복(Divide and conquer)알고리즘이라고 한다. 분할 정복 알고리즘은 보통 재귀 함수로 구현된다는 특징이 있다. 그래서 병합정렬(merge sort)도 재귀함수를 통해서 구현을 하게 될 것이다.

 

동작

1. 배열을 반으로 분할
2. 재귀적으로 병합 정렬 수행
3. 두 부분을 병합

복잡도

• 시간: O(n log n)
• 공간: O(n)
• 안정성: ✅

특징

• 항상 일정한 성능 보장
• 추가 메모리 필요

 

그림으로 보기

 

이미지 출처 : https://rosweet-ai.tistory.com/52

이미지 출처 : https://rosweet-ai.tistory.com/52

 

코드 예시

// 쪼개서 병합하는 함수
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

// 두 배열을 정렬해서 병합하는 함수
function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) result.push(left.shift());
    else result.push(right.shift());
  }
  return [...result, ...left, ...right];
}

// 코드 실행
console.log(mergeSort([10, 24, 76, 73])); // [10, 24, 73, 76]

---

퀵 정렬 (Quick Sort)

피벗(pivot)을 기준으로 작은 값과 큰 값을 분할해 정렬

개념
퀵 정렬 역시 분할 정복 알고리즘에 기반한다.
배열에서 하나의 원소를 피벗(pivot) 으로 선택하고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽에 분할한 뒤 재귀적으로 정렬한다.
대부분의 경우 매우 빠르게 동작하지만, 피벗 선택이 좋지 않은 경우 성능이 저하될 수 있다.

 

동작

1. 피벗 선택
2. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽
3. 양쪽 부분 배열에 대해 재귀 호출

복잡도

• 평균: O(n log n)
• 최악: O(n²)
• 공간: O(log n)
• 안정성: ❌

특징

• 가장 빠른 평균 성능
• 피벗 선택이 성능의 핵심
• 실제 언어의 sort() 기반 구현에 자주 사용

그림으로 보기

왼쪽, 오른쪽 두 개의 서브리스트에 피봇 재설정

더 분할할 대상이 없으므로 정렬 종료

[이미지 출처 : https://rosweet-ai.tistory.com/53#google_vignette]

 

 

코드 예시

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = arr.filter(x => x < pivot);
  const right = arr.filter(x => x > pivot);
  const equal = arr.filter(x => x === pivot);

  return [...quickSort(left), ...equal, ...quickSort(right)];
}

---

5. 알고리즘 비교 요약표

알고리즘	평균 시간복잡도	공간복잡도	안정성	비고
병합 정렬	O(n log n)	O(n)	✅	메모리 필요
퀵 정렬	O(n log n)	O(log n)	❌	평균 성능 최고

---

6. 정렬 알고리즘 선택 가이드

상황	추천 알고리즘
항상 일정한 성능이 필요한 경우	병합 정렬
평균적으로 빠른 성능이 필요한 경우	퀵 정렬

---

참고

• ratsgo.github.io
• velog.io/@geesuee