문제 설명
다음과 같은 정수 배열이 주어졌을 때, 배열을 오름차순으로 정렬하는 프로그램을 작성하시오.
프로그램은 ‘버블 소트’ 알고리즘을 사용하여 구현해야 합니다.
버블 소트는 인접한 두 요소를 비교하고, 크기가 잘못된 경우 서로 위치를 교환하는 방식으로 작동합니다.
이 과정은 배열의 끝까지 반복되며, 이 과정을 한 번 수행할 때 마지막에 있는 요소는 정렬된 상태가 됩니다.
따라서 각 반복이 끝날 때마다 정렬된 요소의 수가 하나씩 증가합니다.
입력 형식
첫 번째 줄에는 정수 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²)의 시간 복잡도를
가지지만, 이해하고 구현하기 쉽기 때문에 학습 목적으로 많이 사용됩니다.
버블 소트의 기본적인 동작 원리는 다음과 같습니다:
- 배열의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교합니다.
- 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 교환합니다.
- 배열의 끝까지 이 과정을 반복합니다.
- 한 번의 전체 확인 후 마지막 요소는 정렬되었으므로, 다음 단계에서 배열의 크기를 하나 감소시키고 다시 반복합니다.
- 이 과정을 배열이 완전히 정렬될 때까지 반복합니다.
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#을 이용한 버블 소트 프로그램을 구현하고, 그 과정에 대해 자세히 알아보았습니다.
간단한 알고리즘이지만, 정렬 알고리즘의 기초를 이해하는 데 매우 유용합니다.
다양한 정렬 알고리즘을 학습하면서 이론을 구체화하고, 프로그래밍 실력을 향상시키는 데 도움이 되길 바랍니다.