자바스크립트로 정렬 구현하기

버블 정렬

개념

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

let arr = [2,1]를 오름차순으로 정렬하고자 한다.
이 때, arr[0]과 arr[1]을 비교해 arr[0]이 arr[1]보다 더 큰 경우 서로의 자리를 바꾸는 알고리즘이다.
stable

Big O

O(n) ~ O(n^2)

코드

let arr = [1,3,2,10,5];
for(let i=0;i<arr.length;i++){
    for(let j=i;j<arr.length;j++){
        if(arr[i]>arr[j]){
            [arr[i],arr[j]]=[arr[j],arr[i]]
        }
    }
}
console.log(arr)

삽입 정렬

개념

왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 적절한 위치에 삽입되는 알고리즘
stable

Big O

O(n) ~ O(n^2)

코드

let arr = [1,3,2,10,5]; 
for(let i=0;i<arr.length;i++){
  let minIndex = i;
  for(let j=i+1;j<arr.length;j++){
    if(arr[minIndex] > arr[j]) minIndex = j;
  }
  if(minIndex!==i) [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
}
console.log(arr)

선택 정렬

개념

주어진 리스트 중, 최솟값을 찾아 그 값을 i번째 값과 교환한다.
unstable

Big O

O(n^2)

코드

let arr = [1, 3, 2, 10, 5];
for (let i = 1; i < arr.length; i++) {
    let select = arr[i];

    for (let j = i - 1; j >= 0; j--) {
        if (arr[j] > select) {
            arr[j + 1] = arr[j];
        } else {
            break;
        }
        arr[j] = select
    }

}
console.log(arr)

힙 정렬

개념

힙 구조를 통한 정렬(최대 힙/ 최소 힙)
unstable

Big O

O(nlog2n)

코드

let arr = [1,3,2,10,5]; 

function heapSort(arr){
    for(let i=arr.length-1;i>=0;i--){
        arr = heapify(arr,i);

        if(arr[0]>arr[i]){
            [arr[i],arr[0]] = [arr[0],arr[i]]
        }
    }
    return arr
}

function heapify(arr,i){
    let index = parseInt(i/2)-1;

    while(index>=0){
        const left = arr[index*2+1]
        const right = arr[index*2+2]

        if(left >= right && arr[index] < left){
            [arr[index*2+1],arr[index]] = [arr[index],arr[index*2+1]]
        }else if(right > left && arr[index] < right){
            [arr[index*2+2],arr[index]] = [arr[index],arr[index*2+2]]
        }
        index--;
    }
    return arr;
}

console.log(arr)

병합(합병) 정렬

개념

분할 정복 알고리즘 중 하나로, 분할->정복->결합의 단계를 거친다.
stable

Big O

O(nlog2n)

코드

let arr = [1, 3, 2, 10, 5, 2];

function mergeSort(arr) {
    if(arr.length<2) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)

    return merge(mergeSort(left),mergeSort(right))

    function merge(left,right){
        let result = []
        let leftPointer = 0;
        let rightPointer = 0;

        while(leftPointer<left.length && rightPointer<right.length){
            if(left[leftPointer]<right[rightPointer])   {
                result.push(left[leftPointer])
                leftPointer++;
            }else{
                result.push(right[rightPointer])
                rightPointer++;
            }
            console.log(result)
        }
        return [...result,...left.slice(leftPointer),...right.slice(rightPointer)]
    }
}

퀵 정렬

개념

분할 정복 알고리즘 중 하나로, pivot을 기준으로 작은 값들의 배열과 큰 값들의 배열로 분할해 재귀적으로 퀵 정렬을 호출한다.
unstable

Big O

O(nlog2n) ~ O(n^2)

코드

let arr = [1, 3, 2, 10, 5, 2];

function quickSort(arr,left,right){
    if(left >= right){
        return;
    }
    const mid = Math.floor((left+right)/2)
    const pivot = arr[mid]
    const partition = divide(arr,left,right,pivot)

    quickSort(arr,left,partition-1)
    quickSort(arr,partition,right)

    function divide(arr,left,right,pivot){
        while(left <= right){
            while(arr[left] < pivot){
                left++;
            }
            while(arr[right] > pivot){
                right--;
            }
            if(left <= right){
                [arr[left],arr[right]] = [arr[right],arr[left]]
                left++;
                right--;
            }
        }
        return left;
    }
    return arr;
}

quickSort(arr,0,arr.length-1)

기수 정렬

개념

비교를 하지 않고 정렬을 하는 방법으로, 최대 자릿수를 기준으로 최대 자릿수만큼 0~9까지의 버킷에 담는 방식.
unstable

Big O

O(nw)
n: 키의 수
w: 키의 길이

계수 정렬

개념

각 수에 따른 누적 합을 계산하여, 누적 합의 자리에 해당 수를 넣어준다.
unstable

Big O

O(n + k)
k: 최대값
(k가 n보다 클 경우 무한이 될 수도 있다.)