Tech by Peter Gichia

Tech by Peter Gichia

Insertion Sort and Selection Sort Algorithms

Learning sorting techniques in Java

Insertion Sort and Selection Sort Algorithms

Hello, world...

Today we are going to learn how to write some simple sorting algorithms that may come in handy especially if you're approaching a technical interview, the ability to write your own function that is capable of sorting a set of values without relying on inbuilt functions when using a particular language actually says a lot about you as a programmer.

What you are going to learn

  • How to write and explain a Selection sort algorithm

  • How to write and explain an Insertion sort algorithm

Let's jump in

Selection sort algorithm

I'm going to explain this visually in the image below before translating it into an actual code.

selectionsort.jpg

Sorting a list in ascending order in selection sort proceeds as follows :

We declare the value at index 0 as the minimum value and in our case 7, then we loop through the list comparing it with other values in the list, and if the value is less than 7 we swap the two positions. In this case, the value on the right 4 is less than 7 so we're going to swap the two positions and now 4 and 7 are sorted in ascending order and we proceed to the right checking the conditions and swapping when necessary till the list is all sorted.

Now let's look at the code

public class SelectionSort {

    public static int[] selectionSort(int[] list){

//        sort the list in ascending order 

        for (int i = 0; i < list.length; i++){

            for (int j = i + 1; j < list.length; j++){

//        compare value at list[i] and list[i+1]

                if( list[j] < list[i]){

//        swap the values if the value on the right is greater
//         than the one on the right

                    swap(list,i,j);

                }
            }
        }

        return list;
    }

    public static void swap(int[] list, int i, int j){

        int temp = list[i];

        list[i] = list[j];

        list[j]= temp;

    }
}

Insertion sort algorithm

Insertion sort is quite different, here instead of swapping values we pick them and insert them in their appropriate positions in ascending order or descending order.

insertionsort (1).png

Let's think of the numbers in the array as cards on a table and we're supposed to pick them up one at a time however as we pick up each new number we are supposed to put it on our hand in such a way that the numbers in our hands are all sorted.

First, we pick 4 and assume its sorted, when we pick up 3 we add it in front of 4 since its less than 4 then we pick 2 and insert it before 3 then 10 which is placed after 4 since its greater than all the values in the sorted array and do this to the rest of the items in the list till all the list is properly sorted.

Now let us look at the code

public class InsertionSort {

    public static int[] insertionSort(int[] list){

        for(int i = 1; i < list.length; i++){

            int curr_item = list[i];

            int prev_item_index = i - 1;

            while(prev_item_index >= 0 && curr_item < list[prev_item_index]){

                list[prev_item_index + 1] = list[prev_item_index];

                --prev_item_index;
            }

            list[prev_item_index + 1] = curr_item;


        }

        return list;
    }
}

In the algorithm above we have two variables :

previous item to store the value at the list[i -1]

current item to store the value at list[i]

Then the while statement is at the heart of the sort.It states that as long as we are within the array (prev_item_index >= 0 ) and the current number is less than the one in the array (curr_item < list[prev_item_index]), we move list[prev_item_index] to the right(list[k+1] = list[k]) and move on to the next number on the left (--prev_item_index).

Conclusion

That's pretty much about selection sort and insertion sort, just keep in mind that in selection sort the values in the list are swapped but in insertion, we move values to the right and insert the right ones on the left.

Be in touch and I'll be posting more articles on android development and data structures and algorithms.

Thank you for reading the blog. Do drop your feedback in the comments below and if you liked it, share it with your developer friends who might find it useful too. If you want to have any discussion around this topic, feel free to reach out to me on Twitter

 
Share this