1. 버블정렬이란?
인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘이다. 왜 버블정렬일까? 가장 큰 요소가 배열의 마지막 위치로 버블처럼 떠오른다고 하여 '버블정렬' 이라는 이름으로 유래됨.
2. 시간복잡도
각 정렬 과정마다 다시 한번 배열을 순회하여 인접한 두 요소를 비교해야 하므로 O(N^2) 의 시간복잡도를 가진다.
3. 핵심이론
1) 배열 사이즈가 N이라고 가정한다.
2) 버블 정렬은 총 (N - 1)번의 과정을 거친다.
3) 각 정렬 과정마다 맨 끝 요소는 정렬이 된 상태이므로 (N - i - 1)번 순회한다.
4) 이전 요소가 다음 요소보다 크면 swap 진행
5) 위 과정 반복
4. 예시
아래 N이라는 배열이 있다고 가정하자.
5 | 4 | 3 | 2 | 1 |
1) 첫번째 순회
4 | 5 | 3 | 2 | 1 |
4 | 3 | 5 | 2 | 1 |
4 | 3 | 2 | 5 | 1 |
4 | 3 | 2 | 1 | 5 (가장 큰 요소가 배열의 끝에 옴) |
첫번째 순회는 총 4번 (N - 0 - 1) 번 진행한다.
2) 두번째 순회
3 | 4 | 2 | 1 | 5 |
3 | 2 | 4 | 1 | 5 |
3 | 2 | 1 | 4 (그 다음 큰 요소가 배열의 끝에 옴) |
5 (이미 정렬 완료) |
두번째 순회는 총 3번 (N - 1 - 1)번 순회한다.
3) 세번째 순회
2 | 3 | 1 | 4 | 5 |
2 | 1 | 3 (그 다음 큰 요소가 배열의 끝에 옴) |
4 (이미 정렬 완료) |
5 (이미 정렬 완료) |
세번째 순회는 총 2번 (N - 2 - 1)번 순회한다.
4) 네번째 순회
1 | 2 (그 다음 큰 요소가 배열의 끝에 옴) |
3 (이미 정렬 완료) |
4 (이미 정렬 완료) |
5 (이미 정렬 완료) |
총 네 번 (N - 1번)의 정렬 과정의 (N - i - 1)번의 비교 과정으로 버블정렬은 종료된다.
예시 코드
public class Main {
public static void bubbleSort(int[] arr){
// 버블정렬 수행
for(int i = 0; i < arr.length - 1; i++){
for(int j = 0; j < arr.length - i - 1; j++){
if(arr[j + 1] < arr[j]){
swap(arr, j + 1, j);
}
}
}
}
// swap 함수
public static void swap(int[] arr, int t1, int t2){
int temp = arr[t1];
arr[t1] = arr[t2];
arr[t2] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
bubbleSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
출력 결과 : 1 2 3 4 5
'알고리즘 공부' 카테고리의 다른 글
[정렬] 퀵정렬 (Quick Sort) - Java (0) | 2024.09.07 |
---|---|
[정렬] 선택정렬 (Selection Sort) - Java (0) | 2024.09.07 |
[백준] 11659번 문제 구간 합 구하기 4 - JAVA (0) | 2024.08.30 |
[프로그래머스] 타겟 넘버 - JAVA (0) | 2024.08.23 |
[프로그래머스] K번째수 (0) | 2024.08.17 |
1. 버블정렬이란?
인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘이다. 왜 버블정렬일까? 가장 큰 요소가 배열의 마지막 위치로 버블처럼 떠오른다고 하여 '버블정렬' 이라는 이름으로 유래됨.
2. 시간복잡도
각 정렬 과정마다 다시 한번 배열을 순회하여 인접한 두 요소를 비교해야 하므로 O(N^2) 의 시간복잡도를 가진다.
3. 핵심이론
1) 배열 사이즈가 N이라고 가정한다.
2) 버블 정렬은 총 (N - 1)번의 과정을 거친다.
3) 각 정렬 과정마다 맨 끝 요소는 정렬이 된 상태이므로 (N - i - 1)번 순회한다.
4) 이전 요소가 다음 요소보다 크면 swap 진행
5) 위 과정 반복
4. 예시
아래 N이라는 배열이 있다고 가정하자.
5 | 4 | 3 | 2 | 1 |
1) 첫번째 순회
4 | 5 | 3 | 2 | 1 |
4 | 3 | 5 | 2 | 1 |
4 | 3 | 2 | 5 | 1 |
4 | 3 | 2 | 1 | 5 (가장 큰 요소가 배열의 끝에 옴) |
첫번째 순회는 총 4번 (N - 0 - 1) 번 진행한다.
2) 두번째 순회
3 | 4 | 2 | 1 | 5 |
3 | 2 | 4 | 1 | 5 |
3 | 2 | 1 | 4 (그 다음 큰 요소가 배열의 끝에 옴) |
5 (이미 정렬 완료) |
두번째 순회는 총 3번 (N - 1 - 1)번 순회한다.
3) 세번째 순회
2 | 3 | 1 | 4 | 5 |
2 | 1 | 3 (그 다음 큰 요소가 배열의 끝에 옴) |
4 (이미 정렬 완료) |
5 (이미 정렬 완료) |
세번째 순회는 총 2번 (N - 2 - 1)번 순회한다.
4) 네번째 순회
1 | 2 (그 다음 큰 요소가 배열의 끝에 옴) |
3 (이미 정렬 완료) |
4 (이미 정렬 완료) |
5 (이미 정렬 완료) |
총 네 번 (N - 1번)의 정렬 과정의 (N - i - 1)번의 비교 과정으로 버블정렬은 종료된다.
예시 코드
public class Main {
public static void bubbleSort(int[] arr){
// 버블정렬 수행
for(int i = 0; i < arr.length - 1; i++){
for(int j = 0; j < arr.length - i - 1; j++){
if(arr[j + 1] < arr[j]){
swap(arr, j + 1, j);
}
}
}
}
// swap 함수
public static void swap(int[] arr, int t1, int t2){
int temp = arr[t1];
arr[t1] = arr[t2];
arr[t2] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
bubbleSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
출력 결과 : 1 2 3 4 5
'알고리즘 공부' 카테고리의 다른 글
[정렬] 퀵정렬 (Quick Sort) - Java (0) | 2024.09.07 |
---|---|
[정렬] 선택정렬 (Selection Sort) - Java (0) | 2024.09.07 |
[백준] 11659번 문제 구간 합 구하기 4 - JAVA (0) | 2024.08.30 |
[프로그래머스] 타겟 넘버 - JAVA (0) | 2024.08.23 |
[프로그래머스] K번째수 (0) | 2024.08.17 |