버블 정렬 (Bubble Sort)
버블 정렬 (Bubble Sort)
기초적인 정렬 방법 중 하나입니다. 큰 값이 끝으로 가는 것이 거품처럼 피어오른다고 해서 버블 정렬이라고 합니다.
시간 복잡도는 O(N^2) 이고 느린 편에 속합니다. 버블 정렬은 선택 정렬, 삽입 정렬 보다 느립니다.
평균적인 정렬 속도 : 버블 < 선택 < 삽입
버블 정렬은 구현이 간단하지만 효율성이 낮은 편입니다. 각 요소가 평균적으로 여러 번 비교되고 이동해야 하기 때문입니다.
동작 과정
시간 복잡도 : O(n^2)
1. 비교화 교환 : 배열을 순회하면서 현재 인덱스의 값과 다음 인덱스의 값을 비교하여 오른쪽이 큰 값이 오도록 교환합니다.
2. 반복 : 이 과정을 한 번 수행하면 가장 큰 값이 배열의 끝으로 버블링(상승)하게 됩니다. 이 과정을 반복합니다.
3. 완료 조건 : 더 이상 교환이 필요없을 때 정렬을 종료합니다.
이 결과 배열은 오름차순으로 정렬됩니다. 반대로 하면 내림차순 정렬이 됩니다.
예시
초기 배열
int[] board = {3,1,4,2,6,5};
| 3 | 1 | 4 | 2 | 6 | 5 |
index = 0
board[0] = 3이고 board[1] = 1 이므로 오른쪽으로 큰 수를 보내기 위해 자리를 바꾼다.
| 1 | 3 | 4 | 2 | 6 | 5 |
index = 1
board[1] = 3, board[2] = 4 이므로 오른쪽 수가 크므로 정렬은 일어나지 않는다.
| 1 | 3 | 4 | 2 | 6 | 5 |
index = 2
board[2] = 4, board[3] = 2 이므로 교체 합니다.
| 1 | 3 | 2 | 4 | 6 | 5 |
index = 3
board[3] = 4, board[4] = 6 이므로 교체하지 않습니다.
| 1 | 3 | 2 | 4 | 6 | 5 |
index = 4
board[4] = 6, board[5] = 5 이므로 교체 합니다.
| 1 | 3 | 2 | 4 | 5 | 6 |
한 번 순회한 결과 마지막 인덱스에 가장 큰 값 6이 들어오게 됩니다.
이 과정을 더 이상 교체 작업이 일어나지 않을 때까지 반복하여 정렬을 완성합니다.
| 1 | 2 | 3 | 4 | 5 | 6 |
Java 코드 구현
/*
버블 정렬
시간 복잡도 : O(n^2)
앞에서부터 2개씩 값을 비교하면서 작은 값을 앞으로 큰 값을 뒤로 보낸다.
한 번 선형 반복할 때 마다 마지막의 값이 정렬된 값을 가진다.
이 과정을 끝까지 반복해서 정렬을 하는 방법이다.
참고 자료 : https://www.youtube.com/watch?v=YbsQiiubO74
*/
public class BubbleSort {
public static void main(String[] args) {
int[] array = {3,1,5,9,4,8,7};
printArray(array);
bubbleSort(array);
printArray(array);
}
// 버블 정렬 시작
public static void bubbleSort(int[] array) {
bubbleSort(array, array.length-1);
}
// 버블 정렬 로직 수행
public static void bubbleSort(int[] array, int last) {
// 마지막 인덱스가 0보다 클 때까지 반복 (마지막부터 정렬된다.)
if(last > 0) {
// 반복을 하면 마지막 인덱스는 정렬이 된다.
for(int i = 1; i <= last; i++) {
if(array[i-1] > array[i]) {
swap(array, i-1, i);
}
}
// 마지막은 정렬되었기에 last - 1을 정렬하기 위해 last - 1을 입력
bubbleSort(array, last - 1);
}
}
public static void swap(int array[], int source, int target) {
int temp = array[source];
array[source] = array[target];
array[target] = temp;
}
public static void printArray(int[] array) {
for(int number : array) {
System.out.print(number + " ");
}
System.out.println();
}
}
마무리
이번에는 버블 정렬을 알아보았습니다.
다음에는 선택 정렬에 대해 알아보겠습니다.
참고 사이트
버블 정렬, 선택 정렬, 삽입 정렬
https://www.youtube.com/watch?v=Bor_CRWEIXo&t=1s
버블 정렬 구현
https://www.youtube.com/watch?v=YbsQiiubO74