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

wkahd01·2022년 1월 11일
1

알고리즘

목록 보기
23/24

버블 정렬

개념

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

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

왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여

코드

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)

삽입 정렬

개념

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

코드

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)

선택 정렬

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

for (let i = 0; i < arr.length; i++) {
    let min = arr[i];
    for (let j = i; j < arr.length; j++) {
        if (arr[j] < min) {
            [arr[i],arr[j]] = [arr[j], arr[i]]
        }
    }
}
console.log(arr)

힙 정렬

추후 작성 예정

병합(합병) 정렬

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)]
    }
}

퀵 정렬

기수 정렬

계수 정렬

profile
꾸준하게 공부하기

0개의 댓글