0. 선택정렬, 버블정렬과 sort메서드
일반적으로 JavaScript를 사용하면서 오름/내림차순 정렬 시 sort메서드를 사용한다.
sort 메서드 사용시 시간복잡도는 O(nlogn)이므로 이중 for문을 사용한 선택/버블정렬의 최선의 경우보다 빠르고 효율적이다.
하지만 기본적인 알고리즘의 정렬 방식을 이해하고 학습하기 위해 사용해 보았다.
1. 선택정렬
가장 작은값, 혹은 가장 큰 값을 맨 앞, 맨 뒤의 값과 위치를 바꾸어준다.
function solution(arr){
let answer=arr;
for(let i=0; i<arr.length; i++){
let idx=i;
for(let j=i+1; j<arr.length; j++){
if(arr[j]<arr[idx]) idx=j;
}
[arr[i], arr[idx]] = [arr[idx], arr[i]];
}
return answer;
}
2. 버블정렬
인접한 두 값을 비교해 오름/내림차순 기준으로 위치를 변경한다.
function solution(arr){
let answer=arr;
for(let i=0; i<arr.length-1; i++){
for(let j=0; j<arr.length-i-1; j++){
if(arr[j]>arr[j+1]){
[arr[j], arr[j+1]]=[arr[j+1], arr[j]];
}
}
}
return answer;
}
3. 삽입정렬
1 <-> 0
2 <-> 1~0
3 <-> 2~0
...
function insertionSort(array) {
const length = array.length;
for (let i = 1; i < length; i++) {
let currentValue = array[i];
let j = i - 1;
while (j >= 0 && array[j] > currentValue) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = currentValue;
}
return array;
}
