Bubble Sort Algorithm

Bubble sort is the most primitive sorting algorithm. It simply iterates through a list and compares two elements and swaps them to put them in order. It repeats this process until no more swaps are made.

Why Bubble Sort you may ask? You can think of the algorithm as “bubbling” the largest element to the end of the list, one at a time. In our next example, 26 is “bubbled” to the end of our list, and then 12, and finally 5. If you notice, we don’t need to compare our elements to the previously “bubbled” ones since we know those are already the greatest values and are in order.

Example of Bubble Sort:

Initial Unsorted Vector

26

5

12

-6

Iteration 1

Comparison 1: 26 vs 5 SWAP

5

26

12

-6

Comparison 2: 26 vs 12 SWAP

5

12

26

-6

Comparison 3: 26 vs -6 SWAP

5

12

-6

26

Iteration 2

5

-6

12

Comparison 4: 5 vs 12 NO SWAP
Comparison 5: 12 vs -6 SWAP

Iteration 3:

-6

5

Comparsion 6: 5 vs -6 SWAP

Note: If you noticed, we didn’t need to compare the “bubbled” elements after an iteration because we know its the largest already

Bubble Sort in C++

As you may notice below, the algorithm simply “bubbles” the largest element to the end of the list. It does this for every element, reason for the two for loops. One iterates for every element to be “bubbled”, and the other for loop to make the comparisons for the elements not sorted yet.

If no swaps were made during an iteration, the list is sorted. Therefore, no need to continue sorting.

bool swap;
    for ( unsigned i = 0; i < vec.size(); i++ )
    {
        swap = false;
        for ( unsigned j = 0; j < vec.size() - i - 1; j++ )
        {
            //If current element is greater than the next, swap them
            if ( vec[j] > vec[j+1] )
            {
                swap = true;
                swap(vec[j], vec[j+1]);
             }
        }

         //If no swaps are made, the list is in order so break out of the for loop
         if ( !swap )
                 break;
    }