Question

Consider the following insertion sort algorithm.

void insertion_sort(element a[], int n)
// Put a[0]..a[n-1] into ascending order by insertion sort.
{
for (int k = 1; k < n; k++) {
// At this point, a[0]..a[k-1] are already in order.
// Insert a[k] where it belongs among a[0]..a[k].
You need to write code for this insertion as the body
of the for-k loop.
}//endfor k
}

a) Write the code for the body of the for-k loop to complete the insertion sort routine.

b) Count the precise best case and worst case number of “element comparisons” in your insertion sort routine. Your answers should be functions of n in closed form. Note that “closed form” means that you must resolve all sigmas and …’s. Asymptotic answers (such as ones that use big-oh, big-theta, etc.) are not acceptable.

Answer 1

a.)

        for (int k = 1; k < n; k++)
        {
                int key = a[k];
                int j = k - 1;

                /* Move elements of a[0..i-1], that are
                greater than key, to one position ahead
                of their current position */
                while (j >= 0 && a[j] > key)
                {
                        a[j + 1] = a[j];
                        j = j - 1;
                }
                a[j + 1] = key;
        }

b.)

Worst case number of compisions: (n*(n-1))/2

Best case number of compisions: 0

NOTE: Worst case occurs when the elements of the array sorted in decreasing order.

Best case occurs when the elements of the array are sorted in increasing order.