1. 문제 제시
주어진 정수 배열을 오름차순으로 정렬하는 버블 소트(Bubble Sort) 알고리즘을 구현하시오.
버블 소트는 가장 단순한 정렬 알고리즘 중 하나로, 인접한 두 원소를 비교하여 정렬하는 방식입니다.
이 알고리즘의 기본 아이디어는 배열의 각 원소를 반복적으로 비교하여, 작은 값을 앞으로 보내는 것입니다.
2. 알고리즘 설명
버블 소트 알고리즘의 작동 방식은 다음과 같습니다:
- 배열의 처음부터 끝까지 두 개의 인접한 원소를 비교합니다. 첫 번째 원소가 두 번째 원소보다 크면 두 원소를 교환합니다.
- 배열의 끝까지 도달할 때까지 이 과정을 반복합니다.
- 배열의 끝까지 도달하면 가장 큰 원소는 맨 뒤로 이동하게 됩니다.
- 위의 과정을 배열의 크기 – 1 만큼 반복합니다. 매 반복마다 최대 값이 배열의 뒤로 이동하므로, 남은 원소에 대해 다시 비교 및 교환을 진행합니다.
3. 예시
예를 들어, 주어진 배열이 다음과 같다고 가정합시다:
[64, 34, 25, 12, 22, 11, 90]버블 소트를 적용하면 다음과 같은 단계가 발생합니다:
- 1차 정렬: [34, 25, 12, 22, 11, 64, 90]
- 2차 정렬: [25, 12, 22, 11, 34, 64, 90]
- 3차 정렬: [12, 22, 11, 25, 34, 64, 90]
- 4차 정렬: [12, 11, 22, 25, 34, 64, 90]
- 5차 정렬: [11, 12, 22, 25, 34, 64, 90]
이 과정이 완료되면 배열이 오름차순으로 정렬됩니다.
4. 자바 구현
다음은 위에서 설명한 버블 소트 알고리즘을 자바로 구현한 코드입니다:
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 요소 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 교환이 발생했음을 표시
}
}
// 만약 교환이 이루어지지 않았다면 배열이 이미 정렬된 것이므로 종료
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("정렬된 배열:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
5. 코드 설명
위 코드는 다음과 같은 주요 기능을 포함하고 있습니다:
- bubbleSort 메소드: 배열을 입력받아 버블 소트 알고리즘을 수행하여 정렬합니다. 두 개의 중첩된 루프를 사용하여 인접한 원소를 비교하고 필요 시 교환합니다.
- swapped 변수: 이 변수는 현재 패스에서 교환이 발생했는지에 대한 플래그 역할을 합니다. 더 이상 교환이 이루어지지 않으면 배열이 이미 정렬된 상태이므로 추가적인 패스를 생략할 수 있습니다.
- main 메소드: 실행 시 예시 배열을 정의하고 버블 소트 메소드를 호출합니다. 정렬 완료 후 결과를 출력합니다.
6. 성능 분석
버블 소트 알고리즘의 시간 복잡도는 최악의 경우와 평균적으로 O(n^2)입니다. 즉, 배열의 길이가 n일 때, n*(n-1)/2 만큼의 비교가 필요합니다. 최선의 경우(이미 정렬된 배열)에 대해서는 O(n)의 성능을 보여줍니다. 이러한 성능 때문에 버블 소트는 작은 데이터 세트에 적합하며, 큰 데이터 세트에는 다른 정렬 알고리즘(예: 퀵 소트, 머지 소트 등)이 더 효과적입니다.
7. 코드 최적화 및 개선
버블 소트는 그 자체로 간단하고 배우기 좋은 알고리즘이지만, 성능 최적화가 가능하다는 점에서 몇 가지 개선점을 고려할 수 있습니다:
- 스왑 플래그를 사용하여 이미 정렬된 경우를 감지할 수 있습니다.
- 각 반복에서 배열의 마지막 요소는 이미 정렬된 상태이므로, 내부 루프의 범위를 감소시킬 수 있습니다.
- 정렬된 상태를 확인하며 전체 루프를 줄일 수 있습니다.
8. 마무리
이번 강좌에서는 자바로 버블 소트 알고리즘을 구현해 보았습니다. 여러 가지 정렬 알고리즘 중에서 가장 단순한 형태의 알고리즘을 배우는 것은 프로그래밍의 기본 원리를 이해하는 데 큰 도움이 됩니다. 알고리즘의 기본 구조와 흐름을 이해하고, 코드로 구현해 보며 여러분의 실력을 키우시길 바랍니다. 다음 강좌에서는 더 발전된 정렬 알고리즘에 대해서 다루어 보겠습니다. 감사합니다!