정렬 알고리즘

1. 정렬 알고리즘이란?

정렬(sorting)은 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 의미합니다.
정렬 알고리즘을 사용하면 검색을 더 쉽게 할 수 있습니다.

정렬의 종류

종류	설명	예시
오름차순	작은 데이터를 앞쪽에 놓는 방식	[1, 2, 3, 4, 5]
내림차순	작은 데이터를 뒤쪽에 놓는 방식	[5, 4, 3, 2, 1]

정렬 알고리즘의 안정성

정렬 알고리즘은 안정된 정렬과 불안정한 정렬로 나뉩니다.

• 안정된 정렬: 키 값이 같은 요소의 순서가 정렬 전후에도 유지됨
  • 예: 학번순으로 정렬된 시험 점수 배열에서 점수가 같은 학생들의 원래 학번 순서가 유지됨

내부 정렬과 외부 정렬

구분	설명
내부 정렬	정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용하는 알고리즘
외부 정렬	정렬할 데이터가 너무 많아 하나의 배열에 저장할 수 없을 때 사용하는 알고리즘

본 내용에서 다루는 알고리즘은 모두 내부 정렬에 해당합니다.

정렬 알고리즘의 핵심 요소

대부분의 정렬 알고리즘은 아래 세 가지 요소를 응용합니다.

• 교환 (Exchange)
• 선택 (Selection)
• 삽입 (Insertion)

---

2. 주요 정렬 알고리즘

여러 정렬 알고리즘의 특징, 동작 원리, 시간 복잡도를 표와 함께 정리합니다.

버블 정렬 (Bubble Sort)

정의: 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘 (단순 교환 정렬)

• 동작 원리:
  1. 인접한 두 요소를 비교하여 오름차순(또는 내림차순)으로 정렬될 때까지 교환
  2. 첫 번째 패스가 끝나면 가장 작은 요소가 맨 앞으로 이동
  3. n-1번 패스가 필요
• 안정성: 서로 이웃한 요소만 교환하므로 안정적
• 개선: 교환이 한 번도 일어나지 않으면 정렬 종료
• 시간 복잡도:
  • 비교: O(n²)
  • 이동: 최악 O(n²), 최선(이미 정렬) 0
  • 전체: 평균 O(n²)

예시 코드 (TypeScript):

function bubbleSort(arr: number[]): number[] {
  const a = [...arr];
  for (let i = 0; i < a.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return a;
}
// 사용 예시: bubbleSort([5, 2, 4, 3, 1]) → [1, 2, 3, 4, 5]

---

단순 선택 정렬 (Simple Selection Sort)

정의: 가장 작은 요소를 맨 앞으로 이동, 두 번째 작은 요소는 두 번째로 이동하는 작업 반복

• 동작 원리:
  1. 정렬되지 않은 부분에서 가장 작은 값을 찾아 첫 번째 요소와 교환
  2. n-1회 반복
• 안정성: 불안정
• 시간 복잡도:
  • 비교: O(n²)
  • 이동: 3(n-1)
  • 전체: O(n²)

예시 코드 (TypeScript):

function selectionSort(arr: number[]): number[] {
  const a = [...arr];
  for (let i = 0; i < a.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < a.length; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];
  }
  return a;
}
// 사용 예시: selectionSort([5, 2, 4, 3, 1]) → [1, 2, 3, 4, 5]

---

단순 삽입 정렬 (Simple Insertion Sort)

정의: 선택한 요소를 앞쪽의 알맞은 위치에 삽입하는 작업 반복 (트럼프 카드 정렬과 유사)

• 동작 원리:
  1. 두 번째 요소부터 시작, 앞쪽 정렬된 부분의 알맞은 위치에 삽입
  2. 기존 요소들을 오른쪽으로 이동
  3. n-1회 반복
• 장점: 안정적, 대부분 정렬되어 있으면 매우 효율적
• 단점: 많은 이동 필요, 레코드가 크면 불리함
• 시간 복잡도:
  • 최선(이미 정렬): O(n)
  • 최악(역순): O(n²)
  • 평균: O(n²)

예시 코드 (TypeScript):

function insertionSort(arr: number[]): number[] {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    let key = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
  return a;
}
// 사용 예시: insertionSort([5, 2, 4, 3, 1]) → [1, 2, 3, 4, 5]

---

셸 정렬 (Shell Sort)

정의: 단순 삽입 정렬의 장점을 살리고 단점을 보완한 빠른 정렬 (도날드 셸 고안)

• 특징:
  • 일정 간격으로 떨어진 요소끼리 그룹 정렬 후, 간격을 좁혀가며 반복
  • 마지막엔 1-정렬(일반 삽입 정렬) 적용
• 시간 복잡도:
  • 명확히 제시되지 않으나, 단순 정렬(O(n²))보다 효율적

예시 코드 (TypeScript):

function shellSort(arr: number[]): number[] {
  const a = [...arr];
  let gap = Math.floor(a.length / 2);
  while (gap > 0) {
    for (let i = gap; i < a.length; i++) {
      let temp = a[i];
      let j = i;
      while (j >= gap && a[j - gap] > temp) {
        a[j] = a[j - gap];
        j -= gap;
      }
      a[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return a;
}
// 사용 예시: shellSort([5, 2, 4, 3, 1]) → [1, 2, 3, 4, 5]

---

퀵 정렬 (Quick Sort)

정의: 분할 정복(divide and conquer) 기반의 아주 빠른 정렬 (찰스 호어 개발)

• 동작 원리:
  1. 피벗(pivot) 선택
  2. 피벗보다 작은/큰 요소로 그룹 분할 (partition)
  3. 각 그룹에 대해 재귀적으로 반복
• 피벗 선택:
  • 임의의 3개 요소 중 중앙값, 처음/가운데/끝 요소 중 가운데 등
• 시간 복잡도:
  • 평균: O(n log n)
  • 최악: O(n²)

예시 코드 (TypeScript):

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter((x) => x < pivot);
  const mid = arr.filter((x) => x === pivot);
  const right = arr.filter((x) => x > pivot);
  return [...quickSort(left), ...mid, ...quickSort(right)];
}
// 사용 예시: quickSort([5, 2, 4, 3, 1]) → [1, 2, 3, 4, 5]

---

병합 정렬 (Merge Sort)

정의: 정렬된 배열의 병합을 응용한 분할 정복 정렬

• 동작 원리:
  1. 리스트를 두 개의 균등한 크기로 분할 (Divide)
  2. 분할된 부분 리스트를 정렬 (Conquer)
  3. 정렬된 두 부분 리스트를 합침 (Combine)
• 특징: 안정적, 데이터 분산 순서에 영향 적음
• 시간 복잡도:
  • 최적/평균/최악: O(n log n)
  • (log n 패스 × n번 비교, 2n번 이동)
  • 단점: 요소 크기가 크면 비효율적

예시 코드 (TypeScript):

function mergeSort(arr: number[]): number[] {
  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));
  const merged: number[] = [];
  let i = 0,
    j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) merged.push(left[i++]);
    else merged.push(right[j++]);
  }
  return [...merged, ...left.slice(i), ...right.slice(j)];
}
// 사용 예시: mergeSort([5, 2, 4, 3, 1]) → [1, 2, 3, 4, 5]

---

3. 정렬 알고리즘 시간 복잡도 비교

알고리즘	최선	평균	최악	안정성
버블 정렬	O(n²)	O(n²)	O(n²)	안정
선택 정렬	O(n²)	O(n²)	O(n²)	불안정
삽입 정렬	O(n)	O(n²)	O(n²)	안정
셸 정렬	-	-	O(n²)	불안정
퀵 정렬	O(n log n)	O(n log n)	O(n²)	불안정
병합 정렬	O(n log n)	O(n log n)	O(n log n)	안정
힙 정렬	O(n log n)	O(n log n)	O(n log n)	불안정

O(n²) 알고리즘: 삽입 정렬, 선택 정렬, 버블 정렬
O(n log n) 알고리즘: 퀵 정렬, 힙 정렬, 병합 정렬