C# 코딩테스트 강좌, 버블 정렬

이번 강좌에서는 C# 코딩테스트에서 자주 출제되는 알고리즘 중 하나인 버블 정렬(Bubble Sort)에 대해 알아보겠습니다. 버블 정렬은 모든 정렬 알고리즘 중 가장 단순하면서도, 이해하기 쉬운 알고리즘입니다. 이 강좌에서는 버블 정렬의 개념, 구현 방법, 그리고 실제 취업 코딩 테스트에서 만나볼 수 있는 문제를 살펴보겠습니다.

버블 정렬(Bubble Sort) 개요

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 간단한 정렬 알고리즘입니다. 이 과정에서 가장 큰 요소가 배열의 뒤로 ‘떨어진다’는 점에서 ‘버블’이라는 이름이 붙었습니다. 알고리즘의 기본 흐름은 다음과 같습니다:

1. 배열의 처음부터 끝까지 순회합니다.
2. 각 인접한 두 요소를 비교하여, 앞의 요소가 뒤의 요소보다 크면 두 요소의 위치를 바꿉니다.
3. 배열의 끝에 도달할 때까지 1-2 단계를 반복합니다.
4. 각 횟수에 대해 하나의 요소가 제자리를 찾을 때까지 반복합니다. 전체 배열이 정렬될 때까지 진행합니다.

버블 정렬 알고리즘의 시간 복잡도

버블 정렬의 평균 시간 복잡도는 O(n²)입니다. 이는 배열의 길이가 n일 때, n-1회 반복하면서 각 내부 순회를 통해 n-1번의 비교가 이루어지기 때문입니다. 하지만 최선의 경우(이미 정렬된 상태)에는 O(n)입니다.

버블 정렬의 장단점

장점

• 구현이 간단하고, 직관적이다.
• 메모리 사용이 적고, 안정적인 정렬이다.

단점

• 정렬 성능이 떨어져 대규모 데이터나 복잡한 정렬이 필요한 경우 비효율적이다.
• 다른 효율적인 정렬 알고리즘과 비교하여 성능이 낮다.

문제 풀이

문제에서 주어진 배열을 버블 정렬을 이용하여 오름차순으로 정렬하겠습니다. 다음은 해당 문제에 대한 해결책입니다.

C#
using System;

class Program
{
    static void Main(string[] args)
    {
        int[] array = { 64, 34, 25, 12, 22, 11, 90 };
        BubbleSort(array);
        
        Console.WriteLine("정렬된 배열: " + string.Join(", ", array));
    }

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

코드 설명

이 코드는 BubbleSort라는 함수를 사용하여 배열을 정렬합니다. BubbleSort 함수는 다음과 같이 작동합니다:

1. 배열의 크기를 얻습니다.
2. 두 개의 중첩된 루프를 사용하여 배열을 순회합니다.
3. 첫 번째 루프는 배열의 각 요소에 대해 최댓값을 찾아오는 역할을 일반적으로 맡고, 두 번째 루프는 인접 요소 비교 및 교환을 처리합니다.
4. 정렬이 완료되면, 결과를 출력합니다.

결론

버블 정렬 알고리즘은 특히 초보자에게 유용한 기본 정렬 방법이며, 알고리즘의 이해를 돕는 데 좋은 역할을 합니다. 이 강좌를 통해 버블 정렬에 대한 이해도를 높이고, 코딩 테스트에서의 기초적인 문제를 해결할 수 있도록 준비해 보시기 바랍니다. 더 나아가, 효율적인 정렬 알고리즘도 함께 학습해 두시면 좋겠습니다.