The procedure Shellsort of Fig. 8.26, sometimes called diminishingincrement sort, sorts an array...

Question

The procedure Shellsort of Fig. 8.26, sometimes called diminishingincrement sort, sorts an array A[1..n] of integers by sorting n/2 pairs (A[i],A[n/2 + i]) for 1 ≤ i ≤ n/2 in the first pass, n/4 four-tuples (A[i], A[n/4 + i], A[n/2 + i], A[3n/4 + i]) for 1 ≤ i ≤ n/4 in the second pass, n/8 eight-tuples in the third pass, and so on. In each pass the sorting is done using insertion sort in which we stop sorting once we encounter two elements in the proper order. procedure Shellsort ( var A: array[l..n] of integer ); var i, j, incr: integer; begin incr := n div 2; while incr > 0 do begin for i := incr + l to n do begin j := i - incr; while j > 0 do if A[j] > A[j + incr] then begin swap(A[j], A[j + incr]); j := j - incr end else j := 0 { break } end; incr := incr div 2 end end; { Shellsort } a. Sort the sequences of integers in Exercises 8.1 and 8.2 using Shellsort. b. Show that if A[i] and A[n/2k + i] became sorted in pass k (i.e., they were swapped), then these two elements remain sorted in pass k + 1. c. The distances between elements compared and swapped in a pass diminish as n/2, n/4, . . . , 2, 1 in Fig XXXXXXXXXXShow that Shellsort will work with any sequence of distances as long as the last distance is 1. d. Show that Shellsort works in O (n1.5) time.

Raavikant · Accepted Answer

Answer:
To Show that Shell Sort works in O (n^1.5) time  with any sequence of distances as long as the last distance is 1. We will analyze the best case complexity and then worst case complexity.

The procedure Shellsort of Fig. 8.26, sometimes called diminishingincrement sort, sorts an array A[1..n] of integers by sorting n/2 pairs (A[i],A[n/2 + i]) for 1 ≤ i ≤ n/2 in the first pass, n/4...

Solution

Answer To This Question Is Available To Download

Related Questions & Answers