Question

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

//code for insertion sort

for(int k=1;k<n;k++)

{

int element=a[k];

int i=k-1;

while(i>=0&&a[i]>element)

{

a[i+1]=a[i];

i=i-1;

}

a[i+1]=element;

}

and for complexity

// hope it will help you.