बुलबुले की तरह

बबल सॉर्ट एक तुलना आधारित सॉर्टिंग एल्गोरिथम है। इस एल्गोरिथम में आसन्न तत्वों की तुलना की जाती है और सही क्रम बनाने के लिए उनकी अदला-बदली की जाती है। यह एल्गोरिथम अन्य एल्गोरिदम की तुलना में सरल है, लेकिन इसमें कुछ कमियां भी हैं। यह एल्गोरिथ्म बड़ी संख्या में डेटा सेट के लिए उपयुक्त नहीं है। छँटाई कार्यों को हल करने में बहुत समय लगता है।

बबल सॉर्ट तकनीक की जटिलता

• समय की जटिलता: O(n) सर्वोत्तम मामले के लिए, O(n^2) औसत और सबसे खराब स्थिति के लिए
• अंतरिक्ष जटिलता: ओ(1)

इनपुट और आउटपुट

Input:
A list of unsorted data: 56 98 78 12 30 51
Output:
Array after Sorting: 12 30 51 56 78 98

एल्गोरिदम

bubbleSort( array, size)

इनपुट - डेटा की एक सरणी, और सरणी में कुल संख्या

आउटपुट - क्रमबद्ध सरणी

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

उदाहरण

#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);
}

आउटपुट

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