Bubble Sort In C++ With Examples

Bubble Sort Technique In C++.

Bubble Sort is the simplest of the sorting techniques.

In the bubble sort technique, each of the elements in the list is compared to its adjacent element. Thus if there are n elements in list A, then A[0] is compared to A[1], A[1] is compared to A[2] and so on.

After comparing if the first element is greater than the second, the two elements are swapped then.

=> Visit Here For The Complete C++ Course From Experts.

Bubble Sort Technique

Using the bubble sort technique, sorting is done in passes or iteration. Thus at the end of each iteration, the heaviest element is placed at its proper place in the list. In other words, the largest element in the list bubbles up.

We have given a general algorithm of bubble sort technique below.

General Algorithm

Step 1: For i = 0 to N-1 repeat Step 2
Step 2: For J = i + 1 to N – I repeat
              Step 3: if A[J] > A[i]
Swap A[J] and A[i]
[End of Inner for loop]
[End if Outer for loop]
Step 4: Exit

Here is a pseudo-code for bubble sort algorithm, where we traverse the list using two iterative loops.

In the first loop, we start from the 0^th element and in the next loop, we start from an adjacent element. In the inner loop body, we compare each of the adjacent elements and swap them if they are not in order. At the end of each iteration of the outer loop, the heaviest element bubbles up at the end.

Pseudocode

Procedure bubble_sort (array , N)
               array – list of items to be sorted
               N – size of array
begin
               swapped = false
               repeat
                             for I = 1 to N-1 
                                              if array[i-1] > array[i] then
                                                           swap array[i-1] and array[i]
                                                           swapped = true
                                              end if
                              end for
                until not swapped
end procedure

The above given is the pseudo-code for bubble sort technique. Let us now illustrate this technique by using a detailed illustration.

Illustration

We take an array of size 5 and illustrate the bubble sort algorithm.

Array entirely sorted.

The above illustration can be summarized in a tabular form as shown below:

As shown in the illustration, with every pass, the largest element bubbles up to the last thereby sorting the list with every pass. As mentioned in the introduction, each element is compared to its adjacent element and swapped with one another if they are not in order.

Thus as shown in the illustration above, at the end of the first pass, if the array is to be sorted in ascending order, the largest element is placed at the end of the list. For the second pass, the second largest element is placed at the second last position in the list and so on.

When we reach N-1 (where N is a total number of elements in the list) passes, we will have the entire list sorted.

Bubble sort technique can be implemented in any programming language. We have implemented the bubble sort algorithm using C++ and Java language below.

C++ Example

Let us see a programming Example to demonstrate the bubble sort.

#include<iostream>
using namespace std;
int main ()
{
   int i, j,temp,pass=0;
   int a[10] = {10,2,0,14,43,25,18,1,5,45};
   cout <<"Input list ...\n";
   for(i = 0; i<10; i++) {
      cout <<a[i]<<"\t";
   }
cout<<endl;
for(i = 0; i<10; i++) {
   for(j = i+1; j<10; j++)
   {
      if(a[j] < a[i]) {
         temp = a[i];
         a[i] = a[j];
         a[j] = temp;
      }
   }
pass++;
}
cout <<"Sorted Element List ...\n";
for(i = 0; i<10; i++) {
   cout <<a[i]<<"\t";
}
cout<<"\nNumber of passes taken to sort the list:"<<pass<<endl;
return 0;
}

Output:

Input list …

10      2       0       14      43      25      18      1       5       45

Sorted Element List …

0       1       2       5       10      14      18      25      43      45

Number of passes taken to sort the list:10

Java Example

class Main {
public static void main(String[] args) {
   int pass = 0;
   int[] a = {10,-2,0,14,43,25,18,1,5,45};
   System.out.println("Input List...");
   for(int i=0;i<10;i++)
   {
      System.out.print(a[i] + " ");
   }
for(int i=0;i<10;i++)
   {
   for (int j=0;j<10;j++)
      {
         if(a[i]<a[j])
         {
            int temp = a[i];
            a[i]=a[j];
            a[j] = temp;
         }
      }
pass++;
}
 
System.out.println("\nSorted List ...");
for(int i=0;i<10;i++)
   {
      System.out.print(a[i] + " ");
   }
   System.out.println("\nNumber of passes taken to complete sort:" + pass);
}
}

Output:

In both the programs, we have used an array of 10 elements and we sort it using the bubble sort technique. In both programs, we have used two for loops to iterate through the adjacent elements of the array.

At the end of each pass (outer loop), the largest element in the array is bubbled up to the end of the array. We also count the number of passes that are required to sort the entire array.

Complexity Analysis Of The Bubble Sort Algorithm

From the pseudo code and the illustration that we have seen above, in bubble sort, we make N-1 comparisons in the first pass, N-2 comparisons in the second pass and so on.

Hence the total number of comparisons in bubble sort is:

Sum = (N-1) + (N-2) + (N-3)+ … + 3 + 2 + 1

= N(N-1)/2

= O(n²) => Time complexity of bubble sort technique

Thus the various complexities for bubble sort technique are given below:

The bubble sort technique requires only a single additional memory space for the temp variable to facilitate swapping. Hence the space complexity for bubble sort algorithm is O (1).

Note that the best case time complexity for bubble sort technique will be when the list is already sorted and that will be O (n).

Conclusion

The main advantage of Bubble Sort is the simplicity of the algorithm. In bubble sort, with every pass, the largest element bubbles up to the end of the list if the array is sorted in ascending order.

Similarly for the list to be sorted in descending order, the smallest element will be in its proper place at the end of every pass.

Being the simplest and easy to implement sorting technique, bubble sort is usually taken for introducing sorting to the audience. Secondly, bubble sort is also used in application like computer graphics wherein filling of polygon edges, etc. require bubble sort to sort the vertices lining the polygon.

In our upcoming tutorial, we will learn about Selection Sort in detail.

=> Visit Here To Learn C++ From Scratch.