정렬 알고리즘 총정리 (버블, 삽입, 선택, 퀵, 병합)

이전 글에서는 힙(Heap)과 우선순위 큐에 대해 알아봤습니다.
이번에는 정렬(Sorting) 알고리즘 중 대표적인 5가지를 소개하며, 각 알고리즘의 원리와 성능, 사용 예시를 정리해봅니다.

1. 정렬 알고리즘이란?

정렬 알고리즘은 데이터를 오름차순 또는 내림차순으로 순서대로 정렬하는 알고리즘입니다.

• 검색 속도 향상, 이진 탐색 가능, 데이터 시각화/분석에 필수
• 각 알고리즘은 시간 복잡도, 공간 복잡도, 안정성 등이 다름

2. 주요 정렬 알고리즘 비교

알고리즘 평균 시간 복잡도 공간 복잡도 안정 정렬 특징

3. 각 정렬 알고리즘 예시 (C#)

 버블 정렬 (Bubble Sort)

void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                (arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
            }
        }
    }
}

 선택 정렬 (Selection Sort)

void SelectionSort(int[] arr)
{
    int n = arr.Length;
    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;
        }
        (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
    }
}

 삽입 정렬 (Insertion Sort)

void InsertionSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

 퀵 정렬 (Quick Sort)

void QuickSort(int[] arr, int left, int right)
{
    if (left >= right) return;
    int pivot = arr[(left + right) / 2];
    int index = Partition(arr, left, right, pivot);
    QuickSort(arr, left, index - 1);
    QuickSort(arr, index, right);
}

int Partition(int[] arr, int left, int right, int pivot)
{
    while (left <= right)
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;
        if (left <= right)
        {
            (arr[left], arr[right]) = (arr[right], arr[left]);
            left++; right--;
        }
    }
    return left;
}

 병합 정렬 (Merge Sort)

void MergeSort(int[] arr)
{
    if (arr.Length <= 1) return;
    MergeSortRecursive(arr, 0, arr.Length - 1);
}

void MergeSortRecursive(int[] arr, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSortRecursive(arr, left, mid);
    MergeSortRecursive(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right)
    {
        temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int t = 0; t < temp.Length; t++)
    {
        arr[left + t] = temp[t];
    }
}

4. 실생활 예시로 이해하기

• 버블 정렬 = 비눗방울이 위로 올라가듯 큰 숫자가 점점 뒤로 밀림
• 삽입 정렬 = 트럼프 카드 정렬하기
• 선택 정렬 = 전체 중 가장 작은 값을 골라서 앞으로 옮김
• 퀵 정렬 = 기준(pivot)을 정하고 왼쪽/오른쪽으로 나눠 정렬
• 병합 정렬 = 정렬된 작은 배열들을 병합하여 큰 배열로 만듦

이번 글에서는 정렬 알고리즘 5종 (버블, 선택, 삽입, 퀵, 병합) 을 비교하며 정리했습니다.

• 단순 정렬은 구조 이해에 좋고
• 퀵/병합 정렬은 실무에서도 자주 사용됩니다.

이로써 자료구조 시리즈의 기초 편이 마무리됩니다.