반응형
버블 정렬(Bubble Sort)
앞에서부터 두 개씩 자기 옆에 있는 값과 비교 → 작은 값은 앞으로 큰 값은 뒤로 바꾸면서 정렬하는 방법
첫 번째 루프
| 3 | 5 | 4 | 2 | 1 |
1. 3과 5를 비교: 작은 값(3)은 앞에, 큰 값(5)은 뒤에 있으니까 통과
| 3 | 5 | 4 | 2 | 1 |
2. 5와 4를 비교: 작은 값(4)은 뒤에, 큰 값(5)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 3 | 4 | 5 | 2 | 1 |
| 3 | 4 | 5 | 2 | 1 |
3. 5와 2를 비교: 작은 값(2)은 뒤에, 큰 값(5)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 3 | 4 | 2 | 5 | 1 |
| 3 | 4 | 2 | 5 | 1 |
4. 5와 1을 비교: 작은 값(1)은 뒤에, 큰 값(5)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 3 | 4 | 2 | 1 | 5 |
- 5는 정렬 완료
두 번째 루프
| 3 | 4 | 2 | 1 | 5 |
1. 3과 4를 비교: 작은 값(3)은 앞에, 큰 값(4)은 뒤에 있으니까 통과
| 3 | 4 | 2 | 1 | 5 |
2. 4와 2를 비교: 작은 값(2)은 뒤에, 큰 값(4)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 3 | 2 | 4 | 1 | 5 |
| 3 | 2 | 4 | 1 | 5 |
3. 4와 1을 비교: 작은 값(1)은 뒤에, 큰 값(4)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 3 | 2 | 1 | 4 | 5 |
- 4와 5는 정렬 완료
세 번째 루프
| 3 | 2 | 1 | 4 | 5 |
1. 3과 2를 비교: 작은 값(2)은 뒤에, 큰 값(3)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 2 | 3 | 1 | 4 | 5 |
| 2 | 3 | 1 | 4 | 5 |
2. 3과 1을 비교: 작은 값(1)은 뒤에, 큰 값(3)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 2 | 1 | 3 | 4 | 5 |
- 3과 4와 5는 정렬 완료
네 번째 루프
| 2 | 1 | 3 | 4 | 5 |
1. 2와 1을 비교: 작은 값(1)은 뒤에, 큰 값(2)은 앞에 있으니까 자리를 바꿔줌
- 바꾼 결과
| 1 | 2 | 3 | 4 | 5 |
- 배열 정렬 완료!
버블 정렬
- 정의: 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘
- 시간 복잡도: 앞에서부터 1개 씩 뒤로 가면서 전체 배열 방을 돌기 때문에 O(n2)의 시간 복잡도를 가짐
- 시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2 이므로, O(n2)
- Bubble Sort는 정렬 여부와 관계 없이, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n2)으로 동일
- 공간 복잡도: 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)
- 장점
- 구현이 매우 간단하고, 소스코드가 직관적
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요 X => 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort)
- 단점
- 시간복잡도가 최악, 최선, 평균 모두 O(n2) -> 비효율적
- 원소의 정렬을 위해 교환 연산(swap)이 많이 일어나게 됨
버블 정렬 자바로 구현해보기
public class Test {
private static void bubbleSort(int[] arr){
bubbleSort(arr, arr.length - 1); // 재귀함수 호출
/*
배열의 주소와 배열에서 정리가 안 된 부분 마지막 인덱스를 같이 넘김
처음에는 모든 배열 방이 다 정렬이 안 된 상태 -> 정렬이 안 된 부분의 마지막 인덱스 == 배열의 마지막 인덱스
*/
}
private static void bubbleSort(int[] arr, int last){
if(last > 0){ // 마지막 인덱스가 0보다 클 때까지 재귀 함수 호출
/*
[ 마지막 인덱스가 0보다 크다는 말의 의미 ]
버블 정렬의 조건과 특징
1. 버블 정렬은 해당 인덱스와 바로 옆에 붙어있는 인덱스의 값을 비교하는 것이므로 2개 이상의 값이 필요함
2. 버블 정렬을 한 번 마칠 때마다(한 번의 루프롤 돌 때마다) 정렬이 완료되는 값이 +1씩 생김 == 정렬이 완료 되지 않은 값들이 -1씩 줄어듦(배열의 끝부터 차례대로 정렬)
ex. [3, 5, 4, 2, 1]의 배열 존재
버블 정렬을 하기 위해 루프를 돌 때마다 [3, 4, 2, 1, '5'] [3, 2, 1, '4', '5'] [2, 1, '3', '4', '5'] ['1', '2', '3', '4', '5']의 순서로 변경됨
['1', '2', '3', '4', '5']를 보면 정렬이 끝이 난 상태 ==> 그렇게 되면 이제 정렬이 안 된 부분의 마지막 인덱스는 없게 되므로 last = 0이 된다.
따라서 마지막 인덱스가 0보다 크다의 의미는 정렬이 안 된 부분이 남아 있다는 의미가 됨.
cf) 마지막 인덱스 == 0 : 정렬이 끝이 남남
*/
for(int i = 1 ; i <= last; i++){
if(arr[i - 1] > arr[i]){ // 내 앞에 있는 애가 나보다 큰가?
swap(arr, i - 1, i); // 자리를 바꿈
}
}
bubbleSort(arr, last - 1); // 루프를 한 번 돌면 기존의 정렬이 안 된 부분의 마지막 인덱스가 정렬이 완료 된 상태이므로 마지막 인덱스는 빼고(== -1을 해준 후) 다시 재귀 함수 호출
}
}
private static void swap(int[] arr, int source, int target) {
/*
ex. arr = [5, 3];
0 1
source = 0 (== 내 앞에 존재하는 값의 인덱스)
target = 1 (== 나의 인덱스)
*/
int temp = arr[source]; // 내 앞에 존재하는 값(arr[0] == 5)을 temp에 넣어줌 (temp == 5)
arr[source] = arr[target]; // 나의 값(arr[1] == 3)을 내 앞의 인덱스(arr[0] = 3)에 넣어줌
arr[target] = temp; // 저장해뒀던 내 앞에 존재하는 값(temp == 5)을 내 인덱스(arr[1] = 5)에 넣어줌
// 결과 -> [3, 5]
}
private static void printArray(int[] arr){
// 값이 잘 나오는지 확인하기 위한 용도의 메소드
for(int data : arr){
System.out.println(data + ", ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {3, 5, 4, 2, 1};
printArray(arr); // 정렬 하기 전 배열 출력
bubbleSort(arr); // 정렬
printArray(arr); // 정렬을 한 뒤의 결과 출력
}
}
코드만 정리
public class Test {
private static void bubbleSort(int[] arr){
bubbleSort(arr, arr.length - 1); // 재귀함수 호출
}
private static void bubbleSort(int[] arr, int last){
if(last > 0){
for(int i = 1 ; i <= last; i++){
if(arr[i - 1] > arr[i]){
swap(arr, i - 1, i);
}
}
bubbleSort(arr, last - 1);
}
}
private static void swap(int[] arr, int source, int target) {
int temp = arr[source];
arr[source] = arr[target];
arr[target] = temp;
}
private static void printArray(int[] arr){
for(int data : arr){
System.out.print(data + ", ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {3, 5, 4, 2, 1};
printArray(arr);
bubbleSort(arr);
printArray(arr);
}
}
출력 결과
출처
https://www.youtube.com/watch?v=QAyl79dCO_k
728x90
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘 정렬] 자바(JAVA)로 알아보는 퀵 정렬(Quick Sort) (0) | 2022.03.26 |
|---|---|
| [이코테 2021 강의] 1. 알고리즘 성능평가 (자바 코드 예시) (0) | 2022.03.19 |
댓글