Algorithm_3. 정렬

개념

정렬(sorting) 알고리즘은 컴퓨터 분야에서 매우 중요한 문제로, 탐색을 위한 데이터의 나열을 의미한다.

O(n²) 정렬

버블 정렬

버블 정렬(Bubble sort)은 가장 기본적이면서 비효율적인 정렬 방식으로 1번째와 2번째, 2번째와 3번째 ... 와 같은 방식으로 모든 원소를 비교한다. 버블 정렬은 시간 복잡도가 O(n²)으로 실제 사용하는 경우는 거의 없지만, 정렬 알고리즘의 기본으로 주로 학습을 위해 다루게 된다.

자바스크립트

function bubbleSort(arr) {
  // i 번째로 큰 수가 i에 위치하게 된다.
  for (let i = 0; i < arr.length - 1; i++) {
    // 이미 정렬된 부분을 고려할 필요가 없으므로 - i 를 해준다
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
};

bubbleSort([4, 3, 2, 1]); // [1, 2, 3, 4]

[3,4,2,1]
[3,2,4,1]
[3,2,1,4]
[2,3,1,4]
[2,1,3,4]
[1,2,3,4]

파이썬

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

코드를 비교하면 파이썬이 스왑을 조금 더 쉽게 구현하는 것을 볼 수 있다.

칵테일 정렬

버블 정렬을 변형시켜 짝수, 홀수의 시작 방향을 다르게 만든 칵테일 정렬(cocktail sort)도 있다.

function cocktailSort(arr) {
  let min = 0;
  let max = arr.length - 1;
  let swapped = true;

  while (swapped) {
    swapped = false;

    // 왼쪽에서 오른쪽으로 커지는 버블정렬
    for (let i = min; i < max; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
    max--;

    if (!swapped) {
      break; // 이미 정렬되어 있는 경우 탈출
    }

    swapped = false;

    // 오른쪽에서 왼쪽으로 작아지는 버블정렬
    for (let i = max; i > min; i--) {
      if (arr[i - 1] > arr[i]) {
        let temp = arr[i];
        arr[i] = arr[i - 1];
        arr[i - 1] = temp;
        swapped = true;
      }
    }
    min++;
  }
  return arr;
}

cocktailSort([4, 3, 2, 1]);  // [1, 2, 3, 4]

[3,2,1,4]
[1,3,2,4]
[1,2,3,4]

선택 정렬

비교와 교체를 즉시 반복하는 버블 정렬과 달리 선택 정렬(Selection sort)은 가장 작은 원소부터 끝까지 훑어본 후 순서에 맞게 정렬한다. 이는 인간의 사고방식과 가장 비슷한 정렬 방식으로 볼 수 있으며 버블 정렬에 비해 약 2배 빠르다.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++){
  let smallestIdx = i
    // 가장 작은 요소의 인덱스 탐색
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[smallestIdx] > arr[j]) {
        smallestIdx = j;
      }
    }
    
    // 현재 요소(arr[i])가 가장 작은 요소가 아니라면 스왑
    if (arr[i] > arr[smallestIdx]) {
       let temp = arr[i];
       arr[i] = arr[smallestIdx];
       arr[smallestIdx] = temp;
    }
  }
  return arr;
}

selectionSort([4, 3, 2, 1]);  // [1, 2, 3, 4]

[1, 3, 2, 4]
[1, 2, 3, 4]

삽입 정렬

삽입 정렬(Insertion sort)은 한 원소를 적절한 위치에 끼워 넣기 위해 나머지 자료를 밀어내는 방식으로 정렬한다. 배열의 크기가 작은 경우 효율적으로 작동한다.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i]; // 현재값 저장
    let j = i - 1; // 정렬된 부분의 현재 인덱스
    
    // 좌측 값이 현재 값보다 크다면 스왑
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current; // 현재값을 정렬된 인덱스에 할당
  }
  return arr;
}

insertionSort([4, 3, 2, 1]);  // [1, 2, 3, 4]

[3, 4, 2, 1]
[2, 3, 4, 1]
[1, 2, 3, 4]

O(n log n) 정렬

병합 정렬

병합 정렬(Merge sort)은 대표적인 분할 정복 알고리즘으로 존 폰 노이만에 의해 개발되었다. 작동은 원소의 개수가 1 또는 0이 될 때까지 반으로 쪼개서 자른 순서의 역순으로 크기를 비교해 병합하는 식으로 이루어진다. 이러한 병합 정렬은 많은 메모리가 필요하지만 데이터의 상태에 영향을 받지 않는 안정 정렬이라는 장점이 있다.

function mergeSort(arr) {
  if (arr.length < 2) return arr; // 원소가 하나일 때는 그대로
  let pivot = Math.floor(arr.length / 2); 
  let left = arr.slice(0, pivot); 
  let right = arr.slice(pivot, arr.length); 
  return merge(mergeSort(left), mergeSort(right)); 
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) { // 두 배열의 첫 원소를 비교하여
      result.push(left.shift()); // 더 작은 수를 결과에 push
    } else {
      result.push(right.shift()); // 오른쪽도 마찬가지
    }
  }
  while (left.length) result.push(left.shift()); // 어느 한 배열이 더 많이 남았다면 나머지 모두 push
  while (right.length) result.push(right.shift()); // 오른쪽도 마찬가지
  return result;
};

mergeSort([4, 3, 2, 1]); // [1, 2, 3, 4]

[4, 3] [2, 1]
[4], [3], [2], [1]
[3, 4] [1, 2]
[1, 2, 3, 4]

퀵 정렬

퀵 정렬(Quick sort)은 비교 연산자를 사용하는 정렬 방식 중 가장 고성능 알고리즘으로 적절한 기준(pivot) 원소를 설정한 뒤 기준보다 크면 뒤로, 작으면 앞으로 보내는 작업을 반복하며 정렬한다. 그러나 기준을 설정하는 방식에 따라 성능 차이가 심하게 나기 때문에 무작위로 기준을 설정하는 Random Quick sort 방식이나 여러 정렬 알고리즘을 합친 하이브리드 퀵 정렬 등을 사용하기도 한다.

퀵 정렬은 분할 방식에 따라 Lomuto’s Partition Scheme과 Hoare’s Partition Scheme으로 나누어진다.

Lomuto’s Partition Scheme

function Swap(array, position1, position2) {
  let temp = array[position1];
  array[position1] = array[position2];
  array[position2] = temp;
}
  
function partition(arr, low, high) {
  let pivot = arr[high];
  let i = (low - 1);
  
  for (let j = low; j <= high- 1; j++) {
    if (arr[j] <= pivot) {
      i++; 
      Swap(arr, i, j);
    }
  }
  Swap(arr, i + 1, high);
  return (i + 1);
}
  
function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high) 
      quickSort(arr, low, pi - 1);
      quickSort(arr, pi + 1, high);
  }
  return arr;
}

quickSort(arr, 0, arr.length-1);

Hoare’s Partition Scheme

function partition(arr, low, high) {
  let pivot = arr[low];
  let i = low - 1, j = high + 1;
  
  while (true) {
    do { 
      i++; 
    } while (arr[i] < pivot);
  
    do {
      j--;
    } while (arr[j] > pivot);
  
  if (i >= j) return j;
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
  
function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high);
      quickSort(arr, low, pi);
      quickSort(arr, pi + 1, high);
  }
  return arr;
}
  
quickSort(arr, 0, arr.length - 1);

하이브리드 정렬

팀 정렬

팀 정렬(Tim sort)은 병합 정렬과 삽입 정렬을 합친 것으로 2002년 Tim Peters가 파이썬을 위해 개발하였다. 덕분에 파이썬의 sorted()는 대부분은 가장 빠른 속도로 정렬을 수행할 수 있게 되었다. 팀 정렬은 대부분의 데이터가 이미 정렬되어 있을 것이라는 가정을 바탕으로 병합 정렬을 이용하여 정렬을 수행하지만, 원소의 개수가 적을 때 오버헤드가 발생하기 때문에 파티션 크기가 특정 값 이하(보통 16 또는 32)가 되면 삽입 정렬을 사용하는 방식으로 정렬한다.

안정 정렬 vs 불안정 정렬

출처 Tim sort에 대해 알아보자

위 표와 같이 정렬 알고리즘은 기본적으로 안정 정렬과 불안정 정렬로 나누어지는 것을 볼 수 있다. 안정 정렬은 중복된 값을 입력 순서와 동일하게 정렬하는 방식으로, 만약 어떠한 자료를 시간순으로 정렬한 뒤 지역명 순으로 재정렬하더라도 기존 순서가 유지된 상태로 정렬이 이루어진다. 그러나 불완전 정렬은 재정렬 시 기존의 정렬 순서가 무시되어 모두 섞인다. 이러한 불완전 정렬의 대표적인 예가 바로 퀵 정렬로 입력값의 형태에 따라 속도가 심하게 변화하기 때문에 성능이 고르지 않다는 단점이 있다.

참고
정렬 알고리즘
Tim sort에 대해 알아보자
파이썬 알고리즘 인터뷰
Hoare’s vs Lomuto partition scheme in QuickSort