버블정렬
- 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
6
2
7 8 1
2 6
7
8 1
2 6 7
8
1
2 6 7 8
1
2
6
7 1 8
private static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
조금 나은 버블정렬
버블 정렬은 각각 한번씩 i랑 i+1 을 비교하므로 만약 한번도 교환이 일어 나지 않았다면 정렬이 된 상태다.
그걸 이용해서 조금 더 나은 버블정렬을 구현할 수 있다.
private static void bubbleSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
boolean checked = false;
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
checked = true;
}
}
if(!checked){
break;
}
}
}