Bubble Sort là thuật toán sắp xếp dựa trên so sánh. Trong thuật toán này, các phần tử liền kề được so sánh và hoán đổi để tạo thành chuỗi chính xác. Thuật toán này đơn giản hơn các thuật toán khác, nhưng nó cũng có một số nhược điểm. Thuật toán này không phù hợp với số lượng lớn tập dữ liệu. Cần nhiều thời gian để giải quyết các công việc sắp xếp.
Sự phức tạp của Kỹ thuật Sắp xếp Bong bóng
-
Độ phức tạp về thời gian:O (n) cho trường hợp tốt nhất, O (n 2 ) cho trường hợp trung bình và trường hợp xấu nhất
-
Độ phức tạp của không gian:O (1)
Input − A list of unsorted data: 56 98 78 12 30 51 Output − Array after Sorting: 12 30 51 56 78 98
Thuật toán
bubbleSort (mảng, kích thước)
Đầu vào :Một mảng dữ liệu và tổng số trong mảng
Đầu ra :Mảng được sắp xếp
Begin
for i := 0 to size-1 do
flag := 0;
for j:= 0 to size –i – 1 do
if array[j] > array[j+1] then
swap array[j] with array[j+1]
flag := 1
done
if flag ≠ 1 then
break the loop.
done
End Mã mẫu
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bubbleSort(int *array, int size) {
for(int i = 0; i<size; i++) {
int swaps = 0; //flag to detect any swap is there or not
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //when the current item is bigger than next
swapping(array[j], array[j+1]);
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // No swap in this pass, so array is sorted
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
bubbleSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
} Đầu ra
Enter the number of elements: 6 Enter elements: 56 98 78 12 30 51 Array before Sorting: 56 98 78 12 30 51 Array after Sorting: 12 30 51 56 78 98