정렬 (Sort)

책장에 있는 책들을 키 순서대로 정리한다고 생각해보자. 작은 책부터 큰 책 순서로 나열하는 방법은 여러 가지가 있다.

어떤 방법은 간단하지만 느리고, 어떤 방법은 복잡하지만 빠르다.

 

이것이 바로 정렬 알고리즘이다.

정렬 (Sort)

정렬은 데이터를 특정 순서대로 배열하는 알고리즘이다.

오름차순(작은 것부터 큰 것), 내림차순(큰 것부터 작은 것) 등 다양한 기준으로 정렬할 수 있다.

정렬 알고리즘 비교

	시간복잡도	난이도	특징
버블 정렬	O(n²)	쉬움	인접한 원소를 교환
선택 정렬	O(n²)	쉬움	최솟값을 찾아 교환
삽입 정렬	O(n²)	쉬움	적절한 위치에 삽입
병합 정렬	O(n log n)	어려움	분할 정복, 안정 정렬
퀵 정렬	O(n log n) ~ O(n²)	어려움	분할 정복, 실정네서 빠름

 

버블 정렬 (Bubble Sort)

인접한 두 원소를 비교해 순서가 잘못된 경우 자리를 교환하는 방식의 정렬 알고리즘이다.

큰 값이 점차 뒤로 이동하는 모습이 거품이 위로 올라오는 모습과 닮아 버블 정렬이라고 불린다.

동작 과정

[4, 2, 3, 1]을 오름차순으로 정렬한다고 가정하자.

 

1회전:

• (4, 2) 비교 → 교환 → [2, 4, 3, 1]
• (4, 3) 비교 → 교환 → [2, 3, 4, 1]
• (4, 1) 비교 → 교환 → [2, 3, 1, 4] (가장 큰 4가 맨 뒤로)

2회전:

• (2, 3) 비교 → 유지 → [2, 3, 1, 4]
• (3, 1) 비교 → 교환 → [2, 1, 3, 4] (3이 제자리로)

3회전:

• (2, 1) 비교 → 교환 → [1, 2, 3, 4] (완료)

 

구현 코드

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // i번째 회전
    for (let j = 0; j < arr.length - i - 1; j++) {
      // 인접한 두 원소 비교
      if (arr[j] > arr[j + 1]) {
        // 교환
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

let arr = [4, 2, 3, 1];
console.log("정렬 전:", arr);  // 정렬 전: [4, 2, 3, 1]

bubbleSort(arr);
console.log("정렬 후:", arr);  // 정렬 후: [1, 2, 3, 4]

장단점

• 장점: 이해와 구현이 간단함
• 단점: 성능이 O(n²) 으로 비효율적

 

선택 정렬 (Selection Sort)

배열의 정렬되지 않은 영역에서 가장 작은 값을 찾아, 그 값을 정렬되지 않은 영역의 첫 번째 원소와 교환하는 방식으로 정렬하는 알고리즘이다.

동작 과정

[4, 2, 1, 3]을 오름차순으로 정렬한다고 가정하자.

 

1회전:

• 전체에서 최솟값 1 찾기
• 1과 첫 번째 원소 4 교환 → [1, 2, 4, 3]

2회전:

• 나머지(2, 4, 3)에서 최솟값 2 찾기
• 2는 이미 제자리 → [1, 2, 4, 3]

3회전:

• 나머지(4, 3)에서 최솟값 3 찾기
• 3과 4 교환 → [1, 2, 3, 4] (완료)

 

구현 코드

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minValueIndex = i;  // 최솟값의 인덱스
    
    // i 이후에서 최솟값 찾기
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minValueIndex]) {
        minValueIndex = j;
      }
    }
    
    // 최솟값과 i번째 원소 교환
    let temp = arr[i];
    arr[i] = arr[minValueIndex];
    arr[minValueIndex] = temp;
  }
}

let arr = [4, 2, 1, 3];
console.log("정렬 전:", arr);  // [4, 2, 1, 3]

selectionSort(arr);
console.log("정렬 후:", arr);  // [1, 2, 3, 4]

 

장단점

• 장점: 이해와 구현이 간단함
• 단점: 성능이 O(n²) 으로 비효율적

 

삽입 정렬 (Insertion Sort)

배열을 정렬된 영역과 정렬되지 않은 영역으로 나눈 뒤, 비정렬 영역에서 데이터를 하나씩 꺼내 정렬된 영역의 올바른 위치에 삽입하는 정렬 알고리즘이다. 카드 게임에서 카드를 정리하는 방식과 유사하다.

동작 과정

[4, 1, 5, 3]을 오름차순으로 정렬한다고 가정하자. 

 

초기: [4] (정렬됨) | [1, 5, 3] (비정렬) 

1회전: 1을 정렬된 영역에 삽입

• 1 < 4 → 4를 오른쪽으로 이동 → [1, 4] | [5, 3]

2회전: 5를 정렬된 영역에 삽입

• 5 > 4 → 그대로 → [1, 4, 5] | [3]

3회전: 3을 정렬된 영역에 삽입

• 3 < 5 → 5를 오른쪽으로 이동
• 3 < 4 → 4를 오른쪽으로 이동
• 3 > 1 → 1 뒤에 삽입 → [1, 3, 4, 5] (완료)

 

구현 코드

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let insertingData = arr[i];  // 삽입할 데이터
    let j;
    
    // 정렬된 영역을 뒤에서부터 확인
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > insertingData) {
        arr[j + 1] = arr[j];  // 오른쪽으로 이동
      } else {
        break;  // 적절한 위치 발견
      }
    }
    
    arr[j + 1] = insertingData;  // 삽입
  }
}

let arr = [4, 1, 5, 3, 6, 2];
console.log("정렬 전:", arr);  // [4, 1, 5, 3, 6, 2]

insertionSort(arr);
console.log("정렬 후:", arr);  // [1, 2, 3, 4, 5, 6]

 

장단점

• 장점: 이해와 구현이 간단함, 거의 정렬된 데이터에는 효율적
• 단점: 성능이 O(n²) 으로 비효율적

 

병합 정렬 (Merge Sort)

분할 정복(Divide and Conquer) 방식의 정렬 알고리즘으로, 

배열을 반으로 계속 나누어(분할) 각각을 재귀적으로 정렬한 뒤(정복) 두 정렬된 배열을 병합하여 하나의 정렬된 배열로 만드는 방식이다.

동작 과정

[3, 5, 2, 4, 1, 7]을 정렬한다고 가정하자.

 

분할:

[3, 5, 2, 4, 1, 7]
    ↓
[3, 5, 2] [4, 1, 7]
    ↓
[3] [5, 2] [4] [1, 7]
    ↓
[3] [5] [2] [4] [1] [7]

병합:

[3] [2, 5] [4] [1, 7]
    ↓
[2, 3, 5] [1, 4, 7]
    ↓
[1, 2, 3, 4, 5, 7]

 

구현 코드

function mergeSort(arr, leftIndex, rightIndex) {
  if (leftIndex < rightIndex) {
    let midIndex = parseInt((leftIndex + rightIndex) / 2);
    
    // 분할
    mergeSort(arr, leftIndex, midIndex);      // 왼쪽 절반 정렬
    mergeSort(arr, midIndex + 1, rightIndex); // 오른쪽 절반 정렬
    
    // 병합
    merge(arr, leftIndex, midIndex, rightIndex);
  }
}

function merge(arr, leftIndex, midIndex, rightIndex) {
  let leftAreaIndex = leftIndex;
  let rightAreaIndex = midIndex + 1;
  
  let tempArr = [];
  let tempArrIndex = leftIndex;
  
  // 두 영역을 비교하며 작은 값부터 임시 배열에 저장
  while (leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
    if (arr[leftAreaIndex] <= arr[rightAreaIndex]) {
      tempArr[tempArrIndex++] = arr[leftAreaIndex++];
    } else {
      tempArr[tempArrIndex++] = arr[rightAreaIndex++];
    }
  }
  
  // 남은 데이터 복사
  if (leftAreaIndex > midIndex) {
    for (let i = rightAreaIndex; i <= rightIndex; i++) {
      tempArr[tempArrIndex++] = arr[i];
    }
  } else {
    for (let i = leftAreaIndex; i <= midIndex; i++) {
      tempArr[tempArrIndex++] = arr[i];
    }
  }
  
  // 임시 배열을 원본 배열에 복사
  for (let i = leftIndex; i <= rightIndex; i++) {
    arr[i] = tempArr[i];
  }
}

let arr = [3, 5, 2, 4, 1, 7, 8, 6];
console.log("정렬 전:", arr);  // [3, 5, 2, 4, 1, 7, 8, 6]

mergeSort(arr, 0, arr.length - 1);
console.log("정렬 후:", arr);  // [1, 2, 3, 4, 5, 6, 7, 8]

 

장단점

• 장점: 성능이 O(n log n) 으로 좋음, 안정 정렬
• 단점: 이해와 구현이 어려움, 추가 메모리 필요

 

퀵 정렬 (Quick Sort)

분할 정복(Divide and Conquer) 방식의 정렬 알고리즘으로,

피벗(pivot)을 기준으로 배열을 두 부분으로 분할하여 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킨 후, 각 부분을 재귀적으로 정렬하는 방식이다.

동작 과정

[5, 3, 7, 2, 6, 4]를 정렬한다고 가정하자. 피벗은 첫 번째 원소 5로 선택한다. 

 

1단계: 분할

• 피벗 5보다 작은 값: [3, 2, 4]
• 피벗: 5
• 피벗 5보다 큰값: [7, 6]

2단계: 재귀 정렬

• [3, 2, 4] 정렬 → [2, 3, 4]
• [7, 6] 정렬 → [6, 7]

최종 결과: [2, 3, 4, 5, 6, 7]

 

구현 코드

function quickSort(arr, left, right) {
  if (left <= right) {
    let pivot = divide(arr, left, right);  // 피벗 위치 찾기
    quickSort(arr, left, pivot - 1);       // 왼쪽 부분 정렬
    quickSort(arr, pivot + 1, right);      // 오른쪽 부분 정렬
  }
}

function divide(arr, left, right) {
  let pivot = arr[left];           // 첫 번째 원소를 피벗으로
  let leftStartIndex = left + 1;
  let rightStartIndex = right;
  
  while (leftStartIndex <= rightStartIndex) {
    // 왼쪽에서 피벗보다 큰 값 찾기
    while (leftStartIndex <= right && pivot >= arr[leftStartIndex]) {
      leftStartIndex++;
    }
    
    // 오른쪽에서 피벗보다 작은 값 찾기
    while (rightStartIndex >= left + 1 && pivot <= arr[rightStartIndex]) {
      rightStartIndex--;
    }
    
    // 교환
    if (leftStartIndex <= rightStartIndex) {
      swap(arr, leftStartIndex, rightStartIndex);
    }
  }
  
  // 피벗을 올바른 위치로 이동
  swap(arr, left, rightStartIndex);
  return rightStartIndex;
}

function swap(arr, index1, index2) {
  let temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
}

let arr = [5, 3, 7, 2, 6, 4, 9, 1, 8];
console.log("정렬 전:", arr);  // [5, 3, 7, 2, 6, 4, 9, 1, 8]

quickSort(arr, 0, arr.length - 1);
console.log("정렬 후:", arr);  // [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

장단점

• 장점
  • 평균 성능 O(n log n)
  • 실전에서 가장 빠름
  • 추가 메모리 거의 불필요
• 단점
  • 최악의 경우 O(n²) (이미 정렬된 경우)
  • 이해와 구현이 어려움

병합 정렬과 비교하면 최악의 경우 성능은 안 좋지만, 실제로는 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가된다.

 

정렬 알고리즘 선택 가이드

• 데이터가 적을 때 (< 100개): 삽입 정렬 (간단하고 빠름)
• 일반적인 경우: 퀵 정렬 (평균적으로 가장 빠름)
• 안정 정렬이 필요할 때: 병합 정렬
• 최악의 경우도 보장해야 할 때: 병합 정렬 (O(n log n) 보장)

 

정렬은 데이터를 특정 순서대로 배열하는 기본적이면서도 중요한 알고리즘이다. 

간단하지만 느린 O(n²) 정렬(버블, 선택, 삽입)과 복잡하지만 빠른 O(n log n) 정렬(병합, 퀵)이 있다. 

 

실전에서는 대부분 퀵 정렬을 사용하며, JavaScript의 Array.sort()도 내부적으로 퀵 정렬 또는 병합 정렬을 사용한다.