Sắp xếp bong bóng

Bubble Sort là một 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 một 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.

Mức độ 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à xấu nhất
Mức độ phức tạp của không gian: O (1)

Đầu vào và Đầu ra

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( array, size)

Đầ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

Ví dụ

#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