Anguilla Library Computer Club
Resources

Lesson on Sorting and Speed

Spreadsheet lesson #4 sorted rows of information into order by the values in one column, but we did not explore how the data was actually sorted into order. There are actually several methods (or algorithms) for sorting. One performance attribute of a sort algorithm is whether it is linear: as the number of sort items increases, does the sort time increase proportionally, or does it increase faster.

Activity: Measure Sorting Algorithms

Find the Sort Tutorial menu item and activate it. After the shareware screen, you should see a menu. If you are on a Mono screen, press C to disable color. This lesson explores three sorting algorithms -- Bubble Sort, Binary Insertion Sort, and QuickSort -- using a Graphical Sort display. The program fills the screen with random data points, then moves them as they are sorted, ending up with a straight diagonal line.

Select Bubble Sort, then Graphical Sorting. Enter 100 as the number of values to sort and plot the result on the graph below as a B at the intersection of 100 and the time in seconds. Now sort 250 items and 1000 items and plot those times. If any sort takes more than 60 seconds, press ESC to stop the sort and try again with a number of items halfway between the last test and the aborted test.

Return to the main menu and repeat these measurements for the Binary Insertion Sort (mark those results with an I) and the Recursive Quicksort (mark with a Q). Which is the Fastest? the Slowest? For each algorithm, draw a line connecting the measurement points. If the algorithm were linear, you would get a straight line. Is any of them Linear? Compare your results with other club members. Can you tell which computer is the fastest? Can you deduce the logic of any of the sort algorithms from the way Graphical Sorting forms the random dots into a straight line? Now explore the other menu options for each sort method: Program Code Sorting is fascinating.

#Items
1000 |-------------------------------------------------------------
     |
750  |-------------------------------------------------------------
     |
500  |-------------------------------------------------------------        
     |
250  |-------------------------------------------------------------
     |
100  |-------------------------------------------------------------
      0  3  6  9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 
               Number of seconds to perform the sort