Bubble Sort

Bubble sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing adjacent elements, and swapping them if they are in the wrong order. This process repeats until no more swaps are needed, which means the list is sorted. Despite its simplicity, bubble sort is inefficient for large datasets.

Here's a more detailed explanation of the bubble sort algorithm:

Initialization: The algorithm starts with the first element of the list.
Comparison and Swap: It compares the current element with the next element in the list. If the current element is greater than the next element, they are swapped.
Pass Through the List: The algorithm then moves to the next element and repeats the comparison and swap process until it reaches the end of the list. This completes one pass.
Repeat: The process is repeated for the entire list. After each pass, the largest element in the unsorted section of the list moves to its correct position at the end of the list.
Optimization: An optimized version of bubble sort checks if any swaps were made during a pass. If no swaps were made, the list is already sorted, and the algorithm can terminate early.
Worst-Case and Average Complexity: The time complexity of bubble sort in the worst and average case is O(n2)O(n^2)O(n2), where nnn is the number of elements in the list. This is because each element is compared with every other element.
Best-Case Complexity: The best-case time complexity is O(n)O(n)O(n), which occurs when the list is already sorted. The algorithm only needs to pass through the list once to confirm that it is sorted.
Space Complexity: Bubble sort has a space complexity of O(1)O(1)O(1) because it only requires a constant amount of additional memory space for the swapping process.

Example

Consider the following example to illustrate bubble sort:

Unsorted List: [5, 3, 8, 4, 2]

Pass 1:

Compare 5 and 3, swap: [3, 5, 8, 4, 2]
Compare 5 and 8, no swap: [3, 5, 8, 4, 2]
Compare 8 and 4, swap: [3, 5, 4, 8, 2]
Compare 8 and 2, swap: [3, 5, 4, 2, 8]

Pass 2:

Compare 3 and 5, no swap: [3, 5, 4, 2, 8]
Compare 5 and 4, swap: [3, 4, 5, 2, 8]
Compare 5 and 2, swap: [3, 4, 2, 5, 8]
Compare 5 and 8, no swap: [3, 4, 2, 5, 8]

Pass 3:

Compare 3 and 4, no swap: [3, 4, 2, 5, 8]
Compare 4 and 2, swap: [3, 2, 4, 5, 8]
Compare 4 and 5, no swap: [3, 2, 4, 5, 8]
Compare 5 and 8, no swap: [3, 2, 4, 5, 8]

Pass 4:

Compare 3 and 2, swap: [2, 3, 4, 5, 8]
Compare 3 and 4, no swap: [2, 3, 4, 5, 8]
Compare 4 and 5, no swap: [2, 3, 4, 5, 8]
Compare 5 and 8, no swap: [2, 3, 4, 5, 8]

Pass 5:

Compare 2 and 3, no swap: [2, 3, 4, 5, 8]
Compare 3 and 4, no swap: [2, 3, 4, 5, 8]
Compare 4 and 5, no swap: [2, 3, 4, 5, 8]
Compare 5 and 8, no swap: [2, 3, 4, 5, 8]

Sorted List: [2, 3, 4, 5, 8]

Key Points

Stability: Bubble sort is a stable sort. This means that it maintains the relative order of records with equal keys.
Adaptability: Although bubble sort is generally inefficient, its adaptability to nearly sorted lists makes it useful in specific scenarios where only a few elements are out of order.

Simple Implementation: Its straightforward logic and easy implementation make bubble sort an educational tool for understanding the basics of sorting algorithms.

  #include<iostream>
  using namespace std;
  class BubbleSort
  {
      int a[20],length,i,j;
      public:
          BubbleSort()
          {
              length=5;
          }
          void input_length()
          {
              cout<<"Enter length"<<endl;
              cin>>length;
          }
          void input_array()
          {
              cout<<"Enter array elements"<<endl;
              for(i=0;i<length;i++)
              {
                  cin>>a[i];
              }    
          }
          void display_array()
          {
              for(i=0;i<length;i++)
              {
                  cout<<a[i]<<" "<<endl;
              }    
          }
          void bubbleSort()
          {
              for(i=0;i<length;i++)
              {
                  for(j=0;j<length-i-1;j++)
                  {
                       if(a[j]>a[j+1])
                       {
                           int temp=a[j];
                           a[j]=a[j+1];
                           a[j+1]=temp;
                       }
                  }
              }
          }
  };

  int main()
  {
      BubbleSort ob;
      ob.input_length();
      ob.input_array();
      cout<<"Array elements before sorting"<<endl;
      ob.display_array();
      ob.bubbleSort();
      cout<<"Array elements after sorting"<<endl;
      ob.display_array();
      return 0;
  }