C# - 정렬 알고리즘 (Sorting Algoritm) : 버블/선택/삽입/병합/퀵 정렬

배열을 효율적으로 정렬하기 위한 여러 알고리즘 적 시도가 있었다.

 

• 버블 정렬 (Bubble Sort)
• 선택 정렬 (Selection Sort)
• 삽입 정렬 (Insertion Sort)
• 병합 정렬 (Merge Sort)
• 퀵 정렬 (Quick Sort)
• 힙 정렬 (Heap Sort)

 

이번 글에서는 위의 유명한 5가지 정렬에 대해 정리해볼 것이다.

 

---

 

버블 정렬 (Bubble Sort)

인접한 두 원소를 비교해 잘못된 순서면 스왑한다.

한 패스가 끝나면 가장 큰 값이 맨 뒤로 이동하게 되며, 이를 정렬 될 때까지 반복한다.

 

public static void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;
        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]);
                swapped = true;
            }
        }
        if (!swapped) break; // 이미 정렬된 경우 O(n)
    }
}

 

비교적 간단하게 구현할 수 있는 정렬 알고리즘이다.

내부 반복문에서 스왑이 일어났는지 여부를 체크하는 것으로 정렬이 완료됐는지 조기 체크 후 탈출하는 것으로 다소 최적화 할 수 있다.

 

시간 : 최악/평균 - O(n²), 최선 - O(n)

공간 : O(1)

안정 정렬

 

더 좋은 정렬 알고리즘이 이미 많아서 n이 매우 작고, 구현 단순성이 중요할때나 교육용/디버그용으로 사용된다.

 

---

 

선택 정렬 (Selection Sort)

간단한 정렬 알고리즘으로, 주어진 리스트에서 최소값을 선택하여 정렬되지 않은 부분과 정렬된 부분을 나누고, 정렬되지 않은 부분에서 최소값을 선택하여 정렬된 부분에 추가하는 과정을 반복한다.

구간을 한 칸씩 뒤로 밀게 된다.

 

public static 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;
        }

        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

 

 

시간 복잡도 : O(n²)

공간 복잡도 : O(1)

불안정 정렬 (동일값의 상대순서가 깨질 수 있음)

 

스왑 횟수를 최소화해야 하는 특수 상황 (스왑 <= n-1)

메모리 제약이 극단적으로 빡빡하고, 구현 단순성이 중요할 때 사용한다.

 

---

 

삽입 정렬 (Insertion Sort)

리스트를 정렬된 부분과 정렬되지 않은 부분으로 나눈 후, 정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복한다.

평균/최악 에서는 느리지만 거의 정렬된 입력에서는 매우 빠르다.

 

public static void InsertionSort(int[] arr)
{
    int n = arr.Length;

    for (int i = 1; i < n; 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;
    }
}

 

 

시간 복잡도 : 최악/평균 - O(n²), 최선 - O(n)

공간 : O(1)

안정 정렬

 

부분적으로 정렬된 데이터, 작은 배열 블록 에서 사용하면 좋다.

 

 

---

 

퀵 정렬 (Quick Sort)

분할 정복 (Divide and Conquer) 기법을 사용하는 정렬 알고리즘으로, 리스트를 기준값을 중심으로 분할한 후, 각 부분을 재귀적으로 정렬한다.

매우 빠르고 구현이 간단하다.

랜덤 피벗 또는 median-od-three 전략을 쓰면 최악 케이스 확률을 낮춘다고 한다.

 

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivotIndex = Partition(arr, low, high);

        QuickSort(arr, low, pivotIndex - 1);
        QuickSort(arr, pivotIndex + 1, high);
    }
}

private static 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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp2 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp2;

    return i + 1;
}

 

 

시간 복잡도 : 평균 O(n log n), 최악 O(n²)

공간 복잡도 : 평균 O(log n) - 재귀 스택

불안정 정렬

 

일반적인 인메모리 정렬에서 가장 빠른 편이머 라이브러리 내부 정렬의 기본 골격으로 주로 활용된다.

 

 

---

 

병합 정렬 (Merge Sort)

분할 정복 (Divide and Conquer) 기법을 사용하는 정렬 알고리즘으로, 리스트를 반으로 나눈 후 재귀적으로 정렬한 다음, 정렬된 부분 리스트를 병합하여 최종적으로 정렬을 수행한다.

항상 O(n log n)을 보장한다.

 

public static void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;

        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);

        Merge(arr, left, mid, right);
    }
}

private static void Merge(int[] arr, int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    Array.Copy(arr, left, leftArr, 0, n1);
    Array.Copy(arr, mid + 1, rightArr, 0, n2);

    int i = 0, j = 0;
    int k = left;

    while (i < n1 && j < n2)
    {
        if (leftArr[i] <= rightArr[j])
        {
            arr[k] = leftArr[i];
            i++;
        }
        else
        {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

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

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

 

시간 복잡도 : O(n log n)

공간 복잡도 : O(n) 추가 버퍼

안정 정렬

 

안정적이고 예측 가능한 성능이 필요할 때 사용한다.

 

 

---

 

힙 정렬 (Heap Sort)

힙(Heap) 자료구조를 이용하여 정렬을 수행하는 알고리즘으로, 주어진 리스트를 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구성한 후, 힙에서 원소를 하나씩 꺼내 정렬된 순서로 배열한다.

public static void HeapSort(int[] arr)
{
    int n = arr.Length;

    for (int i = n / 2 - 1; i >= 0; i--)
        Heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        Heapify(arr, i, 0);
    }
}

private static 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)
    {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        Heapify(arr, n, largest);
    }
}

 

시간 복잡도 : 항상 O(n log n)

공간 복잡도 : O(1)

불안정 정렬

 

 

---

 

안정 정렬: 값이 같은 원소의 상대적 순서가 유지된다. (버블, 삽입, 병합)

불안정 정렬: 상대 순서가 바뀔 수 있다. (선택, 퀵 힙)

예: (score, name)를 정렬할 때, score만 키로 정렬해도 기존 name 순서가 유지되길 원하면 안정 정렬이 필요하다.

 

 

각 케이스

• 입력이 거의 정렬: 삽입 정렬
• 스왑 비용을 크게 보기: 선택 정렬
• 일반적 인메모리에서 평균 성능 최우선: 퀵 정렬(랜덤 피벗/하이브리드)
• 안정성+예측 가능한 성능: 병합 정렬
• 추가 메모리 없이 최악 보장 O(n log n): 힙 정렬
• 아주 작은 n: 단순 O(n²) 정렬도 충분