정렬 알고리즘
포스트
취소

정렬 알고리즘

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

📊 정렬 알고리즘 비교

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

0️⃣ 시간 복잡도

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

  • O(1): 배열의 크기에 상관없이 동일한 시간이 소요
1
const func = (array, index) => arr[index];
  • O(n): 배열의 크기만큼 시간이 소요
1
2
3
4
5
const func = (array) => {
  for (let i = 0; i < array.length; i++) {
    array[i]++;
  }
};
  • O(n log n): O(log n)은 한 번 탐색할 때마다 절반의 경우를 줄이는 방식으로 계산됨
    단, O(n log n)이므로 입력한 크기 만큼의 시간이 더 소요
1
// 예시 없음...
  • O(n2): 배열의 크기의 제곱만큼의 시간이 소요
1
2
3
4
5
6
7
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️⃣ 안정

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

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

// ...오름차순 정렬

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 모든 정렬 알고리즘이 구현되어 있다고 가정

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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 거품 정렬 ( 우측부터 큰 수 배치 )
 *
 * 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 삽입 정렬
 *
 * 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 삽입 정렬 ( 좌측부터 작은 수 배치 )
 *
 * 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 합병 정렬
 *
 * 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 - 시간 복잡도
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.

Framework & Library & API

자바스크립트 완벽 가이드 8장 정리 ( Function )