The sorting algorithms you will learn in the next few lessons share two basic operations in common. These operations are the comparison operation and the swap operation. We will look at each one in more detail before we examine our sorting algorithms.
The Comparison Operation
The comparison operation is simply a way of determining which item in a list should come first. If we are sorting a list of numbers from smallest to largest, the comparison operation tells us to place the number with the least value first. If we are sorting a list of letters alphabetically, the comparison operation tells us to place 'a' before 'b', 'b' before 'c', and so on. We will see that a sorting algorithm must usually perform many comparisons in order to correctly sort a list.
The Swap Operation
The swap operation is one way we move items as we are sorting. By swapping small items with large ones, we can place all the items in the correct order. When we use computers for sorting, the swap operation can be a little tricky because of the way computers copy data from one memory location to another. Using the animation below, see if you can correctly determine the algorithm for the swap operation.
Let's take one more look at the swap algorithm we wrote:
- Copy the contents of cell A to temp.
- Copy the contents of cell B to cell A.
- Copy the contents of temp to cell B.
Notice that this operation requires three copies. It is important to remember that the swap operation is really a combination of copy operations. In our next lesson, we will learn a sorting algorithm called the Simple Sort that uses just the copy operation rather than the swap operation.