| Please send all questions & assignments to: |  |
|
| dsolarek@eng.utoledo.edu | ||
Implementation in BASIC
Sorting an Array
One of the simplest sorting techniques found in programming is the bubble sort algorithm. This sorting technique makes many passes over the list of elements to be sorted (sets of numbers or character strings), partially sorting them with each pass. Smaller elements move up one position during each pass, bigger elements may be pushed down multiple positions during each pass. Eventually, the numbers all bubble into their correct positions. The bubble sort uses a simple comparison to determine when to swap two numbers in the array. Let us see how this works. Suppose we have the following four-element array to begin with:
7 5 1 3First, the 7 and 5 are compared. Since the 7 is larger than 5, both numbers are swapped within the array (moving the 5 to the first position and the 7 to the second), that is:
5 7 1 3Next the 7 and 1 are compared and swapped. Now we have
5 1 7 3Finally, the 7 and the 3 are compared and swapped, resulting in
5 1 3 7This completes the first pass through the list of numbers. Notice that the largest number, 7, has been pushed "down" into its correct position. The other numbers in the array have moved but are not yet in their proper places, which is why multiple passes are needed.
At the end of the second complete pass, the array looks like this:
1 3 5 7Every number is now in its correct position! The array has been sorted into ascending order. Some arrays will require additional passes to get all of the numbers sorted, so, in general, the bubble sort makes N-1 passes over a set of N numbers. This means that ten input nubmers will require nine passes to guarantee that they are completely sorted. The BASIC program shown below implements a bubble sort for an array of ten numbers.
10 REM Sorting an array 20 FOR K = 1 TO 10 30 READ N(K) 40 NEXT K 50 FOR K = 1 TO 9 60 FOR J = 1 TO 10-K 70 IF N(J) > N(J + 1) THEN GOSUB 200 80 NEXT J 90 NEXT K 100 PRINT "The sorted array is:" 110 FOR K = 1 TO 10 120 PRINT N(K); 130 NEXT K 140 END 150 REM 200 TEMP = N(J) 210 N(J) = N(J + 1) 220 N(J + 1) = TEMP 230 RETURN 250 REM 300 DATA 10, 4, 25, 16, 30, 5, 20, 12, 0, 27Nested FOR loops are used to perform the required number of passes over the array. The IF-THEN statement uses a subroutine to swap two elements of the array (elements N(K) and N(K + 1)) whenever the conditional test is true. An execution of the above program yields the following results:
The sorted array is:
0 4 5 10 12 16 20 25 27 30The bubble sort algorithm is not very efficient for a large numbers of elements. However, it is the simplest of sorting algorithms and does illustrate the general approach to sorting.
