Page 220 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

int temp=A[k]; // the k element to be inserted is Notes
retained in a temporal variable,
i = k-1; //at first it is the A[1] value,
which is the second value of the array
while (i >=0 && A[i] > temp)
{
A[i+1] = A[i];
i = i-1;
}
A[i+1] = temp;
}
cout << “Sorted list:” << endl; // Displaying the sorted array
for(int i=0;i < n;i++)
{
cout << A[i] << “ ”;
}
return 0;
}
The output is shown as below:

The temp variable retains the value to be inserted, which at the first run of the loop would be
A[1], being the second value as A[0] is the first value. Then the while loop checks to see if A[0] is
greater than A[1], and if it is true, a swap between the values takes place. Also, i is decremented
by 1. At the next run, A[2] is compared to A[1], and if it is greater a swap takes place, and after that
it is compared to A[0], and if its greater there is a swap between the values, if not, the proper
order has been found out.
How many compares are done? 1 + 2 + ... + (n–1) which results in O(n^2) worst case and (n–1)* 1
which is O(n) best case. Also, how many element shifts are done? 1 + 2 + ... + (n–1) on O(n^2)
worst case and 0, O(1) best case.

Advantages and Disadvantages of Insertion Sort

The advantages of Insertion Sort are:
it is easy to learn;

few lines of code;
efficient for small data sets;
stable, does not change the relative order of elements with equal keys;

LOVELY PROFESSIONAL UNIVERSITY 213