JavaScript
javascript 정렬 알고리즘
citron031
2022. 11. 17. 12:14
정렬 알고리즘으로 버블, 선택, 삽입, 퀵, 합병 정렬을 배웠었다.
하지만, C언어로만 이 코드들을 작성했었기에 자바스크립트로도 정렬 알고리즘을 기록하기로 하였다.
물론, 자바스크립트에서는 arr.sort((a, b) => a - b) 알고리즘으로 손쉽게 배열을 정렬할 수 있다.
🍇 버블 정렬
- 가장 쉽게 생각할 수 있는 정렬 방법으로 앞뒤의 숫자를 비교하여 정렬이 필요하다면, 앞뒤의 숫자를 바꾼다.
- 이미 정렬된 상태라면, 중간에 반복문을 중단할 수 있다.
- 평균적으로 O(N^2) 시간복잡도를 가진다. (큰 배열을 정렬할 때 부적합하다)
const bubbleSort = function (arr) {
let sorted;
for(let i = 0; i < arr.length; i++){
sorted = false;
for(let j = 0; j < arr.length - i; j++){
if(arr[j + 1] < arr[j]){
sorted = true;
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]] // 위치 변경
}
}
if(sorted === false) // 이미 모두 정렬된 상태
return arr;
}
return arr;
};
🍉 선택 정렬
- 배열에서 가장 큰 원소를 찾아내어 뒤로 보내거나, 가장 작은 원소를 찾아내어 앞으로 보내는 방식으로 정렬한다.
- 평균적으로 O(N^2) 시간복잡도를 가진다.
const selectionSort = (arr) => {
let i;
for(i = arr.length - 1; i >= 0; i--) {
// 가장 큰 것을 찾아내 가장 뒤로 보낸다.
let maxIndex = 0;
for (let j = 1; j <= i; j++) {
// 가장 큰 것 찾기
if (arr[maxIndex] < arr[j])
maxIndex = j;
}
// 교체
if (maxIndex != i) {
[arr[i], arr[maxIndex]] = [arr[maxIndex], arr[i]];
}
}
return arr;
}
🥬 삽입 정렬
- 앞에서 부터 하나씩 삽입하는 느낌으로 정렬을 하는 알고리즘이다.
- 새로 정렬 배열에 삽입되는 원소는 차례대로 비교를 하여 위치를 찾아간다.
- 평균적으로 O(N^2) 시간복잡도를 가진다.
- 이미 정렬이 많이 된 배열이라면, 빠르게 정렬할 수 있다.
- 이미 정렬이 된 배열에서 삽입 정렬의 시간복잡도는 O(N)이다.
- 하지만, 최악의 경우에는 모든 배열을 뒤집어야 할 수도 있다.
const insertionSort = function (arr) {
for(let i = 1; i < arr.length; i++){
let j = i - 1;
let save = arr[i]; // 새로 삽입되는 원소
while(j >= 0 && arr[j] > save){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = save; // 자신의 위치를 찾았다.
}
return arr;
};
🍄 퀵 정렬
- 현재 알려진 가장 빠른 정렬 알고리즘이다.
- 임의의 피봇을 하나 정한 뒤 그 원소를 기준으로 큰 원소를 지닌 배열, 작은 원소를 지닌 배열, 피봇과 값이 같은 원소를 가진 배열을 나눈다.
- 그리고 그 나뉜 배열을 대상으로 다시 피봇을 정하고 값의 크기에 따라 배열을 나누는 것을 반복한다.
- 그리고 정리된 배열들을 순서대로 합치면 결과적으로 정렬이 완료된 배열을 얻을 수 있다.
- 평균적으로 O(NlogN) 시간복잡도를 가진다.
const quickSort = (arr) => {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0]; // 임의의 피봇
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) { // 피봇을 제외한 나머지를 피봇과 비교,
if (arr[i] < pivot)
left.push(arr[i]); // 피봇보다 작음
else
right.push(arr[i]); // 피봇보다 큼
}
const leftArr = quickSort(left);
const rightArr = quickSort(right);
return leftArr.concat(pivot, rightArr); // 정렬된 값들을 모두 합쳐 리턴
}🧀 합병 정렬
- 배열을 쪼갠 뒤, 이 배열들을 합치면서 정렬을 해나가는 알고리즘이다.
- 원소를 하나만 가지는 배열부터 시작하여 점점 배열을 합쳐나간다.
- 평균적으로 O(NlogN) 시간복잡도를 가진다.
- 재귀적으로 배열을 쪼개기 때문에 메모리 사용이 많다.
const mergeSort = function (arr) {
let mergeArr = arr.map(el => [el]); // 원소가 하나인 정렬된 부분 리스트가 된다.
while (mergeArr.length !== 1) {
// 하나의 배열이 남을 때 까지 병합을 반복한다.
let tmp = [];
while(mergeArr.length !== 0){
let first = mergeArr.pop();
if(mergeArr.length === 0){
tmp.push(first); // 원소의 개수가 홀수, 마지막 하나 남음
break;
}
let second = mergeArr.pop();
tmp.push(merge(first, second));
}
mergeArr = tmp; // 갱신
}
return mergeArr[0];
};
function merge(arr1, arr2) {
let arr = [];
let i = 0,
j = 0;
while (i !== arr1.length && j !== arr2.length) {
if (arr1[i] > arr2[j]) {
arr.push(arr2[j]);
j++;
} else {
arr.push(arr1[i]);
i++;
}
}
// 남은 배열 붙이기
while (i !== arr1.length) {
arr.push(arr1[i]);
i++;
}
while (j !== arr2.length) {
arr.push(arr2[j]);
j++;
}
return arr;
}
🐬 자바스크립트 배열 고차함수 사용하기
const arr = [1, 25, 3, -4, 0, 13];
arr.sort((a, b) => a - b); // 오름차순 정렬
console.log(arr);
const arr2 = ['lee', 'park', 'kim', 'jamie', 'steve'];
arr2.sort(); // 알파벳 순서대로 정렬
console.log(arr2);다만, sort 함수는 원본 배열을 수정하여 사이드 이펙트가 발생할 우려가 있다.
---- New ✨ ----
이런 이유로 ES2023에서 새로이 등장한 toSorted가 있다.
const arr = [1, -34, 2, 0, 11, -35];
const arr2 = arr.toSorted((a, b) => a - b);
console.log(arr); // [1, -34, 2, 0, 11, -35]
console.log(arr2); // [-35, -34, 0, 1, 2, 11]다만 최신문법이므로 런타임 환경에 호환되는지 확인 후 사용하도록 하자.