Shellsort more accurately Shells sort is an important sortin

Shellsort (more accurately Shell’s sort) is an important sorting algorithm that works by applying insertion sort to each of several interleaving sublists of a given list. On each pass through the list, the sublists in question are formed by stepping through the list with an increment hi taken from some predefined decreasing sequence of step sizes, h1> . . .>hi > . . . > 1, which must end with 1. (The algorithm works for any such sequence, though some sequences are known to yield a better efficiency than others. For example, the sequence 1, 4, 13, 40, 121, . . . , used, of course, in reverse, is known to be among the best for this purpose)

a. Apply shellsort to the list

S, H, E, L, L, S, O, R, T, I, S, U, S, E, F, U, L

b. Is shellsort a stable sorting algorithm?

c. Implement shellsort, straight insertion sort, selection sort, and bubble sort in the language of your choice and compare their performance on random arrays of sizes 10n for n = 2, 3, 4, 5, and 6 as well as on increasing and decreasing arrays of these sizes.

Solution

a) Apply shellsort to the list

S, H, E, L, L, S, O, R, T, I, S, U, S, E, F, U, L
Applying shellsort to the list S
1
,H,E
1
,L
1
,L
2
,S
2
,O,R,T,I,S
3
,U
1
,S
4
,E
2
,F,U
2
,L
3
with the step-sizes 13, 4, and 1 yields the following:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
S
1
H E
1
L
1
L
2
S
2
O R T I S
3
U
1
S
4
E
2
F U
2
L
3
S
1
E
2
E
2
S
1
H FF HE
1
U
2
L
1
L
3
E
2
L
2
F S
2
E
1
OL
1
R

L
2
TS
2
II S
2
O S
3
R U
1
T S
4
S
4
TS
2
S
1
S
3
HH S
3
U
1
U
2
T L
3
L
3
TE
2
F E
1
L
1
L
2
I O R S
4
S
2
H U
1
L
3
S
1
S
3
U
2
TThe final pass
–
sorting the last array by insertion sort
–
is omitted fromthe solution because of its simplicity. Note that since relatively few elementsin the last array are out of order as a result of the work done on thepreceding passes of shellsort, insertion sort will need significantly fewer comparisons to finish the job than it would have needed if it were appliedto the initial array.

b) Is shellsort a stable sorting algorithm?
Shellsort is not stable. As a counterexample for shellsort with thesequence of step-sizes 4 and 1, consider, say, the array 5, 1, 2, 3, 1. Thefirst pass with the step-size of 4 will exchange 5 with the last 1, changing
the relative ordering of the two 1’s in the array. The second pass with the
step-size of 1, which is insertion sort, will not make any exchanges becausethe array is already sorted.

c) Implement shellsort, straight insertion sort, binary insertion sort,mergesort, and quicksort in the language of your choice and compare theirperformance

on random arrays of sizes 102, 103 , 104 ,and 105 as well as onincreasing and decreasing arrays of these sizes