Introduction

In this article, we are going to deep dive into the sorting algorithms. Sorting algos as the name suggests are used to sort arrays. There are mainly 7 types of sorting algorithms:

1. Selection sort

2. Bubble sort

3. Insertion sort

4. Merge sort

5. Quick sort

( In this article we will only be discussing Selection sort, bubble sort, and Insertion sort. Rest two algos we will discuss in another article )

Let's deep dive into each of the algorithms.

NOTE: while explaining the algorithm I would be following a pattern, in which first I would try to explain to you the algorithm, then I would write the pseudo code, after that I will do a dry run and then will give you the code of the algorithm.

Selection sort

In selection sort we pick the first element, then we consider that it has the smallest value, and then we traverse into the whole array trying to find any index that has the smallest value, then we simply swap the two indexes.

Confused?

Let's try to look at the pseudo-code.

for( int i = 0 ; i < arr.length - 1 ; i++ )
{
    smallestIndex = i;
    for( int j = i ; j < arr.length ; j++ ) 
    {
        if(arr[j] <  arr[smallestIndex])
        {
            smallestIndex = j;
        {
    // swap values at smallestIndex and j
    }
}

Let's try to understand with an example:

Let's consider this array : arr = { 8 , 5 , 0 ,1 }

1. For the first time i point at the index the 0 , so the smallestIndex is currently 0. Now we enter the second loop. For the start of the second loop, j is currently 0.

   1. Iteration 1: j is pointing at the index 0 . Is the value at the index j smaller than the value at the index smallestIndex ? FALSE

   2. Iteration 2: j is pointing at the index 1. Is the value at the index j smaller than the value at the index smallestIndex? TRUE. Now smallestIndex is pointing at the index 1.

   3. Iteration 3: j is pointing at index 2. Is the value of the index j smaller than the value of the index smallestIndex? TRUE. Now smallestIndex is pointing at the index 2.

   4. Iteration 4: j is pointing at index 3. Is the value at the index j smaller than the value at the index smallestIndex? FALSE

      So after the first iteration, our i is pointing at the index 0 and our smallestIndex is pointing at index 2, now we simply swap the values of these two indexes. So after swapping out the array, it looks somewhat like this:

      arr = { 0 , 5 , 8 , 1 }

2. Now for the second time, i will be at the index 1 and smallestIndex will also point to index 1 , and we would again do all the steps similarly, go into the second loop, and check if any index has any value smaller than the current smallestIndex , if yes re-assign the smallestIndex value, and then swap the value. After the second iteration is over, our array will look somewhat like this:

   arr = { 0 , 1, 8 , 5 }

3. In the third iteration, i will be at the index 2 and same smallestIndex will also point to the index 2. After you finish the iteration 3, our array will look alike:

   arr = { 0 , 1, 5 , 8}

And VOILLA, our array is sorted.

IMPORTANT NOTE: if you have noticed in the pseudo-code, for the first loop I am only iterating till the length - 2 index.

Let's understand with an example.

arr = { 3 ,4 , 6, 7, 8}

Let's say this is our array. For this array, the length of the array would be 5. So iterating till index - 2 means only iterating till index 3. We will not go till the last index because the last index would already be sorted as we put the biggest number at the last and also because if we look closely at the second loop we are traversing the array to compare other indexes, but at the last index we won't have any other element to compare with, so we only go till length - 2.

Let's look at the code:

Problem link

public class Solution {
    public static void selectionSort(int[] arr) {
        int length = arr.length;
        for( int i = 0 ; i < length - 1 ; i++  ) {
            int smallestIndex = i;
            for( int j = i ; j < length  ; j++  ){
                if(arr[j] < arr[smallestIndex] ) {
                    smallestIndex = j;
                }
            }
            int temp = arr[smallestIndex];
            arr[smallestIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

The time complexity of this algo is O ( n ^ 2 ), and the space complexity is O ( N ).

Bubble sort

In bubble sort, we simply compare the two adjacent indexes and then place the smallest index on the left side and the bigger index on the right side.

NOTE: in selection sort, we used to move from left to right direction in the array, placing all the smaller numbers on the left side and the larger numbers on the right side. But in bubble sort we move from right to left, placing all the bigger numbers on the right side and the smaller numbers on the left side.

Let's look at the pseudo-code for a better understanding.

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

Let's dry-run this code for a better understanding by taking a simple array.

arr = { 7 , 4 ,1 , 0 }

1. For the first time, the value of i will be 3 , so the loop will run 3 times. Then we enter the second loop where the j is initialized 0 and it will run till index 2.

   1. For the first time, j is 0, so arr[j] gives us value 7 and arr[j+1] gives us value 4 . Is 7 > 4 ? TRUE, swap occurs.

      arr = { 4 , 7 ,1 , 0 }

   2. The second time, j is 1, so arr[j] gives us value 7 and arr[j+1] gives us value 1 . Is 7 > 1 ? TRUE, swap occurs.

      arr = { 4 , 1 ,7 , 0 }

   3. For the third time, j is 2, so arr[j] gives us value 7 and arr[j+1] gives us value 0 . Is 7 > 0 ? TRUE, swap occurs.

      arr = { 4 , 1 ,0, 7 }

      Exit from the outer loop (i loop). So you see after one iteration of the outer loop we managed to place the biggest value at the end.

2. For the second time, the value of i will be 2, so the loop will run 2 times. After completing the second iteration our array will look like this:

   arr = { 1 , 0 ,4, 7 }

3. The third time, the value i will be 1, so the loop will run 1 time. After completing the second iteration our array will look like this:

   arr = { 0, 1,4, 7 }

And the loop breaks, so our array is also sorted.

IMPORTANT NOTE: If you look close in the second loop instead of going till i ,I run the loop only till i - 1 , this is because if you don't do so the j pointer will point at the last index of the array and will go on to compare the last index with j+1 value that does not exist, then it will return an error.

Code for this:

Problem link

public class Solution {
    public static void bubbleSort(int[] arr, int n) {
        for( int i = n - 1 ; i>= 0 ; i--){
            for(int j = 0 ; j < i ; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

The time complexity of this algo is O ( n ^ 2 ), and the space complexity is O ( N ).

BUT, there is an exception in this algo, what if the array is already sorted?

arr = { 1, 2, 6, 8 }

In this case, what you can do is you can simply add a swap variable in the second loop and initialize it to, and you can check if the value of the variable is 0 you can simply break the loop as the array is already sorted.

public class Solution {
    public static void bubbleSort(int[] arr, int n) {
        for( int i = n - 1 ; i>= 0 ; i--){
            int swap = 0; // intialize a variable
            for(int j = 0 ; j < i ; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swap++; // increment this on every swap
                }
            }
            if(swap == 0 ) {
                break;
            }
        }
    }
}

In this case, if the array is already sorted, the TC would be O ( N )

Insertion sort

In insertion sort, we take a chunk of numbers from the array and then sort them individually. Like first we take one number, so one number is sorted in itself. Then we take two numbers and sort them. Then we take three numbers and sort them and so on.

Let's first look at its pseudo code:

for( i = 0 , i -> n ) {
    int j = i;
    while( j > 0 && ( arr[j -1] > arr[j] ) {
        swap ( arr[j-1] , arr[j];
        j--;
    }
}

The pseudo-code is a little bit overwhelming, right?

Let's try to understand with an example.

arr = { 15, 14, 9, 8, 7 }

1. For the first time, i will be 0 , so the j will also point to the index 0 and the while loop condition is not fulfilled, so we go to the next iteration.

2. Second time i will be pointing at the index 1 , so the j will also point to the index 1 , now in while loop:

   1. For the first time j is one, so j > 0 is true, and arr[j-1] > arr[j] here is also true ( 15 > 14 ), so a swap occurs.

      arr = { 14, 15, 9, 8, 7 }

      And after this j is reduced to 0 and while the condition is not met, the loop breaks.

3. Third time i will point at the index 2, and so j will also point at the index 2, so we enter the while loop:

   1. First time, j is 2 , so is arr[1] > arr[2] ? TRUE, so a swap takes place

      arr = { 14, 9, 15, 8, 7 }

      Then j is decremented.

   2. Second-time j is 1 , so is arr[0] > arr[1] ? TRUE, so a swap takes place

   3. arr = { 9, 14, 15, 8, 7 }

      Then j is decremented, and j becomes 0, so while the loop breaks.

4. Fourth time i will point at the index 3, and so j will also point at the index 3, so we enter the while loop

   1. First time j is 3 , so is arr[2] > arr[3] ? TRUE, so a swap takes place.

      arr = { 9, 14, 8, 15, 7 }

      Then j is decremented.

   2. The second time j is 2 , so is arr[1] > arr[2] ? TRUE, so a swap takes place.

      arr = { 9, 8, 14, 15, 7 }

      Then j is decremented.

   3. Third time j is 1 , so is arr[0] > arr[1] ? TRUE, so a swap takes place.

      arr = { 8, 9, 14, 15, 7 }

      Then j is decremented and j becomes 0 and we exit the while loop

5. Similarly, for the fifth time i will point at the index 4 and so will j. After the while loop is completed our array will look something alike

   arr = { 7 ,8, 9, 14, 15 } , i.e our array will be sorted.

Wohhoo, our array is now sorted.

Now let's have a look at the actual code:

Problem link

public class Solution {
    public static void insertionSort(int[] arr, int size) {
        for( int i = 0 ; i < size ; i++ ){
            int j = i;
            while(j > 0 && ( arr[j-1] > arr[j])){
                int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
                j--;
            }
        }
    }
}

The time complexity of this algo is O ( n ^ 2 ) but the best case is O ( N ) because if the array is already sorted only the outer loop will run and we will never go inside the while loop.

The space complexity is O ( 1 ).