개념
거품 정렬은 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.
과정
- 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … , (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
- 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
구현(Java)
void bubbleSort(int[] arr) {
int temp = 0;
for(int i = 0; i < arr.length; i++) {
for(int j= 1 ; j < arr.length-i; j++) {
if(arr[j-1] > arr[j]) { // 두 원소를 비교
// 조건에 따라 인접한 두 값을 교환
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
시간복잡도
(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.
또한, Bubble Sort는 정렬 여부와 무관하게 인접한 두 원소를 비교하기 때문에 최선, 평균, 최악의 시간복잡도가 O(n^2) 으로 동일하다.
참고
https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html
'CS > 알고리즘' 카테고리의 다른 글
기수 정렬(Radix sort) (0) | 2024.06.15 |
---|---|
병합 정렬(Merge Sort) (1) | 2024.06.14 |
퀵 정렬(Quick Sort) (0) | 2024.06.13 |
삽입 정렬(Insertion Sort) (1) | 2024.06.13 |
선택 정렬(Selection Sort) (1) | 2024.06.13 |