280 Part V: Algorithms: Telling the Computer What to Do

17.The twenty-eighth through thirty-first lines print the partially sorted array on-screen.

18.The thirty-second line divides X by 2 and stores the integer value into the X variable. This tells the shell-sort algorithm how many smaller lists into which to divide the larger list.

19.The thirty-third line marks the end of the WHILE-WEND loop.

20.The thirty-fourth through thirty-seventh lines print the final sorted array on-screen.

21.The thirty-eighth line tells the computer that the program is at an end.

Quicksort

One of the more popular sorting algorithms is known as Quicksort. The Quicksort method works by picking a number from the middle of the list and then sorting the remaining numbers to the left or right of the previously picked number, as shown in Figure 20-4.

Figure 20-4:
The		Initial list	73	89	26		6		62
Quicksort
divides a			Sort by this number
larger list			6	26	89		73		62
into small
lists based				Sort by this number
on a number			6	26	62		73		89	Sorted list
chosen from
the middle												List to be sorted again
of that list.

After dividing the initial list in half, the Quicksort algorithm repetitively divides each portion of the list in half again, randomly choosing a number from each list. After the Quicksort algorithm divides a long list into a bunch of smaller ones and sorts each small list, it then combines all the small lists back into a single long list that it sorts.

The Quicksort method works as follows:

1.It picks a number from the middle of the list and uses that number to divide the long list in half. All numbers less than the randomly picked number appear to the left, and all numbers greater than the randomly picked number appear to the right.

Chapter 20: Sorting 281

2.It repeats Step 1 for each half of the list that a randomly picked number divides until it sorts all items in a bunch of smaller lists.

3.It smashes all the smaller lists back into a large list.

Because the Quicksort algorithm repeats the same steps for smaller and smaller lists, it uses a technique known as recursion. Recursion simply means that a subprogram repeatedly runs itself.

Because the Quicksort algorithm needs to use recursion, you must store the actual Quicksort algorithm in a separate subprogram. Thus the complete Quicksort program consists of a main program and a subprogram, as in the following example:

MaxSize = 5

REDIM NumArray(MaxSize)

FOR I = 1 TO MaxSize

NumArray(I) = INT(RND(1)*10) + 1

PRINT NumArray(I); “ “;

NEXT I

PRINT “(Initial array)”

CALL QSort 1, MaxSize

FOR I = 1 TO MaxSize

PRINT NumArray(I); “ “;

NEXT I

PRINT “(Sorted array)”

END

The main portion of the Quicksort program works as follows:

1.The first through seventh lines create an array of five random integers and print the array on-screen for you to see.

2.The eighth line calls the QSort subprogram by giving it the front of the list (1) and the maximum size of the list (MaxSize).

3.The ninth through twelfth lines print the final sorted array on-screen.

4.The thirteenth line tells the computer that the program is at an end.

The subprogram QSort looks as follows:

SUB QSort Start, Finish

I = Start

J = Finish

X = NumArray(INT((I+J)/2))

WHILE I <= J

WHILE NumArray(I) < X

I = I + 1

WEND

WHILE NumArray(J) > X

282 Part V: Algorithms: Telling the Computer What to Do

J = J - 1

WEND

IF I <= J THEN

A = NumArray(I)

NumArray(I) = NumArray(J)

NumArray(J) = A

I = I + 1

J = J - 1

END IF

WEND

FOR K = 1 TO Finish

PRINT NumArray(K); “ “;

NEXT K

PRINT

IF J > Start THEN CALL QSort Start, J

IF I < Finish THEN CALL QSort I, Finish

END SUB

The QSort subprogram works as follows:

1.The first line defines the name of the subprogram (QSort) and the data that it needs, which includes two integers (Start and Finish).

2.The second and third lines create two variables (I and J) that they set to the same value as the Start and Finish variables. The subprogram needs the variables I and J because their values change as the subprogram runs, but values of Start and Finish remain the same.

3.The fourth line creates the variable X that divides the size of NumArray in half and stores this value as an integer.

4.The fifth line starts a WHILE WEND loop that runs while the value of I is less than or equal to the value of J.

5.The sixth through eighth lines increase the value of I by 1 as long as the number that NumArray stores is less than the value of X.

6.The ninth through eleventh lines decrease the value of J by 1 as long as the number that NumArray stores is greater than the value of X. Here, the program is trying to determine which numbers in the list are less than or greater than the number picked in the middle of the list in the fourth line.

7.The twelfth through eighteenth lines compare the numbers in the list and move them to the left or right of the number chosen in the fourth line.

8.The nineteenth line marks the end of the WHILE WEND loop that starts in the fifth line.

9.The twentieth through twenty-third lines print the partially sorted array on-screen.

Chapter 20: Sorting 283

10.The twenty-fourth and twenty-fifth lines run the QSort subprogram over and over (recursively), each time feeding it a smaller array of numbers.

11.The twenty-sixth line marks the end of the subprogram.

A typical output for this program looks as follows:

27 62 5 79 14 (Initial array)

5 62 27 79 14

5 14 27 79 62

5 14 27 62 79

5 14 27 62 79 (Sorted array)

The first time that the program runs, the Quicksort algorithm chooses the third number (5) in the array. Then it sorts the remaining numbers depending on whether they’re less than or greater than 5. Because they’re all greater than 5, it stores them to the right of the array. Out of the four remaining numbers to the right of 5, the program picks the number 27 and sorts this smaller list, depending on whether the numbers are less than or greater than 27.

Now a third smaller list remains consisting of 79 and 62. The algorithm sorts this short list and then combines it with all the other small lists to make up the entire sorted list.

Sorting Algorithms

The insertion-sort, bubble-sort, shell-sort, and Quicksort algorithms show you the variety of methods that programs can use to sort data. Naturally, computer scientists keep inventing additional sorting algorithms with their own advantages and disadvantages, so choose your sorting algorithms carefully. Pick the right sorting algorithm, and your program can run quickly. Pick the wrong sorting algorithm, and your program may seem unbearably slow to the user.

As a general rule, insertion sort is best for small lists, bubble sort is best for lists that are already almost sorted, and Quicksort is usually fastest for everyday use. To speed up either insertion sort or bubble sort, consider combining the shell-sort algorithm with either insertion sort or bubble sort.

No matter what sorting algorithm you choose, the biggest problem is taking the time to write all the instructions to implement a particular sorting algorithm. To save you time, many programming languages include built-in sorting commands.

284 Part V: Algorithms: Telling the Computer What to Do

While built-in sorting commands may not necessarily be the fastest way to sort data, built-in sorting commands are much easier to use in comparison to writing your own sorting algorithm. In Liberty BASIC, the built-in sorting command is simply SORT, which looks like this:

SORT ArrayName, FirstArrayElement, LastArrayElement

To use the SORT command, you just have to specify the name of the array you want to sort along with the FirstArrayElement and LastArrayElement to sort. If you want to sort an entire array, the value of FirstArrayElement would be 1, and the value of LastArrayElement would be the length of the array, such as 5.

If you wanted to sort only part of an array, the value of FirstArrayElement would be any number other than 1, such as 4, and the value of

LastArrayElement would be any number greater than FirstArrayElement but less than or equal to the total length of the array.

The following example shows how to use the SORT command to sort an array that consists of five (5) elements, as shown in Figure 20-5:

MaxSize = 5

REDIM MyArray(MaxSize)

MyArray(1) = INT(RND(1) * 100) + 1

PRINT MyArray(1); SPACE$(1);

FOR I = 2 TO MaxSize

MyArray(I) = INT(RND(1) * 100) + 1

PRINT MyArray(I); SPACE$(1);

NEXT I

PRINT

SORT MyArray() 1, MaxSize

PRINT

PRINT “This is the sorted list.”

FOR I = 1 TO MaxSize

PRINT MyArray(I); SPACE$(1);

NEXT

END

If your programming language offers a built-in sorting command, use it. If it turns out to be way too slow for your particular data, take the time to write your own sorting algorithm.

Chapter 20: Sorting 285

Figure 20-5:

Liberty

BASIC’s built-in

SORT command can sort an array quickly and easily with a minimum amount of extra code.

286 Part V: Algorithms: Telling the Computer What to Do