이번 강좌에서는 C# 코딩테스트에서 자주 출제되는 알고리즘 중 하나인 버블 정렬(Bubble Sort)에 대해 알아보겠습니다. 버블 정렬은 모든 정렬 알고리즘 중 가장 단순하면서도, 이해하기 쉬운 알고리즘입니다. 이 강좌에서는 버블 정렬의 개념, 구현 방법, 그리고 실제 취업 코딩 테스트에서 만나볼 수 있는 문제를 살펴보겠습니다.
문제 제시
주어진 정수 배열을 오름차순으로 정렬하시오. 정렬에 버블 정렬을 사용해야 하며, 입력 배열의 길이는 1 이상 1000 이하이며, 배열의 요소는 -10000 이상 10000 이하의 정수로 제한합니다.
버블 정렬(Bubble Sort) 개요
버블 정렬은 인접한 두 요소를 비교하여 정렬하는 간단한 정렬 알고리즘입니다. 이 과정에서 가장 큰 요소가 배열의 뒤로 ‘떨어진다’는 점에서 ‘버블’이라는 이름이 붙었습니다. 알고리즘의 기본 흐름은 다음과 같습니다:
- 배열의 처음부터 끝까지 순회합니다.
- 각 인접한 두 요소를 비교하여, 앞의 요소가 뒤의 요소보다 크면 두 요소의 위치를 바꿉니다.
- 배열의 끝에 도달할 때까지 1-2 단계를 반복합니다.
- 각 횟수에 대해 하나의 요소가 제자리를 찾을 때까지 반복합니다. 전체 배열이 정렬될 때까지 진행합니다.
버블 정렬 알고리즘의 시간 복잡도
버블 정렬의 평균 시간 복잡도는 O(n2)입니다. 이는 배열의 길이가 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 함수는 다음과 같이 작동합니다:
- 배열의 크기를 얻습니다.
- 두 개의 중첩된 루프를 사용하여 배열을 순회합니다.
- 첫 번째 루프는 배열의 각 요소에 대해 최댓값을 찾아오는 역할을 일반적으로 맡고, 두 번째 루프는 인접 요소 비교 및 교환을 처리합니다.
- 정렬이 완료되면, 결과를 출력합니다.
주의사항
버블 정렬은 교육 용도로 이해하기 쉽지만, 실제 코딩 테스트에서는 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다. 예를 들어, 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)은 특히 대규모 데이터에 유리합니다.
결론
버블 정렬 알고리즘은 특히 초보자에게 유용한 기본 정렬 방법이며, 알고리즘의 이해를 돕는 데 좋은 역할을 합니다. 이 강좌를 통해 버블 정렬에 대한 이해도를 높이고, 코딩 테스트에서의 기초적인 문제를 해결할 수 있도록 준비해 보시기 바랍니다. 더 나아가, 효율적인 정렬 알고리즘도 함께 학습해 두시면 좋겠습니다.