정렬 알고리즘

거품 정렬 (Bubble Sort)

요약

서로 인접한 두 원소의 크기를 비교하고, 조건에 맞지 않는다면 자리를 교환하며 정렬하는 알고리즘입니다.

과정

시간 복잡도

Best Case: O(n) - 개선된 거품 정렬

Worst Case: O(n^2)

공간 복잡도

주어진 배열 안에서 교환으로 정렬이 되므로 O(1).

장점

구현이 매우 간단합니다.

배열 안에서 교환하므로 다른 메모리 공간을 필요로 하지 않는 제자리 정렬입니다.

안정 정렬입니다.

단점

그다지 효율적이지 못합니다.

교환 연산이 많습니다.

코드 구현


// 개선된 Bubble Sort
const bubbleSort = (arr) => {
  let noSwap;
  for (let i = arr.length; i > 0; i--) {
    noSwap = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        noSwap = false;
      }
    }
    if (noSwap) break;
  }
  return arr;
};

선택 정렬 (Selection Sort)

요약

처음에 원소를 넣을 자리는 정해져 있고, 그 자리에 넣을 원소를 선택하는 알고리즘입니다.

과정

시간 복잡도

Best Case, Worst Case: O(n^2)

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

공간 복잡도

주어진 배열 안에서 교환으로 정렬이 되므로 O(1)

장점

알고리즘이 단순합니다.

배열 안에서 교환하므로 다른 메모리 공간을 필요로 하지 않는 제자리 정렬입니다.

안정 정렬입니다.

단점

비효율적입니다.

불안정 정렬입니다.

코드 구현


const selectionSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) min = j;
    }
    if (i !== min) [arr[i], arr[min]] = [arr[min], arr[i]];
  }
  return arr;
};

삽입 정렬 (Insertion Sort)

요약

2번째 원소부터 시작해서 왼쪽 원소들과 비교해서 위치를 지정한 뒤, 지정 위치에 있는 원소를 뒤로 옮기고 삽입하여 정렬하는 알고리즘입니다.

과정

시간 복잡도

Best Case: O(n)

모두 정렬이 되어있는 경우, 한번씩 밖에 비교를 안하기 때문입니다.

Worst Case: O(n^2)

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2

공간 복잡도

주어진 배열 안에서 교환으로 정렬이 되므로 O(1)

장점

알고리즘이 단순합니다.

정렬되어 있는 경우, 매우 효율적입니다.

배열 안에서 교환하므로 다른 메모리 공간을 필요로 하지 않는 제자리 정렬입니다.

안정 정렬입니다.

단점

배열의 길이가 길어질수록 비효율적입니다.

코드 구현


const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let curVal = arr[i];
    let idx = i - 1;
    while (idx >= 0 && arr[idx] > curVal) {
      arr[idx + 1] = arr[idx];
      idx--;
    }
    arr[idx + 1] = curVal;
  }
  return arr;
};

병합 정렬 (Merge Sort)

요약

분할 정복 알고리즘을 사용합니다.

n개의 숫자들을 2개의 부분으로 분할할 수 없을 때까지 분할하고, 각각의 부분을 계속 병합하면서 정렬합니다.

과정

시간 복잡도

O(n * log n)

주어진 데이터(n)들을 완전 분할하기까지 log n개의 호출이 생깁니다.
정렬 자체에 필요한 수행시간은 n
따라서 n * log n
최선이든 최악이든 동일하게 적용됩니다.

공간 복잡도

O(n)

두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요합니다.

장점

최선의 경우에도, 최악의 경우에도 O(nlogn)의 시간이 소요되기 때문에 어떠한 경우에도 좋은 성능을 보장받기 때문에 효율적입니다.

단점

추가 메모리 공간이 필요합니다.

코드 구현


// 병합
const merge = (arr1, arr2) => {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }
  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }

  return result;
};

// 분할
const 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);
};

퀵 정렬 (Quick Sort)

요약

분할 정복 알고리즘입니다.

하나의 배열을 pivot을 기준으로 삼아 두 개의 부분으로 분할하여 한쪽은 pivot보다 작은 것들, 다른 쪽은 pivot보다 큰 것들로 정렬한 다음, 각 부분을 또 계속 분할하면서 정렬하는 방법입니다.

병합 정렬과 같이 분할 정복 알고리즘이 기반이지만 다른 점은 병합 정렬은 하나의 리스트를 절반으로 나누어 분할 정복을 하는데, 퀵 정렬은 pivot의 값에 따라 pivot을 기준으로 나뉜 리스트의 길이가 다를 수 있기 때문에 비균등하게 나뉜다는 것입니다.

일반적으로는 병합 정렬보다 퀵 정렬이 빠릅니다.

과정

시간 복잡도

Best Case: O(n log n)

주어진 데이터(n)들을 완전 분할하기까지 log n개의 호출이 생깁니다.
정렬 자체에 필요한 수행시간은 n
따라서 n * log n

Worst Case: O(n^2)

이미 정렬이 완료된 배열이 주어질 경우, 계속 불균형하게 나누어지므로 n^2입니다.
개선을 위해 pivot을 다른 위치로 뽑아서 할 수 있지만 100퍼센트 방지는 안되므로 O(n^2)이 허용이 안된다면 다른 정렬 방법을 선택해야 합니다.

공간 복잡도

O(logn)

장점

시간 복잡도가 O(nlogn)을 가지는 다른 정렬 알고리즘들 중 가장 빠릅니다.

배열 안에서 교환하므로 다른 메모리 공간을 필요로 하지 않는 제자리 정렬입니다.

단점

불안정 정렬입니다.

정렬된 배열에 한해서는 수행시간이 오래 걸립니다.

코드 구현


const pivot = (arr, start = 0, end = arr.length - 1) => {
  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  let pivot = arr[start]; // 가장 왼쪽을 기준으로 함
  let pivotIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      pivotIdx++;
      swap(arr, pivotIdx, i);
    }
  }
  swap(arr, start, pivotIdx);

  return pivotIdx;
};

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    let pivotIdx = pivot(arr, left, right);
    // pivot은 고정이기 때문에 pivot에 -1, +1
    quickSort(arr, left, pivotIdx - 1); // left
    quickSort(arr, pivotIdx + 1, right); // right
  }
  return arr;
};