💡 자바스크립트 언어로 자료구조 & 알고리즘에 대해 배운 내용을 기록합니다
정렬(Sorting) 은 데이터들을 특정한 순서에 따라 재배치하는 프로세스를 의미합니다
ex)
정렬은 매우 흔한 작업이기 때문에 구현과정을 파악하는 것은 좋은 공부가 될 것 같습니다.
정렬에는 다양한 방식들이 있고, 각각 장점과 단점이 있습니다. 정렬 알고리즘들 중에서 가장 기본적인 버블, 선택, 삽입 정렬이 어떤 방식으로 실행되는지, 자바스크립트 코드로는 어떻게 구현되는지 알아보겠습니다
가장 큰 값이 버블처럼 위로 올라가는 모양을 하게 되는 알고리즘입니다
Pseudocode
function bubbleSort(arr) {
let noSwaps;
for (let i = arr.length; i > 0; i--) {
noSwaps = true;
for (let j = 0; j < i - 1; j++) {
if (arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
noSwaps = false;
}
}
if (noSwaps) break;
}
return arr;
}
가장 작은 값을 탐색한다음 Swap을 통해 앞부분에 배치시키는 정렬방식입니다.
Pseudocode
function selectionSort(arr) {
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}
for (let i = 0; i < arr.length; i++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if (arr[min] !== arr[i]) {
swap(arr, i, min);
}
return arr;
}
배열 두번째 요소부터 모든 요소를 앞부분에 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식의 정렬 알고리즘입니다
Pseudocode
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i];
let targetIdx = 1;
for (let j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
targetIdx = j;
arr[targetIdx + 1] = arr[targetIdx];
}
if (targetIdx) {
arr[targetIdx] = currentVal;
}
}
return arr;
}
지금까지 알아본 3가지 정렬 알고리즘의 시간복잡도는 아래와 같습니다
전반적으로 O(n^2) 의 비효율적인 시간복잡도를 갖습니다.
이미 어느정도 정렬이 되어있는 배열에서 버블 정렬과 삽입 정렬을 실행할 경우, O(n)의 시간복잡도를 갖게됩니다. 선택 정렬의 경우 이미 정렬이 어느정도 되어있다 하더라도 모든 요소들을 순회하면서 최소값을 탐색하게 되므로, 여전히 시간복잡도는 O(n^2)이 됩니다
Visualgo
Sorting Algorithm Animations
Udemy - Javascript Algorithms and Data Structures Masterclass