Bubble Sort

05 min read

Bubble sort begins by comparing the first two adjacent elements of an array, and if the first element is greater than second, then the two elements must be swapped else need not swap the element. Again second and third elements are compared and swapped if it is necessary and this process goes on until last and second last element is compared and swapped. This is the first step of Bubble sort. If there are n elements to be sorted then, the process mentioned above should be repeated n-1 times to sort the elements.

Bubble Sort Algorithm

Let’s take an unsorted array of n elements as an example: 6 2 4 9 1 3

Step 1: (First pass)

bubble sort step 1

In the first pass, there were n elements and n-1 comparisons (i.e., 6 elements and 5 comparisons). And the largest value 9 is now in place.

Note: So for the next pass, the last element 9 need not be compared (since already placed in the right position).

Step 2: (Second Pass)

Bubble sort step 2

The last element 6 need not be compared with the 9, since 9 is already placed in the right order. At the end of the second pass, the second largest value 6 is now in place.

Step 3: (Third Pass)

Bubble sort step 3

At the end of the third pass, the third largest value 4 is now in place.

Step 4: (Fourth Pass)

Bubble sort - step 4

Note:  4 6 9 have already been placed in the right position (So, no need of comparing those elements)

Here, when you take a look at the order of elements in the last step it is found that the elements are sorted, but our algorithm does not know if it is completed. This technique needs one more step without any swap to know it is sorted.

Step 5: (Fifth Pass)

bubble sort step 5

In this step 5, no swapping of elements throughout the whole pass, hence the sorting technique is stopped and the array elements were sorted in an ascending order.

Note: Since each pass places the next largest value in place, the total number of passes necessary will be (n−1). After completing the (n−1) passes, the smallest item must be in the correct position with no further processing required. Here there were 6 elements, so 5 passes (n-1).

Algorithm for Bubble Sort

start Bubble_Sort(array)

     for all elements of array

     if array[i] > array[i+1]

            swap(array[i], array[i+1])

        end if

     end for

     return array

end Bubble_Sort

Implementation of Bubble sort (Using C)

void bubble_sort(int arr[], int n)
{
int i, j, temp;
  //the first for loop n elements and n-1 passes
for(i = 0; i < n; i++)  
 {
// comparisons done at each pass
for(j = 0; j < n-i-1; j++)
  {
if( arr[j] > arr[j+1])
{
// swap the elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
 

Complexity Analysis of Bubble Sort

 

Time Complexity of Bubble Sort

In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in the 3rd pass and so on. So the total number of comparisons will be,

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1

Sum = n(n-1)/2 = ½ [ n2 – n]

i.e O(n2)

Hence the time complexity of Bubble Sort is O(n2).

Worst case time complexity: O(n2)

Average case time complexity: O(n2)

Best case time complexity: O(n) (i.e., when the list is already sorted.

 

Space Complexity of Bubble Sort

The space complexity for Bubble Sort is O(1) because only a single additional memory space is required i.e. for temp variable.

 

Advantages of Bubble sorting

  • One of the simplest sorting techniques
  • Space complexity is O(1)

Bubble sort Implementation in C++

#include <iostream>
using namespace std;
void bubble_sort(int arr[], int n);
int main()
{
    int arr[50], n, i;
    cout<<"Enter the number of elements: ";
    cin>>n;
    cout<<"\nEnter the elements: \n";
    for(i=0; i<n; i++)
        cin>>arr[i];
    bubble_sort(arr, n);
    return 0;
}
 
//Bubble sort algorithm
void bubble_sort(int arr[], int n)
{
   int i, j, temp;
   bool flag;
   for (i = 0; i < n-1; i++)
   {
     flag = 0;
     for (j = 0; j < n-i-1; j++)
     {
        if (arr[j] > arr[j+1])
        {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            flag = 1;
        }
     }
     // If no two elements were swapped by inner loop, then break
     if (flag == 0)
        break;
   }
   for (i=0; i < n; i++)
        cout<<arr[i]<<" ";
}

 

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error