Bubble sort explained with simple example

Bubble sort is one of the simplest sorting algorithm which traverse through the list, compares items at adjacent places, and swaps them to make list sorted. After every pass of list one or more item is placed at its correct position. If in a pass, no swaps are performed then it means list becomes sorted.

Pros:
1) Simple algorithm.
2) No extra memory needed.
3) Good for cases when list is almost sorted (only few misplaced items).

Cons:
1) Very slow algorithm. Not good for very large set of data.

Algorithm explained with example:

Let us take an example array “7 9 3 12 1”. Now we will run through this array with bubble sort algorithm to understand how it works.

First Traversal:
{7, 9, 3, 12, 1} –> {7, 9, 3, 12, 1}, No swap required as 7 < 9.
{7, 9, 3, 12, 1} –> {7, 3, 9, 12, 1}, Swapped since 9 > 3.
{7, 3, 9, 12, 1} –> {7, 3, 9, 12, 1}, No swap required as 9 < 12.
{7, 3, 9, 12, 1} –> {7, 3, 9, 1, 12}, Swapped since 12 > 1.

After this first traversal, highest element is at the last place. Hence, next run we need to go through till (n – 1) elements only.

Second Traversal:
{7, 3, 9, 1, 12} –> {3, 7, 9, 1, 12}, Swapped since 7 > 3.
{3, 7, 9, 1, 12} –> {3, 7, 9, 1, 12}, No swap required as 7 < 9.
{3, 7, 9, 1, 12} –> {3, 7, 1, 9, 12}, Swapped since 9 > 1.

After this second traversal, 2nd highest element is placed at 2nd last place. Hence, next run we need to go through till (n – 2) elements only.

Third Traversal:
{3, 7, 1, 9, 12} –> {3, 7, 1, 9, 12}, No swap required as 3 < 7.
{3, 7, 1, 9, 12} –> {3, 1, 7, 9, 12}, Swapped as 7 > 1.

After this third traversal, last three items are placed at their position.

Fourth Traversal:
{3, 1, 7, 9, 12} –> {1, 3, 7, 9, 12}. Swapped as 3 > 1.

Now, the list is sorted.

Let’s have a look at the sample program for bubble sort.

void printArray(int a[] )
{
    for (int i = 0; i < 12; i++)
    {
        cout << a[i] << ", ";
    }
    cout << endl;
}

void bubbleSort()
{
    int a[] = { 76,4,65,33,23,10,44,38,97,100,1,59 };
    int numberOfElements = sizeof(a) / sizeof(a[0]);
    cout << "Bubble Sort" << endl;
    cout << "Initial Array" << endl;

    printArray(a);

    for (int i = 0; i < numberOfElements; i++)
    {
        for (int j = 0; j < (numberOfElements - i - 1); j++) { if (a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }

    cout << "Sorted Array" << endl;
    printArray(a);
}
int main()
{
    bubbleSort();
}

Output of the above program is as follows:

Bubble Sort
Initial Array
76, 4, 65, 33, 23, 10, 44, 38, 97, 100, 1, 59,
Sorted Array
1, 4, 10, 23, 33, 38, 44, 59, 65, 76, 97, 100,

Algorithm performance:

Best case performance:
Best case performance comes when the list is already sorted. In this case, only one traversal through data is needed.
Hence, time complexity for best case scenario is O(n).

Worst case performance:
Worst case performance comes when the list is reverse sorted. In this case, total number of comparison needed are (n + (n – 1) + (n – 2) + … + 1).
Hence, time complexity for worst case scenario is O(n*n).

Space complexity:
Since, no extra space is needed for this sorting algorithm. Hence, Space complexity is O(1).