버블 정렬
인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
데이터가 두 개일 때 버블 정렬
import java.util*;
ArrayList<Integer> list = new ArrayList<>();
list.add(5);
list.add(3);
if(list.get(0) > list.get(1)) {
Collections.swap(list, 0, 1);
}
System.out.println(list); // [3, 5]
데이터가 세 개일 때 버블 정렬
import java.util.*;
ArrayList<Integer> list = new ArrayList<>();
list.add(10);
list.add(3);
list.add(5);
for(int i = 0; i < list.size() - 1; i++) {
if(list.get(i) > list.get(i + 1)) {
Collections.swap(list, i, i + 1);
}
}
System.out.println(list); // [3, 5, 10]
버블 정렬 구현
- n개의 리스트가 있는 경우 최대 n - 1번 적용
- 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정됨
- 한 번도 교환된 적이 없다면 이미 정렬된 상태, 반복 적용할 필요 없음
import java.util.*;
public class BubbleSort {
public ArrayList<Integer> sort(ArrayList<Integer> list) {
for(int i = 0; i < list.size() - 1; i++) {
boolean isSwap = false;
for(int j = 0; j < list.size() - 1 - i; j++) {
if(list.get(j) > list.get(j + 1)) {
Collections.swap(list, j, j + 1);
isSwap = true;
}
}
if(isSwap == false) {
break;
}
}
return list;
}
}
시간 복잡도
- 반복문이 두개 O(n^2), 최악일 경우 𝑛∗(𝑛−1) / 2
- 완전 정렬일 경우 O(n)
feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스
'코테 > 알고리즘' 카테고리의 다른 글
삽입 정렬 (0) | 2023.08.29 |
---|---|
선택 정렬 (0) | 2023.08.29 |
공간 복잡도 (1) | 2023.08.23 |
알고리즘 시간 복잡도 (Time Complexity) (0) | 2023.08.11 |
최대공약수 - 유클리드 알고리즘 (유클리드 호제법) (0) | 2023.01.01 |