Basic sorting algorithms

July 1, 2018 - 5 minute read -
알고리즘

Bubble / Insertion / Merge/ Quick / Selection

그냥 한 번쯤은 구현 해보고 싶었다.

Bubble sort

function bubbleSort(a) {
	for (let i = 0; i < a.length - 1; i++) {
            for (let x = 0 ; x < a.length - 1 - i; x++) {
                if (a[x] > a[x + 1]) {
                    let temp = a[x];
                    a[x] = a[x + 1];
                    a[x + 1] = temp;
                }
            }
        }
}
  • 인접한 두 수를 비교한다. 간단하게 구현 할 수 있으나, 비효율적임.
  • O(n^2)



Insertion

function insertionSort(a) {
    for (let i = 1 ; i < a.length; i++) {
        let selection = a[i];
        let x = i;
        while(1) {
            x--;
            if (x < 0 || selection > a[x]) {
                x++;
                break;
            }
            a[x + 1] = a[x];
        }
        a[x] = selection;
    }
console.log(a);
}



Merge

function mergeSort(a) {
    if (a.length <= 1) {
        return a;
    }
    let half = Math.floor(a.length / 2);
    let arrayOne = mergeSort(a.slice(0, half));
    let arrayTwo = mergeSort(a.slice(half, a.length));

    return merge(arrayOne, arrayTwo);
}
function merge(a, b) {
    let mergedArr = [];
    while (a.length && b.length) {
        if (a[0] < b[0]) {
            mergedArr.push(a.shift());
        } else {
            mergedArr.push(b.shift());
        }
    }

    while (a.length || b.length) {
        if (a.length) {
            mergedArr.push(a.shift());
        }
        if (b.length) {
            mergedArr.push(b.shift());
        }
    }

    return mergedArr;
}



Quick

function quickSort(arr) {
    quickSortHelper(arr, 0, arr.length - 1);
    return arr;
}

function quickSortHelper(arr, left, right) {
    if (left >= right) {
        return ;
    }

    let partitionIdx = partition(arr, left, right);
    quickSortHelper(arr, left, partitionIdx - 1);
    quickSortHelper(arr, partitionIdx + 1, right);

}

function partition(arr, left, right) {
    let pivot = arr[right];
    let pivotIdx = left;

    for (; left < right; left++) {
        let current = arr[left];
        if (current < pivot) {
            swap(arr, left, pivotIdx);
            pivotIdx++;
        }
    }

    swap(arr, pivotIdx, right);

    return pivotIdx;
}

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
  • https://www.youtube.com/watch?v=7BDzle2n47c
  • 추가적인 메모리가 필요없고 속도가 빠른편에 속한다. 정렬의 기준이 되는 pivot 값이 재수없게 가장 큰 수나 가장 작은 수로 계속 정해지거나, 이미 정렬된 상태라면 O(n^2)까지 걸릴 수 있다. 세 수를 뽑아 가운데 수를 pivot으로 정하는 등의 방법으로 리스크를 줄일 수 있다.
  • O(nlogn)



Selection

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let miniIdx = i;
        for (let x = i; x < arr.length; x++) {
            if (arr[miniIdx] > arr[x]) {
                miniIdx = x;
            }
        }
        swap(arr, miniIdx, i);
    }
    return arr;
}

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}