이 글에서는 C#으로 버블 소트 알고리즘을 구현하는 방식에 대해 설명합니다. 버블 소트는 가장 기본적인 정렬 알고리즘 중 하나로, 여러 가지 알고리즘 시험에서 자주 등장하곤 합니다. 이번 포스팅에서는 버블 소트의 동작 원리에 대한 자세한 설명과 함께 C#으로 구현한 예제를 살펴보겠습니다.
버블 소트란?
버블 소트는 배열의 인접한 요소를 비교하여 두 요소의 순서를 맞춰주는 간단한 정렬 알고리즘입니다. 이 과정에서 가장 큰(혹은 작은) 요소가 배열의 끝으로 ‘버블’처럼 떠오르는 모습을 연상할 수 있습니다. 이 알고리즘은 간단하게 구현할 수 있지만, 효율적인 정렬 알고리즘은 아닙니다. 시간 복잡도는 O(n^2)입니다.
문제 설명
주어진 정수 배열을 버블 소트 알고리즘을 사용하여 오름차순으로 정렬하시오.
입력
- 입력: 정수 배열 arr = [64, 34, 25, 12, 22, 11, 90]
출력
- 출력: 정렬된 배열 [11, 12, 22, 25, 34, 64, 90]
버블 소트 알고리즘 설명
버블 소트는 다음과 같은 과정을 거칩니다:
- 배열의 길이를 확인합니다.
- 두 개의 중첩된 루프를 사용하여 배열의 모든 요소를 반복합니다.
- 인접한 두 요소를 비교하고, 잘못된 순서인 경우 서로 교환합니다.
- 한 번의 전체 비교가 끝났을 때, 가장 큰 요소가 배열 끝으로 이동하게 됩니다.
- 이 과정을 N-1회 반복하면 배열이 정렬됩니다.
C#로 버블 소트 구현하기
이제 위의 과정을 C# 코드로 구현해 보겠습니다.
using System;
class Program
{
static void Main()
{
int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
Console.WriteLine("원본 배열:");
PrintArray(arr);
BubbleSort(arr);
Console.WriteLine("정렬된 배열:");
PrintArray(arr);
}
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 PrintArray(int[] arr)
{
foreach (var item in arr)
{
Console.Write(item + " ");
}
Console.WriteLine();
}
}
코드 설명
위 코드는 간단한 C# 콘솔 애플리케이션을 사용하여 버블 소트를 구현한 예시입니다.
- BubbleSort(int[] arr): 주어진 배열을 정렬하는 메서드입니다. 이 메서드는 두 개의 중첩 루프를 사용하여 배열을 반복하면서 인접한 요소를 비교하고 교환합니다.
- PrintArray(int[] arr): 배열의 요소를 출력하는 헬퍼 메서드입니다. 각 요소를 공백으로 구분하여 출력합니다.
결론
버블 소트는 배우고 이해하기 쉬운 정렬 알고리즘이지만, 실제로는 더 나은 성능을 가진 다른 알고리즘을 사용하는 것이 좋습니다. 그러나 코딩테스트 준비 과정에서 기본적인 정렬 알고리즘의 개념을 알고 이해하는 것은 중요합니다.
이 글이 다음 코딩테스트 준비에 도움이 되길 바랍니다. 질문이나 논의할 점이 있다면 댓글로 남겨 주시기 바랍니다!