Simple Sort

Of course, we all know that the Simple Card Sort algorithm is not very useful to a computer. However, we can use the same idea as in our Simple Card Sort to write a Simple Sort that can be used by a computer. Let's see what this algorithm looks like and how it can be used to sort numbers in a computer.

Simple Sort Algorithm

1. 1. Get a list of unsorted numbers
2. 2. Repeat steps 3 through 6 until the unsorted list is empty
3. 3.    Compare the unsorted numbers
4. 4.    Select the smallest unsorted number
5. 5.    Move this number to the sorted list
6. 6.    Store a maximum value in the place of the smallest number
7. 7. Stop

Notice that most of the steps in our new algorithm are the same as the steps in the Simple Card Sort. The exception is step 6. We need this extra step because we are no longer moving cards from hand to hand but copying numbers in computer memory. For our algorithm to work, we must replace our original number with a special marker so it will not be considered again. The steps below illustrate how the Simple Sort algorithm works on a computer.

1.First, we give the computer a list of unsorted numbers. These numbers are stored in a group of contiguous memory cells called an array. Each memory cell of the array holds a single number.

2.As the computer sorts these numbers, it will repeatedly compare them to find the smallest number. This is similar to the comparisons we made when sorting our hand of cards. Each time we compared two cards and kept the smaller of the two. Then we compared this card to the remaining cards until we found a smaller one or checked all the cards. The computer uses the same process only with numbers rather than cards.

Once the smallest number is found, the computer will copy this number to a new array of memory cells and replace the old number with a special number called MAX. MAX is the largest number a single memory cell can hold. None of the remaining numbers can be larger than MAX, so this number is a good choice for marking memory cells that have already been sorted.

3. Next, the computer begins searching for the smallest number in the unsorted list. Although it is easy for us to scan the numbers and select the 2 as smallest, the computer must compare all the memory cells in the unsorted array to be certain which number is smallest. This means the computer must perform six comparisons: (7 < 8), (7 > 5), (5 > 2), (2 < 4), (2 < 6), and finally (2 < 3). Once the comparisons are done, the computer copies 2 to the sorted array and replaces the original 2 with MAX.

4. Now the computer begins searching for the smallest number again. Six more comparisons are required to determine that 3 is smallest: (7 < 8), (7 > 5), (5 < MAX), (5 > 4), (4 < 6), and finally (4 > 3). Now we can see the importance of replacing 2 with MAX in our previous step. If we had not made this change, then 2 would have been selected as the smallest number again. After copying 3 to the sorted array, the computer also replaces the original with MAX.

5. With six more comparisons, the computer selects 4 as the smallest number, copies it to the sorted array, and replaces the original with MAX.

6. The numbers 5, 6, 7, and 8 are also selected in turn by six comparisons, a copy, and a replacement of the original. Once all the memory cells in the unsorted array have been considered, the sorted array contains our original numbers in sorted order.