Insertion Sort

An insertion sort is a way of sorting elements in ascending or descending order. The letters of a word, for example: "maple" might be sorted alphabetically and give you "aelmp". Or, numbers in a list here "25,3,56,123,2" might be sorted in order resulting in "2, 3, 25, 56, 123".

The algorithm:

    insertion_sort(item s[],int n){
         int i, j;

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

Type a word into the box below and press sort to see the letters sorted alphabetically by an insertion sort.

Word:

Description

What the algorithm does to sort elements in order. In this case the algorithm is comparing elements for alphabetic order. Parmeters passed. "s[]" is the list of items to sort. 'n' is the length of the list, i.e. number of items. So, if the list is a string, say the letters "zyx", then n = 3.

One tried and true way to understand how algorithms work is to start with the simplest cases and run them through the algorithm manually to see how they work.

For example, try the string "ba" first. Run it through the algorithm and see what it does, then try "cba" after that to see what it does. In the case of the insertion algorithm, that should be enough to figure out how the algorithm works for all cases.

The outer loop starts at the second element and moves from left to right to the end of the string. This loop makes sure that every character of the string is accounted for.

The inner loop, i.e. while loop, compares a value to all of the values to the left of it until it finds one that is smaller than it, at which point it exits. This algorithm moves from right to left, starting where the outer loop left off and compares each value in turn.

In this way all letters are accounted for, and they will end up in alphabetical order when the algorithm has done its job.