해당 포스트는 정렬 알고리즘에 대해 정리한 포스트입니다.
주관적으로 해석한 내용이므로 잘못된 내용이 포함될 수 있습니다.
📊 정렬 알고리즘 비교
이름 | 최선 | 평균 | 최악 | 메모리 | 안정 |
---|---|---|---|---|---|
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)
: 배열의 크기에 상관없이 동일한 시간이 소요
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: