자바스크립트 정렬 구현하기, 특징 정리, 시간복잡도(버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 병합정렬)

정렬의 원리가 궁금하신 분은 제 깃허브를 참고하시길 바랍니다.

또는 자바로 구현된 정렬 소스를 원하시는 경우에도 깃허브를 참고하시길 바랍니다.

https://github.com/donghyeon0725/algorithm_java/blob/master/src/com/algorithm/sort/README.md

donghyeon0725/algorithm_java

 

버블 정렬 

function bubble(arr) {
    for (let i=0; i<arr.length; i++) {
        for (let j=0; j<arr.length - (i + 1); j++) {
            if (arr[j] > arr[j + 1]) {
                // swap
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }

    return arr;
}

let arr = [13,5,11,7,23,15,1,3,4,6,8];
console.log(bubble(arr));

• 인접한 두 값을 비교합니다.
• 시간복잡도 : O(n^2)

 

선택정렬

function select(arr) {

    let idx = 0;
    for (let i=0; i<arr.length-1; i++) {
        let min = Number.MAX_SAFE_INTEGER;

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

let arr = [13,5,11,7,23,15,1,3,4,6,8];
console.log(select(arr));

• 1개를 정렬할 때마다, 배열 한바퀴를 모두 돌아 가장 작은 값을 찾아서 현재 가리키고 있는 자리에 값을 변경하는 방법
• 시간 복잡도는 버블정렬과 동일하나 실측 속도는 더 빠르다. => 값의 교체가 일어나는 회수가 덜하기 때문
• 시간복잡도 : O(n^2)

 

삽입정렬

function insert(arr) {

    // 정렬 시작의 범위
    for (let i=1; i<arr.length; i++) {
        let j = i;
        while (j > 0 && (arr[j] < arr[j-1])) {
            [arr[j], arr[j-1]] = [arr[j-1], arr[j]];
            j--;
        }
    }

    return arr;
}

let arr = [13,5,11,7,23,15,1,3,4,6,8];
console.log(insert(arr));

• 범위를 점점 넓혀가며 계속 정렬을 수행함. 범위가 넓어짐에 따라서 정렬되지 않은 값이 범위 내부로 들어왔을 때, 해당 값이 알맞은 자리에 찾아갈때까지 계속 정렬을 수행함. 제자리를 찾는다면 범위를 넓힘 => 제 깃허브 그림으로 보시면 이해가 쉬우실거에요.
• 시간 복잡도가 O(n^2) 이긴 하나, 거의 정렬 되어 있는 배열을 정렬할 때 버블 & 선택정렬 알고리즘보다 빠름
• 시간복잡도 : O(n^2)

 

 

퀵정렬

function quick(arr, start, end) {
    if (start >= end) return;

    let pivot = arr[end];
    let left = start, right = end;

    // 엇갈리지 않은 동안만
    while (left < right) {
        // 피벗보다 큰 값을 찾는다.
        while (arr[left] <= pivot && left < end) {
            left++;
        }

        // 피벗보다 작은 값을 찾는다.
        while (arr[right] >= pivot && right > start) {
            right--;
        }

        // 엇갈리지 않은 경우
        if (left < right)
            [arr[left], arr[right]] = [arr[right], arr[left]];
        // 엇갈린 경우 left와 pivot을 교환
        else
            [arr[left], arr[end]] = [pivot, arr[left]];

    }

    quick(arr, start, right);
    quick(arr, left, end);
}

let arr = [13,5,11,7,23,15,1,3,4,6,8];
quick(arr, 0, arr.length - 1);
console.log(arr);

• 피벗을 하나 정하고 그 피벗보다 큰값과 작은 값을 하나씩 선택해 두 값의 자리를 교체하는 방법
• 피벗이 엇갈리면 피벗의 위치를 중간으로 옮기고 다시 양쪽으로 정렬을 수행함
• n 크기의 배열에 대해 log n 번 정렬을 수행하므로 시간복잡도는 O (n * log n)
• 허나 이는 피벗의 크기가 한쪽으로 치우칠 경우 O (n ^ 2) 의 시간복잡도에 가깝게 된다는 단점이 있음

 

 

 

병합정렬

function mergeSort(arr, start, end) {
    // 크기가 1이 될때까지 계속 쪼갠 뒤, 병합
    if (start < end) {
        let half = Math.floor((start + end)/2);
        // 나늠
        mergeSort(arr, start, half);
        mergeSort(arr, half+1, end);
        // 나눈 두 배열을 병합 => 작은 배열을 먼저 정렬함
        merge(arr, start, end);
    }
}

function merge(arr, start, end) {

    let half = Math.floor((start + end ) / 2);
    let left = start, right = half + 1
    let idx = start;

    // 한쪽 인덱스가 먼저 끝이 나면
    while (left <= half && right <= end) {

        if (arr[left] > arr[right])
            temp1[idx++] = arr[right++];
        else
            temp1[idx++] = arr[left++];

    }

    // 좌측 인덱스가 아직이면
    while (left <= half) {
        temp1[idx++] = arr[left++];
    }

    // 우측 인덱스가 아직이면
    while (right <= end) {
        temp1[idx++] = arr[right++];
    }

    // 배열을 옮김
    for (let i=start; i<=end; i++) {
        arr[i] = temp1[i];
    }
}


let arr = [13,5,11,7,23,15,1,3,4,6,8];
// 정렬할 배열과 크기가 동일한 배열 생성 => 병합정렬을 위함
let temp = Array.from({arr:length});

mergeSort(arr, 0, arr.length - 1);
console.log(arr);

• 별도의 배열공간을 하나 더 만들어서 배열의 크기가 1이 될때까지 쪼갠다 (실제로 쪼개는 것이 아닌, 가상으로 범위를 잡은 것). 이것을 재귀 호출을 이용해서 구현한다.
• 쪼갠 배열을 인접한 배열 2개씩 묶어서 정렬을 수행한다. 이때, 정렬은 투포인터 알고리즘을 사용한다. (두개 비교해서 작은 것 먼저 순서대로 배열에 들어간다고 보면 됨 => 배열이 모두 정렬되어 있기 때문에 가능함)
• 시간복잡도 : O(n * log n)