정렬 알고리즘이란?

정렬 (Sorting) 이란? : 데이터를 일정한 순서로 배열

정렬은 데이터를 특정한 조건에 따라 일정한 순서로 다시 배열 하는 작업입니다. 숫자나 알파벳으로 이루어진 데이터셋을 오름차순 또는 내림차순으로 배열하는 것이기도 합니다. 이런 작업은 많은 컴퓨터, 과학 문제에서 핵심적인 역할을 합니다. 

정렬의 중요한 역할: 탐색 도움

데이터가 정렬되어 있다면 바이너리 탐색과 같은 효율적인 탐색 알고리즘을 사용할 수 있습니다. 바이너리 탐색은 데이터가 이미 정렬되어 있을 때, 중간 값과 비교하여 탐색 범위를 반으로 줄여가며 빠르게 원하는 값을 찾아내는 알고리즘입니다. 따라서 정렬된 데이터는 탐색 시간을 크게 단축시켜줍니다.

 

정렬 알고리즘의 종류

1. 버블 소트 (Bubble Sort): 인접한 두 원소를 비교하고 필요에 따라 위치를 교환하는 방식으로 동작합니다. 가장 간단하면서도 비효율적인 정렬 알고리즘 중 하나입니다. 인접한 두 원소를 비교하며 필요에 따라 위치를 교환하는 방식으로 동작합니다. 한 번의 회전이 끝나면 가장 큰 원소가 마지막 위치로 이동합니다.

예시코드 c++ :

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                // swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

 

예시코드 jsp :

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

// Example usage:
const bubbleSortedArray = bubbleSort([64, 34, 25, 12, 22, 11]);
console.log("Bubble Sorted Array:", bubbleSortedArray);

2. 셀렉션 소트 (Selection Sort): 주어진 리스트에서 최소값을 찾아 맨 앞으로 이동시키는 방식을 반복하여 정렬하는 알고리즘입니다. 간단하고 구현이 쉽지만, 정렬해야 할 리스트의 크기가 크면 성능이 떨어집니다.

예시코드 c++ :

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        // swap arr[minIndex] and arr[i]
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

예시코드 jsp :

function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // swap arr[minIndex] and arr[i]
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
}

// Example usage:
const selectionSortedArray = selectionSort([64, 34, 25, 12, 22, 11]);
console.log("Selection Sorted Array:", selectionSortedArray);

 

3. 퀵 소트 (Quick Sort): 분할 정복 방식을 사용하여 리스트를 정렬하는 빠르고 효율적인 알고리즘입니다. 피벗을 선택하고, 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어가며 정렬합니다. 평균적으로 높은 성능을 보이며 많은 언어에서 기본 정렬 라이브러리에 사용됩니다. 

예시코드 c++:

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low-1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // swap arr[i+1] and arr[high]
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i+1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

 

예시코드 jsp : 

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const pivot = arr[0];
    const left = [];
    const right = [];

    for (let i = 1; i < arr.length; i++) {
        arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
    }

    return quickSort(left).concat(pivot, quickSort(right));
}

// Example usage:
const quickSortedArray = quickSort([64, 34, 25, 12, 22, 11]);
console.log("Quick Sorted Array:", quickSortedArray);

4. 합병 소트 (Merge Sort): 리스트를 반으로 나누어 각각을 정렬하고 합침으로써 정렬을 수행하는 알고리즘입니다. 안정적이며 대규모 데이터에도 효과적으로 동작합니다.

예시코드 c++:

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[m + 1+ j];

    int i = 0, j = 0;
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

 

예시코드 jsp :

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

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

    return merge(mergeSort(left), mergeSort(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), right.slice(rightIndex));
}

// Example usage:
const mergeSortedArray = mergeSort([64, 34, 25, 12, 22, 11]);
console.log("Merge Sorted Array:", mergeSortedArray);

5. 힙 소트 (Heap Sort): 자료구조를 이용하여 정렬하는 알고리즘으로, 힙의 특성을 활용하여 정렬을 수행합니다. 퀵 소트와 유사한 평균 시간 복잡도를 가지며 안정적이며, 효율적인 메모리 사용으로 널리 사용되고 있습니다.

예시코드 c++ :

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    heapSort(arr, n);

    cout << "\nSorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

 

예시코드 jsp :

function heapSort(arr) {
    const n = arr.length;

    // Build heap (rearrange array)
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // One by one extract an element from heap
    for (let i = n - 1; i > 0; i--) {
        // Move current root to end
        [arr[0], arr[i]] = [arr[i], arr[0]];

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }

    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

// Example usage:
const heapSortedArray = heapSort([64, 34, 25, 12, 22, 11]);
console.log("Heap Sorted Array:", heapSortedArray);