[C#] 정렬 알고리즘

정렬 알고리즘과 C#의 Sort

01. 정렬 알고리즘

정렬 알고리즘은 주어진 데이터를 특정한 순서(대부분 오름차순/내림차순) 로 배열하는 방법입니다.
컴퓨터 과학에서 매우 중요한 기본 개념이며, 효율적인 검색, 탐색, 데이터 처리의 기반이 됩니다.

 

1) 선택 정렬 ( Selection Sort )

• 원리 : 배열에서 가장 작은(또는 큰) 값을 찾아 맨 앞(또는 뒤) 원소와 교환.
• 시간 복잡도 : O(n²) (최악/평균 동일)
• 공간 복잡도 : O(1) (추가 메모리 거의 없음)

• 구현 예제
  • 가장 작은 원소를 찾아서 맨 앞에 위치하는 것을 반복하여 정렬하는 알고리즘

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

for (int i = 0; i < arr.Length; i++)
{
    int minIndex = i;

    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[j] < arr[minIndex])
        {
            minIndex = j;
        }
    }

    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
    
    // (arr[i], arr[minIndex]) = (arr[minIndex], arr[i]);
}

foreach (int num in arr)
{
    Console.WriteLine(num);
}

 

2) 삽입 정렬 (Insertion Sort)

• 원리 : 정렬되지 않은 요소를 하나씩 꺼내어 이미 정렬된 부분에 적절히 삽입.
• 시간 복잡도 : O(n²), 하지만 배열이 거의 정렬되어 있다면 O(n)까지 효율적.
• 공간 복잡도 : O(1)
• 구현 예제
  • 현재 위치에서 그 이하의 배열을 정렬된 배열 부분에 삽입하는 방법으로 정렬하는 알고리즘

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

for (int i = 1; i < arr.Length; i++) // i = 2 (1번지)
{
    int j = i - 1; // j = 5 (0번지)
    int key = arr[i]; // key = 2

    while (j >= 0 && arr[j] > key) // 5 > 2
    {
        arr[j + 1] = arr[j]; // {5, 5}
        j--;
    }

    arr[j + 1] = key; // {2, 5}
}

foreach (int num in arr)
{
    Console.WriteLine(num);
}

 

 

3) 퀵 정렬 (Quick Sort)

• 원리 : 피벗(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 후 재귀적으로 정렬.
• 시간 복잡도 : 평균 O(n log n), 최악 O(n²)
• 공간 복잡도 : 평균 O(log n) (재귀 스택 사용)

void QuickSort(int[] arr, int left, int right) // left = 0, right = 5
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right); 

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}

int Partition(int[] arr, int left, int right) // left = 0, right = 5
{
    {5, 2, 4, 6, 1, 3}
    int pivot = arr[right]; // right값을 찾음 pivot = arr[5] = 3
    int i = left - 1; // i = -1

    for (int j = left; j < right; j++) // 0~4
    {
        if (arr[j] < pivot) // arr[j](left) 위치값보다 < pivot(3)이 크다면
        {
            i++;
            Swap(arr, i, j); // i와 j값을 바꿈
        }
    }

    Swap(arr, i + 1, right);

    return i + 1;
}

void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

static void Main(string[] args)
{
    int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

    QuickSort(arr, 0, arr.Length - 1);

    foreach (int num in arr)
    {
        Console.WriteLine(num);
    }
}

 

4) 병합 정렬 (Merge Sort)

• 원리 : 분할 정복(Divide and Conquer). 배열을 반으로 나눈 뒤 각각 정렬하고 합침.
• 시간 복잡도 : 항상 O(n log n)
• 공간 복잡도 : O(n) (임시 배열 필요)
• 구현 예제
  • 분할 정복 방법을 이용하여 정렬하는 알고리즘

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);
    }
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] temp = new int[arr.Length];

    int i = left;
    int j = mid + 1;
    int k = left;

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

    while (i <= mid)
    {
        temp[k++] = arr[i++];
    }

    while (j <= right)
    {
        temp[k++] = arr[j++];
    }

    for (int l = left; l <= right; l++)
    {
        arr[l] = temp[l];
    }
}

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

MergeSort(arr, 0, arr.Length - 1);

foreach (int num in arr)
{
    Console.WriteLine(num);
}

 

 시간복잡도 비교표

알고리즘	평균 시간	최악 시간	공간
선택 정렬	O(n²)	O(n²)	O(1)
삽입 정렬	O(n²)	O(n²)	O(1)
퀵 정렬	O(n log n)	O(n²)	O(log n)
병합 정렬	O(n log n)	O(n log n)	O(n)

02. C# Sort

C#에서는 직접 알고리즘을 구현하지 않고도, Array.Sort 또는 List<T>.Sort 메서드를 사용해 간단히 정렬할 수 있습니다.

 

특징

• 기본적으로 오름차순 정렬
• 요소들의 자료형에 따라 다양한 정렬 기준을 사용할 수 있습니다.
• 원본 배열이나 리스트를 직접 수정하므로 반환값이 없습니다.

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers)); // {1, 2, 3, 4, 5, 6, 7, 8, 9}

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names)); // Alice, Bob, John

 

string.Join

구분 문자열로 여러 문자열 요소들을 합치는 정적 메서드 입니다.

기본 문법

string result = string.Join(string separator, IEnumerable<string> values);
string result = string.Join(string separator, params string[] values);
string result = string.Join(string separator, object[] values);