top of page
  • LinkedIn
  • Facebook
  • YouTube
  • Twitter
  • Instagram
  • Pinterest
  • Tumblr
  • Vkontakte

Bubble Sort - Your Sorting 101 Guide

Updated: Jun 3, 2022

Algorithm


Bubble sort is one of the simplest sorting algorithms. Bubble sort works by scanning (passing) the given array multiple times and repeatedly swapping adjacent elements until all elements in the array are sorted. In each pass, the largest element is pushed or bubbled to its correct position towards the end of the array. Hence the name bubble sort.


During its processing bubble sort segregates the array into two parts, sorted portion and unsorted portion. Sorted portion (sorted elements) will be towards the end of the array. In each pass once the elements are moved to their correct position in the array (sorted portion), there is no need to compare those elements again.


For a given input array arr that needs to be sorted in ascending order, bubble sort does the following steps:

  1. Bubble sort compares adjacent elements and swaps them if they are not in correct order.

  2. We start by comparing the first and second element in the array. If first element is greater than second element, that means they are not in correct order, so we swap them. If first element is less than second element, that means they are in correct order, so there is no need to swap. If first and second elements are equal then also there is no need to swap, because whether we swap them or not it doesn't make any difference to the output (however if you want your algorithm to be stable, then you should not be swapping them).

  3. Next we move on to compare the second and third element and repeat the comparisons mentioned in step 2. Then we compare third and fourth elements and so on until we reach the end of the array. This comparison procedure, described in step 2 to 3, from first element to the last element is known as one "pass" on the array.

  4. For an array of size n, we need a total of n-1 such passes on the array for it to be fully sorted.

  5. Also in each pass one element is moved to its correct sorted position in the array, we don't have to consider this element again in the next pass as it is already sorted.


Simulation


Consider we are given the below input array: