68 SORTING ALGORITHMS
b. Write a short paragraph that explains exactly why this third version of
bubble sort will work.
c. Does this third version of bubble sort change the worst-case analysis?
Give an analysis or justification for your answer.
d. This third version of bubble sort does change the average-case analysis.
Give a detailed explanation of what is involved in calculating this new
average-case analysis.- Develop a formal argument that proves that the largest element must be in
the correct place after the first pass of the BubbleSort loop. - Develop a formal argument that proves that if there are no swaps done on
any pass of BubbleSort, the list must now be in the correct order.
3.3 Shellsort
Shellsort was developed by Donald L. Shell. It is unusual in that it begins by
considering the full list of values as a set of interleaved sublists. On the first
pass, it may deal with sublists that are just pairs of elements. On the second
pass, it could deal with groups of four elements each. The process repeats,
increasing the number of elements per sublist and, therefore, decreasing the
number of sublists. Figure 3.1 shows the sublists that can be used in the process
of sorting a list of 16 elements.
In Fig. 3.1(a), we see that there are eight sublists of two values each, which
match up the first and ninth elements, the second and tenth elements, and so
on. In Fig. 3.1(b), we see that there are now four sublists of four values each.
The first sublist now has the elements in the first, fifth, ninth, and thirteenth
locations. The second sublist has the elements in the second, sixth, tenth, and
fourteenth locations. In Fig. 3.1(c), we see that there are two sublists, which
have the odd and even location elements in them. In the last pass, shown in
Fig. 3.1(d), we are back to one list.
The sorting of the sublists is done with just an insertion sort based on the
one in Section 3.1. This makes the algorithm
Shellsort( list, N )
list the elements to be put into order
N the number of elements in the list