정렬 알고리즘

해당 포스트는 정렬 알고리즘에 대해 정리한 포스트입니다.
주관적으로 해석한 내용이므로 잘못된 내용이 포함될 수 있습니다.

📊 정렬 알고리즘 비교

이름	최선	평균	최악	메모리	안정
Bubble Sort	O(n)	O(n2)	O(n2)	O(1)	O
Insertion Sort	O(n)	O(n2)	O(n2)	O(1)	O
Selection Sort	O(n2)	O(n2)	O(n2)	O(1)	X
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	O
Heap Sort	O(n)	O(n log n)	O(n log n)	O(1)	X
Quick Sort	O(n log n)	O(n log n)	O(n2)	O(log n)	X

0️⃣ 시간 복잡도

실제 시간을 측정하는 것이 아닌 얼마나 많은 단계가 있는지 측정하는 방법을 의미합니다.

• O(1): 배열의 크기에 상관없이 동일한 시간이 소요

const func = (array, index) => arr[index];

• O(n): 배열의 크기만큼 시간이 소요

const func = (array) => {
  for (let i = 0; i < array.length; i++) {
    array[i]++;
  }
};

• O(n log n): O(log n)은 한 번 탐색할 때마다 절반의 경우를 줄이는 방식으로 계산됨
  단, O(n log n)이므로 입력한 크기 만큼의 시간이 더 소요

// 예시 없음...

• O(n2): 배열의 크기의 제곱만큼의 시간이 소요

const func = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      array[i]++;
    }
  }
};

1️⃣ 메모리

정렬하는데 사용되는 메모리를 의미합니다.
O(1)의 경우 추가적인 메모리를 소모하지 않는 것을 의미하고, O(n)은 배열의 크기만큼 추가적인 메모리를 사용한다는 의미입니다.

( ex) Merge Sort의 경우 배열이 하나가 될 때까지 계속 쪼개기 때문에 배열의 크기만큼의 추가적인 메모리가 소모됩니다. )

2️⃣ 안정

동일한 키 값이 있는 경우 정렬후에 순서가 유지되는지 여부입니다.

const arr = [5, 4, 4, 3, 2, 1];

// ...오름차순 정렬

// arr[1]에 있는 4와 arr[2]에 있는 4의 위치가 바뀌지 않으면 "안정" / 바뀌면 "불안정"
// [1, 2, 3, 4, 4, 5]

3️⃣ 역순으로 정렬된 경우 시간 비교

// 모든 정렬 알고리즘이 구현되어 있다고 가정

console.time("역정렬된 배열 생성 시간");
const arr = Array(100_000)
  .fill(null)
  .map((v, i) => i)
  .reverse();
console.timeEnd("역정렬된 배열 생성 시간");

console.time("Selection Sort");
selectionSort(arr);
console.timeEnd("Selection Sort");

console.time("Bubble Sort");
bubbleSort(arr);
console.timeEnd("Bubble Sort");

console.time("Insertion Sort");
insertionSort(arr);
console.timeEnd("Insertion Sort");

console.time("Merge Sort");
mergeSort(arr);
console.timeEnd("Merge Sort");

/**
 * "0 ~ 99,999"이 역순으로 정렬된 배열
 * 단위: "ms"
 * 
 * 역정렬된 배열 생성 시간: 3
 * Selection Sort: 6600
 * Bubble Sort: 13300
 * Insertion Sort: 10500
 * Merge Sort: 300
 */

📉 난이도 下

0️⃣ 거품 정렬 ( Bubble Sort )

좌측부터 인접한 값 두 개를 비교해서 우측이 더 크면 교환을 반복합니다.
한 번 순회하면 가장 우측에 가장 큰 수가 들어가고 그 반복을 요소의 개수만큼 실행해서 정렬하는 방식입니다.
( 한 번 순회할 때마다 반복 횟수 -1 ( 가장 우측에 가장 작은 수가 들어가 있기 때문 ) )

/**
 * 거품 정렬 ( 우측부터 큰 수 배치 )
 *
 * 1. 인접한 두 수를 비교해서 작은 것을 좌측으로 큰 것을 우측으로 이동
 * 2. "1"을 length - n번 반복
 *
 * @param { number[] } array 숫자 배열
 * @returns { number[] } 오름차순으로 정렬된 배열
 */
const bubbleSort = (array) => {
  const sortedArray = [...array];

  // 전체 순회
  for (let index = 0; index < sortedArray.length; index++) {
    // 부분 순회 ( 0 ~ length, 0 ~ length -1, ... ) ( 한 번 순회할 때마다 우측에 최댓값 )
    for (let i = 0; i < sortedArray.length - index; i++) {
      // 좌/우측 비교 후 좌측이 더 크다면 우측과 교환
      if (sortedArray[i] > sortedArray[i + 1]) {
        [sortedArray[i], sortedArray[i + 1]] = [sortedArray[i + 1], sortedArray[i]];
      }
    }
  }

  return sortedArray;
};

1️⃣ 삽입 정렬 ( Insertion Sort )

좌측부터 우측으로 하나씩 본인의 크기에 맞는 위치로 이동시킵니다.
우측 끝까지 반복하면 모두 정렬이 됩니다.

/**
 * 삽입 정렬
 *
 * 1. 좌측에서 우측으로 가면서 각 요소에 맞는 위치로 삽입
 *
 * @param { number[] } array
 * @returns { number[] } 오름차순으로 정렬된 배열
 */
const insertionSort = (array) => {
  const sortedArray = [...array];

  // 좌측에서 우측
  for (let index = 1; index < sortedArray.length; index++) {
    let currentValue = sortedArray[index];
    let left = index - 1;

    // 좌측 값이 더 크다면 좌측 우측 교환 ( 제일 왼쪽까지, 우측이 더 클 때까지  )
    while (left >= 0 && sortedArray[left] > currentValue) {
      [sortedArray[left + 1], sortedArray[left]] = [sortedArray[left], sortedArray[left + 1]];
      left--;
    }
  }

  return sortedArray;
};

2️⃣ 선택 정렬 ( Selection Sort )

모두 순회한 후 최솟값을 찾고 맨 앞의 값과 교환을 계속 반복하면서 정렬하는 방법입니다.
( 한 번 순회할 때마다 반복 횟수 -1 ( 가장 좌측에 가장 작은 수가 들어가 있기 때문 ) )

/**
 * 삽입 정렬 ( 좌측부터 작은 수 배치 )
 *
 * 1. 0 ~ length 순회 후 최솟값 찾고 첫 번째 값과 교환
 * 2. 1 ~ length 순회 후 최솟값 찾고 두 번째 값과 교환
 * 3. ...
 * 4. length - 1 ~ length 순회 후 최솟값 찾고 첫 번째 값과 교환
 *
 * @param { number[] } array 숫자 배열
 * @returns { number[] } 오름차순으로 정렬된 배열
 */
const selectionSort = (array) => {
  const sortedArray = [...array];

  let minIndex = null;
  // 전체 순회
  for (let index = 0; index < sortedArray.length; index++) {
    minIndex = index;

    // 부분 순회 ( 0 ~ length, 1 ~ length, ... ) ( 한 번 순회할 때마다 좌측에 최솟값 )
    for (let i = index; i < sortedArray.length; i++) {
      // 최솟값 찾기
      if (sortedArray[minIndex] > sortedArray[i]) minIndex = i;
    }

    // 최솟값 맨 앞으로 이동
    [sortedArray[index], sortedArray[minIndex]] = [sortedArray[minIndex], sortedArray[index]];
  }

  return sortedArray;
};

📈 난이도 上

0️⃣ 합병 정렬 ( Merge Sort )

1개가 될 때까지 배열을 절반으로 나눕니다.
1개가 되면 이전에 나눈 배열과 비교해서 오름차순으로 정렬합니다.
오름차순으로 정렬하는 과정을 모든 배열이 합쳐질 때까지 반복합니다.

/**
 * 합병 정렬
 *
 * 1. 배열을 절반으로 나눈다.
 * 2. 배열에 요소가 하나가 남을 때까지 "1"을 재귀적으로 반복한다. ( 트리 형태로 )
 * 3. 배열에 요소가 하나 남는다면 이전에 나눴던 요소와 비교해 오름차순으로 정렬한다.
 * 4. 오름차순으로 정렬한 배열들끼리 다시 좌측부터 비교하면서 오름차순으로 정렬한다.
 * 5. 나눴던 모든 배열에 "4"를 적용해서 정렬된 하나의 배열을 만든다.
 */

/**
 * 배열을 절반으로 나눈다.
 * 만약 요소가 하나라면 이전 요소와 비교해 합친다.
 *
 * @param { number[] } left
 * @param { number[] } right
 */
const merge = (left, right) => {
  // "undefined"와 비교한다면 원래 배열 반환
  if (!left || !right) return [...left, ...right];

  const tempArray = [];

  // 좌측이나 우측이 0개가 될 때까지 비교 후 "tempArray"에 추가
  while (left.length !== 0 && right.length !== 0) {
    if (left[0] > right[0]) {
      tempArray.push(right.shift());
    } else {
      tempArray.push(left.shift());
    }
  }

  // 한쪽이 다 끝났다면 나머지 그대로 삽입 ( 어차피 오름차순으로 정렬되어있기 때문에 그대로 넣어도 상관 없음 )
  return [...tempArray, ...left, ...right];
};
/**
 * 재귀적으로 "mergeSort()"를 호출한다.
 * 내부적으로 "merge()"를 호출한다.
 *
 * @param { number[] } array
 */
const mergeSort = (array) => {
  // 배열의 요소가 하나 남을 때까지 반으로 나눈다.
  if (array.length === 1) return array;

  // 배열이 1개가 될 때까지 절반으로 나눔
  const mid = array.length / 2;
  const left = array.slice(0, mid);
  const right = array.slice(mid);

  // 재귀적으로 호출해서 1개가 되면 "merge()" 수행
  return merge(mergeSort(left), mergeSort(right));
};

1️⃣ 힙 정렬 ( Heap Sort )

TODO:

2️⃣ 퀵 정렬 ( Quick Sort )

TODO:

📮 레퍼런스

1. naver d2 - Tim sort에 대해 알아보자
2. 노마드 코더 - Big O
3. hanamon - 시간 복잡도