Several Sorting Algorithms
Computer applications frequently are presented with a disorganized
list of things, which must be given some order. Once ordered, this
list can often be processed faster. A simple example is the creation
of an index in a book: on certain pages, the user inserts a mark and
a key word, and the word-processor must sort all the key words
alphabetically.
The way that sorting algorithms work can best be understood if we
simplify the task, and reduce it to the problem of sorting numbers.
Here are several sorting algorithms. Each one starts with an array
of numbers, and sorts them in increasing order.
A note on the way the numbers are visualized: The arrays of numbers can
be pictured in three ways:
- Sticks: as a bar graph, where each bar represents a number.
The height of the bar gives the number's value, and
the left-right location of a bar represents the number's
location in the array.
- Dots: each number is represented by a dot. The dot's
x coordinate represents the number's position in the array,
while its y coordinate gives the number's value.
This is similar to sticks, except each bar is replaces
by a dot at the top of the bar. It is most useful for picturing
large arrays.
- Line stack: here, the array is visualized as a pile of
horizontal sticks, each one representing a number. When sorted,
the sticks decrease in size from bottom to top.
Alejo Hausner, CS Department, Princeton University
Last modified: Tue Jul 23 14:19:22 1996