C# 코딩테스트 강좌, 버블 소트 프로그램 1

문제 설명

다음과 같은 정수 배열이 주어졌을 때, 배열을 오름차순으로 정렬하는 프로그램을 작성하시오.
프로그램은 ‘버블 소트’ 알고리즘을 사용하여 구현해야 합니다.
버블 소트는 인접한 두 요소를 비교하고, 크기가 잘못된 경우 서로 위치를 교환하는 방식으로 작동합니다.
이 과정은 배열의 끝까지 반복되며, 이 과정을 한 번 수행할 때 마지막에 있는 요소는 정렬된 상태가 됩니다.
따라서 각 반복이 끝날 때마다 정렬된 요소의 수가 하나씩 증가합니다.

입력 형식

첫 번째 줄에는 정수 N (1 ≤ N ≤ 100)이 주어집니다.
두 번째 줄에는 N개의 정수가 주어지며, 각 정수는 -1000 ≤ A[i] ≤ 1000의 범위를 갖습니다.

출력 형식

정렬된 N개의 정수를 한 줄에 띄어쓰기로 구분하여 출력합니다.

예제 입력

        5
        5 3 2 4 1

예제 출력

        1 2 3 4 5

버블 소트 알고리즘 소개

버블 소트(bubble sort) 알고리즘은 가장 간단한 정렬 알고리즘 중 하나로, 배열을 반복적으로 탐색하면서
인접한 요소를 비교하여 정렬하는 알고리즘입니다. 이 알고리즘은 효율적이지 않으며, O(N²)의 시간 복잡도를
가지지만, 이해하고 구현하기 쉽기 때문에 학습 목적으로 많이 사용됩니다.

버블 소트의 기본적인 동작 원리는 다음과 같습니다:

  1. 배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교합니다.
  2. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 교환합니다.
  3. 배열의 끝까지 이 과정을 반복합니다.
  4. 한 번의 전체 확인 후 마지막 요소는 정렬되었으므로, 다음 단계에서 배열의 크기를 하나 감소시키고 다시 반복합니다.
  5. 이 과정을 배열이 완전히 정렬될 때까지 반복합니다.

C# 버블 소트 구현

이제 위의 알고리즘을 바탕으로 C#을 이용해 버블 소트를 구현해보겠습니다.
아래는 버블 소트를 구현한 C# 코드입니다. 


using System;

class Program
{
    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;
                }
            }
        }
    }

    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        
        BubbleSort(arr);
        
        Console.WriteLine(string.Join(" ", arr));
    }
}

위 코드에서는 배열을 정렬하는 BubbleSort 메소드를 정의하고 있습니다.
이 메소드는 두 개의 중첩 반복문을 사용하여 인접 요소를 비교하고 교환하여 배열을 정렬합니다.
Main 메소드에서는 사용자로부터 배열의 크기와 요소를 입력받고,
BubbleSort 메소드를 호출하여 배열을 정렬한 후, 결과를 출력합니다.

코드 실행 및 테스트

코드를 실행하기 위해서는 C#를 지원하는 IDE나 에디터를 사용해야 합니다.
Visual Studio나 Visual Studio Code와 같은 IDE를 사용할 수 있습니다.
코드를 입력한 후, Run 버튼을 클릭하거나 Ctrl + F5를 눌러 실행합니다.

실행 후에 입력 예제와 같이 정수를 입력하면 오름차순으로 정렬된 결과가 출력됩니다.
다양한 테스트 케이스를 사용하여 알고리즘의 정확성을 확인하는 것이 좋습니다.

테스트 케이스

  • 입력:

    3
5 1 2

    출력:

    1 2 5
  • 입력:

    4
3 3 2 1

    출력:

    1 2 3 3
  • 입력:

    5
-1 -2 0 2 1

    출력:

    -2 -1 0 1 2

버블 소트 알고리즘의 장단점

버블 소트 알고리즘은 간단하고 이해하기 쉬운 정렬 알고리즘이지만, 많은 데이터에 대해서는
비효율적입니다. 아래는 버블 소트의 장단점입니다.

장점

  • 구현이 간단하고 직관적이다.
  • 정렬이 완료되는 과정을 시각적으로 확인하기 쉽다.
  • 추가 메모리를 필요로 하지 않는다. (제자리 정렬)

단점

  • 시간 복잡도가 O(N²)로 비효율적이다. 대규모 데이터에 대해서는 사용하지 않는 것이 좋다.
  • 최악의 경우, N개의 요소 전체를 비교해야 하므로 많은 시간이 소요될 수 있다.
  • 정렬하는 동안 여러 번 배열을 수정을 계속하므로 안정성이 떨어질 수 있다.

이상의 장단점을 고려할 때, 버블 소트는 주로 학습 용도로 사용되며, 실무에서는
퀵 소트, 병합 정렬(merge sort) 등 더 효율적인 정렬 알고리즘을 사용하는 것이 일반적입니다.

결론

오늘은 C#을 이용한 버블 소트 프로그램을 구현하고, 그 과정에 대해 자세히 알아보았습니다.
간단한 알고리즘이지만, 정렬 알고리즘의 기초를 이해하는 데 매우 유용합니다.
다양한 정렬 알고리즘을 학습하면서 이론을 구체화하고, 프로그래밍 실력을 향상시키는 데 도움이 되길 바랍니다.

© 2023 코딩테스트 강좌. 모든 권리 보유.