정렬 알고리즘 기본 개념 및 C# 구현

안녕하세요! 오늘의 기술 면접 지식은 정렬 알고리즘에 관한 것입니다. 이 포스팅에서는 자주 사용되는 정렬 알고리즘의 기본 개념과 C#으로 구현한 예제 코드를 다룹니다.

 

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 알고리즘입니다. 시간 복잡도는 O(n^2)입니다.

 

public static 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])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

퀵 정렬 (Quick Sort)

퀵 정렬은 피벗(pivot)을 기준으로 작은 요소와 큰 요소를 분할하여 정렬하는 알고리즘입니다. 평균 시간 복잡도는 O(n log n)이며, 최악의 경우 O(n^2)입니다.

 

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(arr, low, high);
        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 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 swapTemp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = swapTemp;

    return i + 1;
}

병합 정렬 (Merge Sort)

병합 정렬은 배열을 절반씩 나누어 정렬한 후, 병합하는 알고리즘입니다. 시간 복잡도는 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[] leftArray = new int[mid - left + 1];
    int[] rightArray = new int[right - mid];

    Array.Copy(arr, left, leftArray, 0, mid - left + 1);
    Array.Copy(arr, mid + 1, rightArray, 0, right - mid);

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

    while (i < leftArray.Length && j < rightArray.Length)
    {
        if (leftArray[i] <= rightArray[j])
        {
            arr[k] = leftArray[i];
            i++;
        }
        else
        {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

    while (i < leftArray.Length)
    {
        arr[k] = leftArray[i];
        i++;
        k++;
    }

    while (j < rightArray.Length)
    {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

 

병합 정렬은 안정 정렬(Stable Sort)이며, 공간 복잡도가 O(n)인 것이 특징입니다. 이러한 특징 때문에 병합 정렬은 대용량 데이터를 정렬하는 데에 적합한 알고리즘입니다. 기술 면접에서 정렬 알고리즘에 대한 질문이 나올 경우, 병합 정렬과 관련된 이론과 구현 예시를 활용하여 답변할 수 있습니다. 다음 포스팅에서 또 다른 주제로 찾아뵙겠습니다!