1. 버블 정렬 이란?
버블 정렬은 간단한 정렬 알고리즘 중 하나로, 배열 안에서 가장 작은(또는 가장 큰) 값을 찾기 위해 인접한 두 원소를 반복적으로 비교하며 자리를 바꾸는 방식입니다. 가장 큰 값이 한 번에 끝으로 이동하는 방식이 거품이 위로 올라가는 모양과 비슷하다고 해서 "버블 정렬"이라고 부릅니다.
2. 버블 정렬의 동작 원리
- 배열의 첫 번째 값부터 시작해서 인접한 두 값을 비교합니다.
- 두 값이 크기 순으로 정렬되지 않았다면, 자리 바꿈(swap)을 수행합니다.
- 배열의 끝까지 이 과정을 반복합니다.
- 배열의 끝에 가장 큰 값이 놓이게 되면, 다음 단계에서는 마지막 값을 제외하고 나머지 값들에 대해 동일한 과정을 반복합니다.
- 배열이 정렬될 때까지 위 과정을 반복합니다.
3. 동작 과정
- 첫 번째 패스(pass) : 배열의 처음부터 끝까지 인접한 값들을 비교하여 큰 값을 오른쪽으로 이동시킵니다.
[5, 1, 4, 2, 8]에서5와1비교 -> 자리 바꿈 ->[1, 5, 4, 2, 8][1, 5, 4, 2, 8]에서5와4비교 -> 자리 바꿈 ->[1, 4, 5, 2, 8][1, 4, 5, 2, 8]에서5와2비교 -> 자리 바꿈 ->[1, 4, 2, 5, 8][1, 4, 2, 5, 8]에서5와8비교 -> 자리 바꾸지 않음
- 두 번째 패스(pass) : 마지막 값이 이미 가장 큰 값이므로, 그 값을 제외하고 나머지 값을 다시 비교합니다.
[1, 4, 2, 5, 8]에서1과4비교 -> 자리 바꾸지 않음[1, 4, 2, 5, 8]에서4와2비교 -> 자리 바꿈 ->[1, 2, 4, 5, 8][1, 2, 4, 5, 8]에서4와5비교 -> 자리 바꾸지 않음
- 세 번째 패스(pass) : 앞의 3요소를 비교 합니다.
[1, 2, 4, 5, 8]에서1과2비교 -> 자리 바꾸지 않음[1, 2, 4, 5, 8]에서2과4비교 -> 자리 바꾸지 않음
- 네 번째 패스(pass) : 앞의 2요소를 비교 합니다.
[1, 2, 4, 5, 8]에서1과2비교 -> 자리 바꾸지 않음
- 정렬 결과 :
[1, 2, 4, 5, 8]
4. 버블 정렬 구현 (Java)
import java.util.Arrays;
public class main {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1 ; i++) {
// 이미 정렬된 부분을 제외하고 반복
for (int j = 0 ; j < n - 1 - i ; j++) {
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
System.out.println("원본 배열 : "+Arrays.toString(arr));
bubbleSort(arr);
System.out.println("정렬된 배열 : "+Arrays.toString(arr));
}
}코드 설명
bubbleSort메서드는 배열을 입력받아 정렬하는 함수입니다.n = arr.length: 배열의 길이를 구합니다.for(int i = 0 ; i < n -1; i++): 이 반복문은 배열을 몇 번 패스할지를 결정합니다. 각 패스마다 가장 큰 값이 끝으로 이동하므로, 이미 정렬된 요소들은 다시 비교할 필요가 없습니다.
for(int j = 0; j < n - 1 - i ; j++): 이 내부 반복문에서는 인접한 두 요소를 비교하고 필요할 경우 자리를 바꾸는 작업을 수행합니다.arr[j] > arr[j+1]: 현재 값이 다음 값보다 크다면, 두 값을 자리 바꿈하여 큰 값이 뒤로 가게 합니다.
