Sorting algorithm simplified: Insertion, Selection and Bubble sort

Posted: April 05, 2024

Photo Credit: Jan Antonin Kolar

Generally, sorting is the first technique when it comes to learning algorithms. There are some basic sorting algorithms such as Selection sort, Bubble sort and Insertion sort which people learn as they start practicing DSA. When I was learning these sorting algorithms, it was difficult for me to understand and memorize the approach. I tried multiple times, wrote it on paper, and placed a printed poster in front of my desk but I was not able to code by myself. I had to take the references from the websites. After wasting some papers and my desk’s free space, I focused on their names and made a better way to memorize the approach. In this blog I am going to share that approach. But before we proceed further, I had a confusion about insertion sort. Why do we call it insertion while there isn’t any insert operation in logic. By reading it some people might say that there are not any bubbles popping out or selection is happening in bubble sort and selection respectively. To answer those queries I would say please read the whole article.

Selection sort

Firstly, we are going through a selection sort. By name itself, it is indicating selection and sorting, meaning order elements either in increasing order or decreasing order by selecting them. Having said that, we need to select the smallest item (as we will order elements in increasing order) from an array of [4,6,3,2,1]. But how do we know the smallest element in an array, for that we will iterate through the array and decide the smallest. I am writing code in java so it would be easy if you have some basic knowledge of java programming or otherwise it is quite understandable if you have some basic programming knowledge.

int smallest = arr[0]; //let's say we assume that first element is the smallest
for(int i=1;i<arr.length;i++){ // hence we assume the first element as the smallest, then no need to compare
	if(arr[i] <= smallest){
		smallest = arr[i];
	}
}

After we get the smallest element, we will replace it with our first element. Why first element? because the increasing array the smallest element comes first.

arr[0] = smallest;
// but wait, if we do this we will override the array and first element's value will be gone

To avoid that, we will store the smallest value’s index for swapping. So the code will look like this:

int smallest = arr[0]; //let's say we assume that first element is the smallest
int smallestIndex = 0 // initial we take the smallest index as zero because we assume first element as smallest
for(int i=1;i<arr.length;i++){ // hence we assume the first element as smallest then no need to compare
	if(arr[i] <= smallest){
		smallest = arr[i];
		smallestIndex = i;
	}
}

int temp = arr[0];
arr[0] = smallest;
arr[smallestIndex] = temp;
//wait is the array sorted? let's see
//Current array values: [1,6,3,2,4]

Here we can see that only the first position is sorted and the rest of them are still unsorted. So, our next step is to sort the second position and then third, fourth up to nth position which means here is 5th position which is nothing but length of the array. For doing this task we need to iterate over the array n times which is the length of the array using a loop and also keep a track of which position we are currently sorting.

for(int j=0;j<arr.length;j++){
	int position = j; //we start from index j as our position to sort
	int smallest = arr[j]; //let's say we assume that first element is the smallest
	int smallestIndex = j // initial we take smallest index as zero because we assume first element as smallest
	for(int i=j;i<arr.length;i++){ // assign i to j as we update range for getting smallest element
		if(arr[i] <= smallest){
			smallest = arr[i];
			smallestIndex = i;
		}
	}
	int temp = arr[position]; //need update the position to sort at every iteration
	arr[position] = smallest;
	arr[smallestIndex] = temp;
}

And that’s it, selection sort done. First we built logic for the first element to sort. But as we go further we realize that we need to adapt the same logic for all the positions, for that we just add another loop on that smallest element loop and update the sort position and range for finding the smallest element. As you might have noticed that to sort an array using selection sort the only thing needed to know is we have to select the smallest or greatest element from the array nothing else

Bubble sort

In bubble sort, the core idea is to bubble out the smallest or greatest element such that the bubble floats to the surface of the water. Let’s take the same array [4,6,3,2,1]. As the bubble generates at the bottom of the water and floats towards the surface, think array as vertical, bottom would be index 0 and surface would be index last position here it is 4. To bubble out the greatest element we need to compare the subsequent elements because if we select the greatest bubble and instantly assign to the surface that it will become a teleportation of the bubble or other way around the approach would become similar to selection sort.

for(int i=1;i<arr.length;i++){
	if(arr[i] <= arr[i-1]){
		int temp = arr[i];
		arr[i] = arr[i-1];
		arr[i-1] = temp;
	}
}

After doing iteration current array values are [4,3,2,1,6]. But if you take a look at the surface I mean at the last index of the array it is sorted, it bubbles out from the rest of them. So, the same pattern will be executed for the remaining of them. To do that we need to follow this process for n time meaning total length of the array.

for(int j=0;j<arr.length;j++){
	for(int i=1;i<arr.length;i++){
		if(arr[i] <= arr[i-1]){
			int temp = arr[i];
			arr[i] = arr[i-1];
			arr[i-1] = temp;
		}
	}
}

That’s it, the code is done. Elements are sorted in increasing order. But if you examine the code a little bit, we are comparing the already sorted elements. Once the loop runs a couple of times the last two indexes of the array will be sorted and there is no need to compare them. And to remove that comparison we need to minimize the range to unsorted portions by times the loop runs. First time loop runs, include all elements then second time it runs ignore the last element meaning reduce the range by one, third time loop runs, reduce the range by two. If you are following the pattern the range = ith time loop runs - 1. This reduction happens from the later part of the array so the range would be 1 (as we are comparing current element to previous element) to n - ith time loop runs - 1.

for(int j=0;j<arr.length;j++){
	for(int i=1;i<=arr.length-j-1;i++){ //here we need to add less than equal to include last element in first iteration
		if(arr[i] <= arr[i-1]){
			int temp = arr[i];
			arr[i] = arr[i-1];
			arr[i-1] = temp;
		}
	}
}

Having this little bit optimization, bubble sort is complete and memorized to the end of the life.

Insertion sort

In insertion sort, the name itself can’t give us logical hints. But the approach of insertion sort is related to the sub-array and shifting. So, memorize insertion sort for sub-array and shifting. Let’s take the same array [4,3,2,1,6]. Sub-array means choosing a contiguous part of an array. First take the first element as a subarray as this is only one element and it is sorted, so start with the first two elements of the array and keep in mind that if the current element is smaller than the previous element then place current element to previous element’s positions and shift the subarray by 1 index. Increase the range one by one in each iteration.

for(int j=1;j<arr.length;j++){ // increase range by 1
	int currentElement = arr[j]; // store the current element

	//run while loop from previous element to current element
	int i = j-1;
	while(i>=0 && arr[i] > currentElement){
		arr[i+1] = arr[i]; // override the value
		i = i - 1;
	}
	arr[i+1] = currentElement; // override the currentElement where the loop ends
}

This sorting method may seem a little hard to understand. But keeping the idea of shifting and replacing we can make it a little easier to understand.

We are done. I have shared my approach to understand these basic algorithms yet still relevant for logic building in an age of AI. I hope you like it and please try these approaches to understand these better.