정렬 알고리즘 (N^2)

버블 정렬

두 인접한 원소를 비교하여 정렬하는 방법이다.

작동 과정

1. 배열의 길이가 N일 때, 1부터 N-1번 원소까지 이전의 원소와 비교하여 더 크다면/작다면 위치를 교환한다.
2. 위 과정을 N번 반복한다.

특징

1. 코드가 단순하다.
2. 추가적인 메모리 공간이 필요하지 않다.
3. 안정 정렬로 동작한다.

코드

JavaScript (오름차순)

function bubbleSort(array) {
    const N = array.length;

    for (let i = 0; i < N; i++) {
        for (let j = 1; j < N; j++) {
            if (array[j] < array[j - 1]) {
                swap(array, j, j - 1);
            }
        }
    }
}

function swap(array, aIdx, bIdx) {
    const temp = array[aIdx];
    array[aIdx] = array[bIdx];
    array[bIdx] = temp;
}

선택 정렬

작동 과정

1. 모든 원소 중 가장 낮은/높은 원소를 골라 가장 앞에 위치 시킨다.
2. 정렬이 완료된 맨 앞 원소를 제외한 나머지 원소 중 가장 낮은/높은 원소를 골라 두 번째에 위치시킨다.
3. 모든 원소에 대해 위 과정을 반복한다.

특징

1. 추가적인 메모리가 필요하지 않다.
2. 불안정 정렬로 동작한다.

코드

Javascript (오름차순)

function selectionSort(Array) {
    const N = Array.length;

    for (let i = 0; i < N; i++) {
        let min = Number.MAX_SAFE_INTEGER;
        let minIdx;
        for (let j = i; j < N; j++) {
            if (min > Array[j]) {
                min = Array[j];
                minIdx = j;
            }
        }

        swap(Array, i, minIdx);
    }
}

function swap(array, aIdx, bIdx) {
    const temp = array[aIdx];
    array[aIdx] = array[bIdx];
    array[bIdx] = temp;
}

삽입 정렬

동작 과정

1. 두 번째 원소부터 해당 원소의 앞에 존재하는 원소들의 부분 배열에서 삽입될 위치를 검색한다.
2. 해당 위치에 원소를 삽입한다.
3. 마지막 원소까지 반복한다.

특징

1. 추가적인 메모리가 필요하지 않다.
2. 안정 정렬로 동작한다.
3. 이미 정렬되어 있는 경우 최선의 경우로 $O(N)$의 시간복잡도.

코드

JavaScript (오름차순)

function insertionSort(Array) {
    const N = Array.length;

    for (let i = 1; i < N; i++) {
        const key = Array[i];
        let insertIdx = i - 1;

        while(insertIdx >= 0 && Array[insertIdx] > key) {
            Array[insertIdx + 1] = Array[insertIdx];
            insertIdx--;
        }

        Array[insertIdx + 1] = key;
    }
}

function swap(array, aIdx, bIdx) {
    const temp = array[aIdx];
    array[aIdx] = array[bIdx];
    array[bIdx] = temp;
}