Bubble Sort Algorithm

Bubble sort algorithm is one of the simplest sorting algorithm. It compares a pair of adjacent element at a time and orders them accordingly, until the entire list is sorted.* For example take number (4,2,5) If we are to sort this in an ascending order, the final result should be (2,4,5).

The algorithm first takes a pair of number (4,2) it then checks if they are in the right order by comparing these two numbers, i.e whether 4>2 or not. This clearly is not the case, thus it swaps the number resulting in (2,4) and updates the list accordingly.

New Updated List = (2,4,5)

The algorithm then takes the newly updated list to check and moves forward to check whether (4,5) is in the right order or not i.e whether 4 > 5 or not. This time this check returns the value of true, hence it does not change the order of the numbers.

New Updated List = (2,4,5)

This can be represented by this code below, where it is iterating through every element on the list, taking two numbers item[i] and item[i+1] and checking to see if they are ordered or not. If not, it calls a swap_item function.

for (int i=0; i<n-1;i++) {
if (item[i] > item[i+1]){
swap_items(item[i],item[i+1]);
}
}


• How does an algorithm know if the entire list is sorted or not? It is just ordering two elements at a time?

As the algorithm compares two elements at a time, orders them, updates the list and continues to do so till it reaches the end of the list, it is intuitive to notice that the largest element on the list is at the end of the list ie nth position after the first pass.

Similarly, in the second pass, the algorithm continues to order each and every pair of elements as a result of which the second largest element will be at positioned at n-1 position of the list.

So if the length of the list is n, it is fair to notice that if we continue this same process for n-1 times, the larger items on the list will be placed in their appropriate position and we will have a sorted list of numbers.

for (int pass=0; pass < n-1 ; pass ++) {
for (int i=0; i<n-1;i++) {
if (item[i] > item[i+1]){
swap_items(item[i],item[i+1]);
}
}
}


This is the core of bubble sort algorithm. You can implement the swap_items function as you want in your language of choice. I’ll be implementing this in C++, which is presented at the end of this blog.

Optimizations

You may have noticed that in the inner loop, i iterates from index 0 to n-1. You could do that and the code still works, but remember that after we have gone through the entire array once, the largest elements will subsequently take their positions. So we could reduce some extra checking by limiting checks that are already ordered. For example after the first pass it’s okay even if we do not check the second last and the last element as we are certain that the largest element is already at the final position and the order will likely remain the same, even if we do so.

We can limit this check by limiting the value of i from n-1 to n-1-pass

Code

#include<iostream>
using namespace std;

void printArray(int arr[], int size) {
for(int i=0; i< size; i++) {
cout << arr[i] << " ";
}
}

void swap_items(int *i, int *j){
// (i,j) => (j,i)
int temp = *i;
*i = *j;
*j = temp;
}

void bubblesort(int arr[], int n){
for (int pass=0; pass<n-1; pass++){
//This is n-1 because we after n-1 pass,
//the largest n-1 elements will be in their app position
//and we can be sure that the array is sorted
cout << "-----------------" << endl;
cout << "Pass: " << pass << endl;
cout << "-----------------" << endl;
for (int i=0; i < n-1-pass ; i++) {
// This is to iterate over the array.

if (arr[i] > arr[i+1]) {
swap_items(&arr[i],&arr[i+1]);
}
printArray(arr,n);
cout << endl;
}
}
}
int main(){
int arr[] = {1,6,90,15,2};
int n = sizeof(arr[1]);
bubblesort(arr,n);
cout << "Sorted Array: \n";
printArray(arr,n);
return 0;
}


Result

The first figure is when you limit i to n-1-pass and second figure is when you iterate over the full array. There is one other optimization possible in this code.

· algorithms