 |
Introduction to Sorting Laboratory |
|
Introduction to Sorting Laboratory |
In the computer science problem of sorting, the input is an array of numbers and the output must be the same numbers arranged in non-decreasing order. This is an interesting problem in computer science for two reasons. First, many applications require sorting of a large number of items (telephone books, tax records, etc.) so the efficiency of a sorting algorithm can be very important. Second, there are a number of well-studied sorting algorithms. This makes a good practice topic for the skills of analyzing and comparing algorithms. These are the skills that this lab is designed to practice.
By the end of these exercises, you should be able to:
These exercise focus on the following sorting algorithms:
Each algorithm will have three sections: an introduction which will give pseudocode and a basic explanation of the algorithm, an exploration which will use animations of the algorithm to discover its subtleties and, finally, investigations in the run-time analysis of the algorithm. Each of these areas is decribed in more detail below. You can navigate through these exercises using the colored table of buttons at the top of each page. At the top of the table is a single yellow button. Clicking that will return you to this page. Under that button, there is a row three buttons for each sorting algorithm. Those buttons correspond to the three sections: introduction, exploration, and analysis.
In order to be able to make required comparisons between the algorithms, it is recommended that you explore them in order initially, but the navigation table should allow you to get to any portion of the exercises directly.
Each algorithm's exercises will begin with an explanation of the philosophy of the algorithm and its pseudocode. The objective of this section is just to give a brief description of the algorithm; more details will be discussed in the exploration section. Some of the variables in the pseudocode may be colored differently from the rest of the code. This means that the animation will show the values of those variables in those colors (see the section on the animations below for more details).
The pseudocode will reference a function "swap(x,y)." This function swaps the elements in the x and y positions of the array being sorted. The array is always called "a" and always contains n elements.
After the brief introduction, the details of the algorithm will be explored through animations of that algorithm. These explorations will be guided experiments in which the algorithm will be run with particular input and you will look for specific behaviors. This is the section where you will truly begin to understand the subtleties of an algorithm.
The heart of these exercises is an applet which animates each of the sorting algorithms.
If you have trouble viewing all of the applet, try turning of the tool bars/status lines at the top and bottom of your browser and scrolling until the controls are at the very top of the screen.
These explorations are guided because they will tell you what parameters the applet should be given and what to look for in the animation. Each such run will be described in a table like this:
| Algorithm | Initial Data | Speed | Amount of Data |
The columns specifed the following parameters:
When you have selected the parameters for your animation, you start it by clicking the "Go" button. All parameters must be set before the animation begins; once it starts, you cannot change the values of the parameters.
The animation represents the data in the array as vertical lines. The horizontal position of a line represents its postion in the array and the height of the line is proportional to the value in that position of the array. Think of it this way: the array goes across the bottom of the screen and the height of each line represents the size of the entry in that position. This means that sorted data will cause small lines on the left and increasingly larger lines across to the right of the screen.
Most of the algorithms will show the values of various variables with smaller colored lines between the controls at the top of the screen and the vertical lines representing the data. Each algorithm's introduction page will describe the meanings of those lines and will color-code the variables in the pseudocode to match.
When the animation completes, it will display the number of swaps and the number of comparisons that were made in the text boxes at the top of the screen. The parameters can then be set for the next animation and clicking "go" will make it run again.
If you ever want to interrupt an animation (bubble sort on slow can take quite a while), just reload or refresh the page. That restarts the animation applet and will let you set the parameters.
In this section, we will explore the theoretical run-time analysis of the algorithm.
This page has been accessed times since December 8, 1998.