정렬 알고리즘 (Sorting Algorithms)

정렬 알고리즘은 데이터를 특정 순서대로 정리하는 과정입니다. 여기서는 대표적인 정렬 알고리즘들인 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬을 다룹니다.

1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 데이터를 비교하고, 크기가 작은 데이터를 앞으로 이동시키는 과정을 반복하는 방식입니다. 리스트가 정렬될 때까지 이 과정을 반복합니다.


// 버블 정렬 예제 코드 (JavaScript)
function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 두 값 교환
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

버블 정렬은 매우 간단하지만, 시간 복잡도는 O(n²)으로 비효율적입니다. 따라서 작은 데이터셋에 적합합니다.

2. 선택 정렬 (Selection Sort)

선택 정렬은 주어진 리스트에서 가장 작은 값을 찾아 첫 번째 자리로 이동시키고, 그 다음 작은 값을 두 번째 자리에 위치시키는 과정을 반복하는 방식입니다.


// 선택 정렬 예제 코드 (JavaScript)
function selectionSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 두 값 교환
        let temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
    return arr;
}

선택 정렬의 시간 복잡도는 O(n²)으로, 데이터가 많을 경우 비효율적입니다. 하지만 직관적인 구현이 장점입니다.

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 이미 정렬된 리스트에 새로운 데이터를 적절한 위치에 삽입하여 정렬을 유지하는 방식입니다. 작은 데이터셋이나 거의 정렬된 리스트에 적합합니다.


// 삽입 정렬 예제 코드 (JavaScript)
function insertionSort(arr) {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

삽입 정렬의 시간 복잡도는 O(n²)이지만, 거의 정렬된 리스트에 대해서는 더 빠릅니다. 최선의 경우 O(n)입니다.

4. 퀵 정렬 (Quick Sort)

퀵 정렬은 피벗(Pivot)을 기준으로 데이터를 두 그룹으로 나눈 다음, 각각의 그룹을 재귀적으로 정렬하는 방식입니다. 데이터가 무작위로 섞여 있으면 매우 효율적입니다.


// 퀵 정렬 예제 코드 (JavaScript)
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivot = arr[Math.floor(arr.length / 2)];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (i === Math.floor(arr.length / 2)) continue;
        if (arr[i] < pivot) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

퀵 정렬의 평균 시간 복잡도는 O(n log n)이지만, 최악의 경우 O(n²)이 될 수 있습니다.

5. 병합 정렬 (Merge Sort)

병합 정렬은 리스트를 절반으로 나누고, 각각을 정렬한 후 병합하는 방식입니다. 퀵 정렬과는 달리 안정적인 정렬 알고리즘입니다.


// 병합 정렬 예제 코드 (JavaScript)
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    let left = mergeSort(arr.slice(0, mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return result.concat(left, right);
}

병합 정렬의 시간 복잡도는 항상 O(n log n)입니다. 다만, 추가적인 메모리 공간이 필요합니다.

6. 힙 정렬 (Heap Sort)

힙 정렬은 힙(Heap) 자료구조를 사용하여 데이터를 정렬하는 방식입니다. 힙은 완전 이진 트리 형태를 갖추고 있으며, 최대값 또는 최소값을 빠르게 찾을 수 있습니다.


// 힙 정렬 예제 코드 (JavaScript)
function heapify(arr, length, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < length && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < length && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, length, largest);
    }
}

function heapSort(arr) {
    let length = arr.length;

    // 힙 구성
    for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
        heapify(arr, length, i);
    }

    // 정렬
    for (let i = length - 1; i >= 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
    return arr;
}

힙 정렬의 시간 복잡도는 O(n log n)으로 안정적인 성능을 보입니다. 추가 메모리가 거의 필요하지 않습니다.

DAILY IS COMING

정렬 알고리즘 요약