선택 정렬(Selection Sort)는 최솟값을 선택해서 가장 앞으로 보내는 방식의 정렬 알고리즘이다.
O(N^2)
let selectionSort = (arr) => {
let minIdx, temp;
for (let i = 0; i < arr.length; i++) {
minIdx = i;
for (let j = i+1; j < arr.length; j++) {
if (arr[minIdx] > arr[j]) {
minIdx = j;
}
}
// 최솟값이 변경되면 swap
if (minIdx !== i) {
temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
return arr;
}
버블 정렬(Bubble Sort)는 옆에 있는 값과 비교해서 더 작은 값을 앞으로 당기는 방식의 정렬 알고리즘이다.
O(N^2)
let BubbleSort = function(arr) {
let temp;
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j+1] < arr[j]) {
temp = arr[j];
arr[j] = arr[j+1]
arr[j+1] = temp;
}
}
}
return arr;
}
삽입 정렬(Insertion Sort)는 각 숫자를 적절한 위치에 삽입하는 방식의 정렬 알고리즘이다. 정렬할 필요가 있을 경우에만 삽입을 진행하기 때문에 대체로 정렬된 상태에 한정해서는 어떤 정렬 알고리즘보다 빠르다.
O(N^2)
let insertionSort = (arr) => {
let temp;
for (let i = 0; i < arr.length; i++) {
let j = i;
while (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
j--;
}
}
return arr;
}