Consider the following insertion-sort-like algorithm: Sort the odd-indexed eleme

Question

Consider the following insertion-sort-like algorithm: Sort the odd-indexed elements using insertion sort (leaving them in the odd-indexed locations). Sort the even-indexed elements using insertion sort (leaving them in the even-indexed locations). Sort all of the elements using (standard) insertion sort.

(a) Write the pseudo code for this algorithm,‘ without a sentinel.

(b) Assume n = 8. What is the best-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed.

(c) Assume n = 8. What is the worst-case number of comparisons? Just state the number and show your input. Otherwise, no justification needed.

(d) Calculate the number of comparisons the algorithm uses in the worst case for n even. Show your work.

Explanation / Answer

Now that you know how to insert a value into a sorted subarray, you can implement insertion sort:

    Call insert to insert the element that starts at index 1 into the sorted subarray in index 0.
    Call insert to insert the element that starts at index 2 into the sorted subarray in indices 0 through 1.
    Call insert to insert the element that starts at index 3 into the sorted subarray in indices 0 through 2.
    …
    Finally, call insert to insert the element that starts at index n1n-1n1 into the sorted subarray in indices 0 through n2n-2n2.

Pseudocode

We use a procedure INSERTION_SORT. It takes as parameters an array A[1.. n] and the length n of the array. The array A is sorted in place: the numbers are rearranged within the array, with at most a constant number outside the array at any time.

INSERTION_SORT (A)

1.     FOR j 2 TO length[A]
2.             DO key A[j]
3.                   {Put A[j] into the sorted sequence A[1 . . j 1]}
4.                    i j 1
5.                    WHILE i > 0 and A[i] > key
6.                                 DO A[i +1] A[i]         
7.                                         i i 1  
8.                     A[i + 1] key

Analysis
Best-Case:
The best case occurs if the array is already sorted. For each j = 2, 3, ..., n, we find that A[i] less than or equal to the key when i has its initial value of (j 1). In other words, when i = j 1, always find the key A[i] upon the first time the WHILE loop is run.

Therefore, tj = 1 for j = 2, 3, ..., n and the best-case running time can be computed using equation (1) as follows:

T(n) = c1n + c2 (n 1) + c4 (n 1) + c5 2 j n (1) + c6 2 j n (1 1) + c7 2 j n (1 1) + c8 (n 1)

T(n) = c1n + c2 (n 1) + c4 (n 1) + c5 (n 1) + c8 (n 1)

T(n) = (c1 + c2 + c4 + c5 + c8 ) n + (c2 + c4 + c5 + c8)

This running time can be expressed as an + b for constants a and b that depend on the statement costs ci. Therefore, T(n) it is a linear function of n.

The punch line here is that the while-loop in line 5 executed only once for each j. This happens if given array A is already sorted.

T(n) = an + b = O(n)

It is a linear function of n.

The worst-case:

The worst-case occurs if the array is sorted in reverse order i.e., in decreasing order. In the reverse order, we always find that A[i] is greater than the key in the while-loop test. So, we must compare each element A[j] with each element in the entire sorted subarray A[1 .. j 1] and so tj = j for j = 2, 3, ..., n. Equivalently, we can say that since the while-loop exits because i reaches to 0, there is one additional test after (j 1) tests. Therefore, tj = j for j = 2, 3, ..., n and the worst-case running time can be computed using equation (1) as follows:

T(n) = c1n + c2 (n 1) + c4 (n 1) + c5 2 j n ( j ) + c6 2 j n(j 1) + c7 2 j n(j 1) + c8 (n 1)

T(n) = c1n + c2 (n 1) + c4 (n 1) + c5 2 j n [n(n +1)/2 + 1] + c6 2 j n [n(n 1)/2] + c7 2 j n [n(n 1)/2] + c8 (n 1)

T(n) = (c5/2 + c6/2 + c7/2) n2 + (c1 + c2 + c4 + c5/2 c6/2 c7/2 + c8) n (c2 + c4 + c5 + c8)

This running time can be expressed as (an2 + bn + c) for constants a, b, and c that again depend on the statement costs ci. Therefore, T(n) is a quadratic function of n.

Here the punch line is that the worst-case occurs, when line 5 executed j times for each j. This can happens if array A starts out in reverse order

T(n) = an2 + bn + c = O(n2)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.