버블정렬(Bubble Sort)
버블정렬은 선택정렬과 유사한 정렬방법으로 두 인접한 원소를 비교하여 정렬하는 방법이다. 시간복잡도가O(n^{2})
로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 버블정렬은 선택정렬과 다르게 안정 정렬이다.
-정렬 방식
- 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1) 번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
- 1회 반복시에는 배열에 맨뒤에 최댓값이 위치하게 되며 반복 때마다 배열의 뒤쪽부터 최댓값으로 정렬되어 마지막엔 오름차순으로 정렬이 마무리된다.
public class Main {
public static void main(String[] args) {
int[] arr = {7, 5, 2, 4, 3, 1, 9, 6, 0, 8};
bubbleSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
// 선택정렬 알고리즘
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
for (int j = 1; j < arr.length-i; j++) {
if (arr[j-1] > arr[j]) {
int temp = arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
}
}
}
장점
- 추가적인 메모리 소비가 거의 없다.
- 안정 정렬이다.
- 구현이 쉽다.
단점
- 비교적 많은 반복수를 요구한다.
버블정렬의 경우 많은 시간복잡도를 요구하며 사실상 거의 쓰이지 않는 알고리즘이다. 선택정렬과 같은 O(n^{2})의 시간복잡도를 갖는다 하더라도 버블정렬의 교환 횟수가 평균적으로 더 많기 때문에 거의 쓰이지 않는다.
참고
