276 Part V: Algorithms: Telling the Computer What to Do
9.The seventeenth line sets the value of NoSwaps to zero. This line tells the bubble-sort algorithm that a swap’s occurring somewhere in the list, so it must repeat the WHILE-WEND loop again.
10.The eighteenth through twenty-first lines print the array on-screen so that you can see how the computer’s sorted the array so far.
11.The twenty-second line marks the end of the IF THEN statement that starts on the twelfth line.
12.The twenty-third line marks the end of the FOR-NEXT loop.
13.The twenty-fourth through twenty-sixth lines use an IF THEN statement to check whether the value of NoSwaps is equal to 1. If so, it sets the value of Time2Stop to one.
14.The twenty-seventh line marks the end of the WHILE-WEND loop. This loop stops looping only after the value of Time2Stop equals 1. This situation occurs only if the list is completely sorted.
15.The twenty-eighth through thirty-first lines print the final sorted array on-screen.
16.The thirty-second line tells the computer that the program is at an end.
For sorting small lists, the bubble-sort algorithm is fairly fast, but it’s extremely slow if you need to sort a large number of items. Even worse, the bubble-sort algorithm takes a long time to sort if one or more low values are near the end of the array, which means that the bubble-sort algorithm must run multiple times.
Shell Sort
One problem with insertion-sort and bubble-sort algorithms is that they often must move an item from the far end of a list to the front, an especially serious drawback for the bubble-sort algorithm. The shell-sort algorithm presents a simple solution to make sorting faster.
The shell-sort algorithm works by the principle of “divide and conquer.” Instead of trying to sort an entire list at a time, the shell-sort algorithm divides a larger list into multiple smaller lists. After it sorts these smaller lists, it combines them into a final sorted list.
The shell-sort algorithm doesn’t actually do any sorting; it works with an existing sorting algorithm (such as insert sort or bubble sort) to speed up the overall sorting process.
Chapter 20: Sorting 277
Basically, the shell sort works as follows:
1.It divides a long list into multiple smaller lists. (Figure 20-3 shows a list divided into three smaller lists. In this case, the shell-sort algorithm is taking every third item in the list to create three separate smaller lists.)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Initial list |
15 |
16 |
78 |
29 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15 |
|
|
29 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Step 1 and 2 |
|||
|
|
|
|
16 |
|
|
4 |
||||
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
78 |
|
|
|
|
|
|
Figure 20-3: |
|
|
|
|
|
|
|
|
|||
The shell |
|
|
|
|
|
|
|
|
|
||
15 |
4 |
78 |
29 |
16 |
Step 3 |
||||||
sort breaks |
|
||||||||||
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
||||
a large list |
|
15 |
|
78 |
|
16 |
Step 4 |
||||
into smaller |
|
|
|
|
|
|
|||||
|
|
4 |
|
29 |
|
|
|
Temporary list |
|||
lists and |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|||
then sorts |
|
15 |
4 |
16 |
29 |
78 |
Step 5 |
||||
those |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||||
4 |
15 |
16 |
29 |
78 |
Sorted list |
||||||
smaller lists. |
|
||||||||||
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2.It sorts each smaller list by using an algorithm such as insertion sort or bubble sort. In the example shown in Figure 20-3, the first minilist contains the numbers 15 and 29, which don’t need sorting. The second minilist contains the numbers 16 and 4, so it sorts their positions. The third minilist contains just the number 78.
3.It smashes all the smaller lists back into a large list. In Figure 20-3, notice that the numbers 4 and 16 are sorted.
4.It divides the long list into multiple smaller lists again but into fewer smaller lists than in Step 1. In Figure 20-3, the shell-sort algorithm divides the list into two small lists, taking every second item to create two smaller lists.
5.It repeats Steps 2 through 4 (if necessary) until a single sorted list remains. Notice that after it sorts the numbers 16 and 78, the entire list is completely sorted.
To see how the shell-sort algorithm works, run the following program, which uses shell sort to initially sort items and then uses the bubble-sort method to actually sort the items in the list:
278 Part V: Algorithms: Telling the Computer What to Do
MaxSize = 5
REDIM MyArray(MaxSize)
FOR I = 1 TO MaxSize
MyArray(I) = INT(RND(1) * 100) + 1 PRINT MyArray(I); SPACE$(1);
NEXT I
PRINT “(Initial array)”
X = INT(MaxSize / 2)
WHILE X > 0
Time2Stop = 0
Limit = MaxSize - X
WHILE (Time2Stop = 0)
Switch = 0
FOR K = 1 TO Limit
IF MyArray(K) > MyArray(K + X) THEN
TempX = MyArray(K)
MyArray(K) = MyArray(K + X)
MyArray(K + X) = TempX
Switch = K
END IF
NEXT K
Limit = Switch - X
IF Switch = 0 THEN
Time2Stop = 1
END IF
WEND
FOR I = 1 TO MaxSize
PRINT MyArray(I); SPACE$(1); NEXT I
X = INT(X / 2) WEND
FOR I = 1 TO MaxSize
PRINT MyArray(I); SPACE$(1);
NEXT I
PRINT “(Sorted array)”
END
A typical output for this program looks like this:
94 17 70 90 62 (Initial array)
62 17 70 90 94
17 62 70 90 94
17 62 70 90 94 (Sorted array)
Chapter 20: Sorting 279
The first time that the program runs, the shell-sort algorithm compares the numbers that locations 1, 3, and 5 of the array stores (94, 70, and 62, respectively). After sorting this list, it sorts the numbers in locations 2 and 4 of the array (17 and 90). Then it sorts the entire list.
To see how the shell-sort program works in detail, examine the program line by line, as follows:
1.The first through seventh lines create the variable MaxSize equal to 5, create the array MyArray to hold five integers, create a random number between 1 and 100, store it in the array MyArray, and then print the array on-screen along with the string (Initial array).
2.The eighth line creates the variable X and divides the total size of the list by 2 and stores the integer value in the X variable. In this case, the value of X is 2 (MaxSize / 2 = 2), so X tells the shell-sort algorithm to divide the long list into two smaller lists.
3.The ninth line starts a WHILE-WEND loop that continues as long as the value of X is greater than 0.
4.The tenth line creates a Time2Stop variable and sets its value to zero.
5.The eleventh line creates the variable Limit and sets its value to MaxSize - X. The first time that this line runs, the value of Limit is 5 – 2, or 3.
6.The twelfth line is the start of a WHILE-WEND loop that continues looping while the value of the Time2Stop variable is zero.
7.The thirteenth line creates the variable Switch and sets its value to zero.
8.The fourteenth line starts a FOR-NEXT loop.
9.The fifteenth line starts an IF THEN statement that checks to see whether neighboring items in the array are sorted.
10.The sixteenth through eighteenth lines compare two numbers that the array stores and switch their positions if necessary, which is the bubblesort algorithm.
11.The nineteenth line sets the value of Switch to the value of K.
12.The twenty-first line marks the end of the IF THEN statement that starts on the fifteenth line.
13.The twenty-second line marks the end of the FOR-NEXT loop.
14.The twenty-third line sets the value of Limit to Switch - X.
15.The twenty-fourth through twenty-sixth lines check to see whether the value of Switch equals zero. If so, it then sets the value of Time2Stop to one.
16.The twenty-seventh line marks the end of the WHILE loop that starts on the twelfth line.