2) Consider the following insertion sort algorithm. void insertion_sort (element a[], int n) // Put a...

Transcribed Image Text:

2) 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. 2) 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 rating: 100% (QA)

a To complete the insertion sort routine you need to insert ak into its correct position among the elements a0 to ak1 Heres the code for the body of t... View the full answer