Data Structures and Algorithms - Old Questions

9. What is sorting? Describe the Insertion sort.

Sorting is the technique to arranging the items of list in any specific order which may be ascending or descending order. 

Insertion Sort

An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm. It builds the sorted sequence one number at a time.

Suppose a[0], a[1], a[2], …………….,a[n-1] are n elements in memory, insertion sort works as follow:

Pass 1: a[0] by itself is trivially sorted.

Pass 2: a[1] is inserted either before or after a[0] so that a[0], a[1] is sorted.

Pass 3: a[2] is inserted into its proper place in a[0],a[1], that is before a[0], between a[0] and a[1], or after a[1], so that: a[0],a[1], a[2] is sorted.

……

Pass n: a[n-1] is inserted into its proper place in a[0], a[1], a[2], ……….a[n-2] so that a[0], a[1], a[2], ……….a[n-1] is sorted array with ‘n’ elements.

Algorithm for Insertion Sort:

Let a[n] be an array of size n. 

Void insertionsort(int a[], int a)

{

          int i, j, temp;

         for(i=1;i<n;i++)

        {

              temp= a[i];

              j=j--;

            while((temp<a[j])&&(j>=0))

          {

            a[j+1]= a[j];

           j= j--;

       }

      a[j+1]=temp;

    }

}

Example:

A list of unsorted elements are: 9, 7, 6, 15, 16, 5, 10, 11