Visual Basic 2008 Programming: Business Applications with a Design Perspective
Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9
Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Appendix A Appendix B Appendix C Home
Loading
Last change: February 13 2016 18:48:19.

 Chapter in PDF

Table of Contents

Appendix C: Sorting and Searching
Last change: February 13 2016 18:48:22.
<<PreviousNext>>

C.3 Shell Sort

You may have noticed that in the bubble sort, each element is moved toward its proper position one swap at a time. Many swaps are usually involved before each element reaches its final position. One approach to improve this slow movement is to initially perform the comparisons of an element with another approximately half the array away. A swap of these two elements will thus accomplish a big move. The comparisons continue until no further swap is called for. This interval of comparisons can then be cut in half. The same process is repeated. Eventually, the interval will be equal to one. When it finally finishes the comparisons with this interval, you can be sure that all elements are sorted in order. (At this stage, the sort is similar to the bubble sort, but requires much fewer swaps and rounds of comparison.)
The following example illustrates how Shell sort is performed:
Position             1          2          3          4          5
Value              38        51        23        56        34
The initial interval is computed to be slightly smaller than half of the array; that is, 2 in this case. The first element, 38, is then compared with the third element, 23. Because the two elements are out of order, they are swapped:
Position             1          2          3          4          5
Value              23        51        38       56        34
The second element, 51, is then compared with the fourth element, 56, and 38 with 34, resulting in another swap:
Position           1          2          3          4          5
Value              23        51        34        56        38

The comparisons have reached the end. Because the current round resulted in swaps, another round of comparisons with the same interval should be performed; that is, 23 with 34, 51 with 56, and 34 with 38. No swap occurs. So, the interval is reduced by half to 1, and another round of comparisons is performed until no swap occurs.

Assume X() is the array to be sorted. You can first compute the interval as follows:

Interval = CInt(Math.Ceiling(UBound(X) / 2))

Does the formula appear more complex than necessary? Actually, it is written this way to take care of a fine point. The reason will be explained shortly.

A For loop as shown here should complete a round of comparisons:

For I = 0 to UBound(X) – Interval If X(I) > X(I + Interval) Then ‘ Out of order, swap Temp = X(I) X(I) = X(I + Interval) X(I + Interval) = Temp End If Next I

The For statement sets the position of the element on the left to be compared and starts at the lower bound of the array. It should end when I + Interval is greater than the upper bound of X; that is, I should go as high as I + Interval = UBound(X). Thus, the ending value for I is Ubound(X) – Interval.

This loop is to be repeated until no swap occurs. To keep track of swaps, you can use a Boolean variable, Swapped. The variable can be set to False before executing the For loop. If a swap occurs, it is set to True. Before the outer loop is repeated, this variable can be tested, and another round of comparisons is performed only if Swapped is True.

Do Swapped = False For I = 0 to UBound(X) – Interval If X(I) > X(I + Interval) Then ‘ Out of order, swap Temp = X(I) X(I) = X(I + Interval) X(I + Interval) = Temp Swapped = True End If Next I Loop While Swapped

When the outer loop is finished, it is time to reduce the interval size by half and then repeat another round of comparisons until the interval size is zero. The entire sort procedure using the Shell sort algorithm should appear as follows:

Sub ShellSort(ByVal X() As Integer) Dim Interval As Integer Dim I As Integer Dim Swapped As Boolean Dim Temp As Integer Interval = CInt(Math.Ceiling(UBound(X) / 2)) Do Until Interval = 0 Do Swapped = False ' assume no swap For I = 0 To UBound(X) - Interval If X(I) > X(I + Interval) Then ' Out of order, swap Temp = X(I) X(I) = X(I + Interval) X(I + Interval) = Temp ' Swap occurs, so set swapped to true Swapped = True End If Next I Loop While Swapped ' Reduce the interval by half Interval = CInt(Interval / 2) Loop End Sub

Notice that two different formulas are used to compute Interval. The second formula computes Interval by converting into the integer value the quotient of the previous Interval divided by 2. CInt rounds its parameter; however, when the fractional portion is exactly .5, it rounds the parameter to the nearest even number. That is, if the parameter is 1.5, it will be rounded to 2; but if the parameter is .5, it will be rounded to 0. This is exactly what you want for it to do in the second formula. But consider the formula at the beginning. If X has two elements (thus its UBound is 1), Interval will be 0 if you use the same formula as the second one. This will mean that when X has two elements, the array will never be sorted. To ensure that Interval will be at least one, the Ceiling function, which gives the smallest integer greater than or equal to the parameter, is first used to round the number up before the result is converted to an integer by the CInt function.

You can implement a test procedure by following the same steps as outlined in the preceding section. Test the program, and you should find that this algorithm is much faster than those previously discussed.

Last change: February 13 2016 18:48:22.
  1. The Insert Sub Procedure
  2. The Insertion Sort Procedure
  3. Insertion Sort Versus Bubble Sort
  4. Testing Insertion Sort
  5. Binary Insertion Sort
  • C.3 Shell Sort
  • C.4 Quick Sort
    1. Header for Quick Sort
    2. Comparing Backward
    3. Comparing Forward
    4. The Outer Loop
    5. Sorting the Sub-arrays
    6. Terminating the Procedure
    7. The Better, the Worse
    8. Solving the Paradox
    9. The Stack Space Issue
    10. The Complete Code for Quick Sort
    11. <<PreviousNext>>