[Algorithm] 정렬

다양한 정렬 알고리즘에 대해 정리하였습니다.

---

< 버블 정렬(Bubble Sort) >

정렬을 위한 교환 작업이 마치 거품처럼 버블버블 거린다고 해서 버블 정렬이라고 합니다.

 

- Performance : O(n²)

- Space Complexity : O(1)

 

[ 알고리즘 단계 ]

1. 배열을 처음부터 끝까지 순회하며 인접한 두 원소를 비교합니다.
2. 만약 현재 원소가 다음 원소보다 크다면 두 원소의 위치를 서로 교환합니다.
3. 이 과정을 배열의 끝까지 반복하면서 가장 큰 원소가 배열의 마지막으로 이동합니다.
4. 배열의 마지막 원소는 정렬되었으므로, 다시 처음부터 끝까지 반복합니다. 이때는 마지막 원소는 정렬된 상태이므로 제외하고 진행합니다.
5. 위의 과정을 반복하면서 배열이 완전히 정렬될 때까지 진행합니다.

 

function bubbleSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        // 한 번 순회 동안 배열의 가장 큰 값이 끝으로 이동하므로, 마지막 i개의 요소는 정렬된 상태로 간주할 수 있습니다.
        for (let j = 0; j < len - 1 - i; j++) {
            // 현재 원소와 다음 원소를 비교하여 순서가 올바르지 않은 경우 교환합니다.
            if (arr[j] > arr[j + 1]) {
                // 두 원소의 위치를 교환합니다.
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

// 테스트를 위한 예시 배열
const arr = [5, 3, 8, 4, 2];

// 정렬된 배열 출력
console.log(bubbleSort(arr)); // [2, 3, 4, 5, 8]

 

 

---

< 선택 정렬(Selection Sort) >

각 단계에서 리스트에서 최솟값을 "선택"하여 위치를 교환하기 때문에 선택 정렬이라고 합니다.

 

- Worst case Performance : O(n²)

- Best case Performance : O(n²)

- Average case Performance : O(n²)

- Space Complexity : O(1)

 

[ 알고리즘 단계 ]

1. 배열을 처음부터 끝까지 순회하며 자신보다 작은값을 찾으면 해당 값을 현재값과 교환합니다.
2. 다음 원소로 이동하여 위의 과정을 반복합니다. 현재 위치를 다음 위치로 이동하여 리스트를 순회하면서 최솟값을 선택하고 위치를 교환합니다.
3. 리스트의 끝까지 위의 과정을 반복하여 리스트가 정렬될 때까지 진행합니다. 이때, 정렬된 부분은 제외하고 진행합니다.

 

function bubbleSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        // 한 번 순회 동안 배열의 가장 큰 값이 끝으로 이동하므로, 마지막 i개의 요소는 정렬된 상태로 간주할 수 있습니다.
        for (let j = 0; j < len - 1 - i; j++) {
            // 현재 원소와 다음 원소를 비교하여 순서가 올바르지 않은 경우 교환합니다.
            if (arr[j] > arr[j + 1]) {
                // 두 원소의 위치를 교환합니다.
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

// 테스트를 위한 예시 배열
const arr = [5, 3, 8, 4, 2];

// 정렬된 배열 출력
console.log(bubbleSort(arr)); // [2, 3, 4, 5, 8]

 

 

---

< 삽입 정렬(Insertion Sort) >

삽입 정렬은 각 요소를 "삽입"하는 방식으로 정렬을 수행하기 때문에 삽입 정렬이라고 부릅니다.

 

- Worst case Performance : O(n²)

- Best case Performance : O(n)

- Average case  Performance : O(n²)

- Space Complexity : O(1)

 

[ 알고리즘 단계 ]

1. 리스트의 두 번째 요소부터 시작하여 시작 요소 이전의 모든 요소가 정렬된 상태로 간주합니다.
2. 현재 위치의 요소를 적절한 위치에 "삽입"합니다. 이를 위해 현재 위치의 요소를 앞쪽으로 비교해 나가며, 삽입될 위치를 찾습니다.
3. 적절한 위치를 찾으면 현재 요소를 그 위치에 삽입하고, 이후 요소들을 한 칸씩 뒤로 이동시킵니다.
4. 리스트의 모든 요소에 대해 위 단계를 반복합니다. 이 과정을 통해 리스트는 하나씩 정렬되어 가게 됩니다.

 

 

function bubbleSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        // 한 번 순회 동안 배열의 가장 큰 값이 끝으로 이동하므로, 마지막 i개의 요소는 정렬된 상태로 간주할 수 있습니다.
        for (let j = 0; j < len - 1 - i; j++) {
            // 현재 원소와 다음 원소를 비교하여 순서가 올바르지 않은 경우 교환합니다.
            if (arr[j] > arr[j + 1]) {
                // 두 원소의 위치를 교환합니다.
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

// 테스트를 위한 예시 배열
const arr = [5, 3, 8, 4, 2];

// 정렬된 배열 출력
console.log(bubbleSort(arr)); // [2, 3, 4, 5, 8]

 

 

---

< 병합 정렬(Merge Sort) >

배열을 나누고 정렬한 후에 병합하여 최종적으로 정렬된 배열을 얻기 때문에 병합 정렬이라고 부릅니다.

 

- Performance : O(n log n)

- Space Complexity : O(n)

 

[ 알고리즘 단계 ]

1. 정렬할 배열을 절반으로 나눕니다. 이를 계속해서 작은 조각들로 나누어 나갑니다. 배열이 충분히 작아지면 더 이상 나누지 않습니다.
2. 각각의 작은 조각을 정렬합니다. 이때 정렬은 재귀적으로 이루어집니다.
3. 정렬된 작은 조각들을 합쳐 전체 배열을 정렬합니다. 이때 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는데, 작은 값을 차례대로 선택하면서 합칩니다.

 

function mergeSort(arr) {
    // 재귀적으로 배열을 분할하는 함수
    function mergeSortRecursive(arr) {
        if (arr.length <= 1) {
            return arr; // 기저 사례: 배열이 비어있거나 이미 정렬되어 있음
        }

        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid);

        return merge(mergeSortRecursive(left), mergeSortRecursive(right));
    }

    // 두 개의 정렬된 배열을 병합하는 함수
    function merge(left, right) {
        let result = [];
        let leftIndex = 0;
        let rightIndex = 0;

        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] < right[rightIndex]) {
                result.push(left[leftIndex]);
                leftIndex++;
            } else {
                result.push(right[rightIndex]);
                rightIndex++;
            }
        }

        // 남은 요소들을 결과에 추가
        return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
    }

    return mergeSortRecursive(arr);
}

// 예시 배열
const array = [5, 3, 8, 6, 2, 7, 1, 4];
console.log("정렬 전:", array);
console.log("정렬 후:", mergeSort(array));

 

 

---

< 퀵 정렬(Quick Sort) >

다른 정렬 알고리즘들과 비교했을 때 일반적으로 빠른 속도를 보이는 특징이 있기 때문에 퀵 정렬이라고 부릅니다.

 

- Worst case Performance : O(n²)

- Performance : O(n log n)

- Space Complexity : O(n)

 

[ 알고리즘 단계 ]

1. 리스트에서 피벗을 선택합니다. 일반적으로 리스트의 중간 요소를 피벗으로 선택하거나 무작위로 선택합니다.
2. 선택한 피벗을 기준으로 리스트를 두 그룹으로 나눕니다. 피벗보다 작은 요소들은 피벗의 왼쪽으로, 피벗보다 큰 요소들은 피벗의 오른쪽으로 이동시킵니다.
3. 분할된 두 그룹에 대해 재귀적으로 퀵 정렬을 적용합니다. 이렇게 하면 각 그룹 내에서도 피벗을 선택하고, 다시 분할하고, 정렬하는 과정이 반복됩니다. 이 재귀적인 과정은 각 그룹이 정렬되어 최종적으로 전체 리스트가 정렬될 때까지 계속됩니다.
4. 재귀적인 호출이 완료되면, 각 그룹이 정렬된 상태이므로 이를 합병하여 전체 리스트를 완전히 정렬합니다.

 

function quickSort(array) {
    if (array.length <= 1) return array
    
    const pivotIndex = Math.floor(array.length / 2)
    const pivot = array[pivotIndex];
    const left = [];
    const right = [];
    
    for (let i = 0; i < array.length; i++) {
        if (i === pivotIndex) continue;
        else if (array[i] < pivot) left.push(array[i]);
        else right.push(array[i]);
    }
    
    return quickSort(left).concat(pivot, quickSort(right))
}

 

 

---

< 힙 정렬(Heap Sort) >

이 알고리즘이 힙(Heap) 자료 구조를 사용하여 정렬을 수행하기 때문에 힙 정렬이라고 부릅니다.

힙 정렬은 특히 안정적인 시간 복잡도와 낮은 공간 복잡도가 중요한 경우에 유리합니다.

 

- Performance : O(n log n)

- for get root value Performance : O(1)

- Space Complexity : In-Place Algorithm (별도의 메모리 필요하지 않음)

 

 

[ 알고리즘 단계 ]

1. 힙 생성 (Heapify):

• 주어진 배열을 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 만듭니다.
• 최대 힙의 경우, 배열의 모든 요소를 순회하면서 각 요소를 힙에 추가하는 과정을 거칩니다. 이때, 힙의 삽입 연산(heapifyUp)을 사용하여 요소를 추가하면서 최대 힙 속성을 유지합니다.
• 최소 힙의 경우, 마찬가지로 배열의 모든 요소를 순회하면서 각 요소를 힙에 추가하는 과정을 거칩니다. 이때, 힙의 삽입 연산(heapifyUp)을 사용하여 요소를 추가하면서 최소 힙 속성을 유지합니다.
• 이 과정을 거치면 배열의 요소들이 힙 속성을 만족하게 되고, 최대 힙일 경우 루트에는 배열의 최대값이 위치하게 됩니다.

2. 정렬:

• 최대 힙을 구성한 후에는 루트에 있는 최대값을 배열의 가장 마지막 요소와 교환합니다.
• 이후, 힙의 크기를 하나씩 줄이고(마지막 요소를 제외), 배열의 마지막 요소를 제외한 부분에 대해 다시 최대 힙 속성을 유지하도록 재구성합니다.
• 이 과정을 반복하여 배열의 모든 요소가 정렬될 때까지 진행합니다.

3. 정렬된 배열 반환

• 힙 정렬이 완료되면, 정렬된 배열을 반환합니다.

 

// 배열의 두 요소를 교환하는 함수
function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

// 주어진 배열을 힙 정렬하여 반환하는 함수
function heapSort(arr) {
    // 배열을 최대 힙으로 변환
    buildMaxHeap(arr);

    // 배열을 정렬
    for (let i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i); // 최대값(루트)을 배열의 맨 뒤로 이동
        heapifyDown(arr, 0, i); // 힙 크기를 줄이고 최대 힙 속성을 유지
    }

    return arr;
}

// 주어진 배열을 최대 힙으로 변환하는 함수
function buildMaxHeap(arr) {
    const n = arr.length;
    // 배열의 중간부터 시작하여 최대 힙 속성을 유지
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapifyDown(arr, i, n);
    }
}

// 주어진 배열에서 특정 위치의 요소를 아래로 내려가며 최대 힙 속성을 유지하는 함수
function heapifyDown(arr, index, heapSize) {
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    let largest = index;

    // 왼쪽 자식과 비교하여 가장 큰 값을 찾습니다.
    if (leftChildIndex < heapSize && arr[leftChildIndex] > arr[largest]) {
        largest = leftChildIndex;
    }

    // 오른쪽 자식과 비교하여 가장 큰 값을 찾습니다.
    if (rightChildIndex < heapSize && arr[rightChildIndex] > arr[largest]) {
        largest = rightChildIndex;
    }

    // 가장 큰 값이 자신이 아니면 해당 자식과 교환하고 재귀적으로 heapifyDown을 호출합니다.
    if (largest !== index) {
        swap(arr, index, largest);
        heapifyDown(arr, largest, heapSize);
    }
}

// 사용 예제
const array = [12, 11, 13, 5, 6, 7];
console.log(heapSort(array.slice())); // 배열의 복사본을 전달하여 원래 배열이 변하지 않도록 합니다.