2015-02-12

Our authors use about the worst possible sorting algorithm, one in which it
is complicated, it is not clear that it will work, and it still takes more time
than other simpler algorithms. We will* ignore *it.

Instead there is an algorithm that we can model on the way five-card draw poker players put their cards into order:

- Pick up the five-card hand in your left hand (if you are right handed) and fan it out.
- As long as there are any cards in your left hand
- Find the largest card in your left hand.
- Move it to the far left of the cards in your right hand

- Your right hand now has the cards in ascending order from left to right.

Left Hand

Right Hand

9, 5, K, 7, 3 9, 5, 3, 7 K 7, 5, 3 9, K 3, 5 7, 9, K 3 5, 7, 9, K 3, 5, 7, 9, K

Notice that the last card simply moves across — all by itself, it is necessarily the largest card in the left hand.

This is called "selection sort", based on successively selecting elements in an array and putting them into place.

View the array as having an unsorted front and a sorted back. Initially it is all unsorted. Find the largest entry in the front and then swap it with the last entry in the presently unsorted segment. That entry is now in place, so the sorted back has grown by one and the unsorted front has shrunk by one. Go until only one entry is left at the front — this is necessarily in proper position.

This allows us to re-use code: we already have a function to return the index
of the largest array entry between x[0] and x[num-1]. So use that to find the
largest entry. The function expects subscripts to run from zero up to some
limit, which is why we treat the front as unsorted and the back as sorted.
Some people like to run the algorithm by find the* smallest *entry
in the range and then move that to the top. Unfortunately we do not have a
function to find something starting from anywhere but index 0.

void selSort(int x[], int n) // Selection Sort { int lim; // End of unsorted segment // When lim hits 1 we're done. for (lim = n; lim > 1 ; ) // Decremented in the loop { int hold; // For the swap int big, // Index of largest ck; // Cell being checked big = maxIdx(x, lim); // Decrement of loop variable lim--; // subscript of last cell // Swap logic hold = x[lim]; x[lim] = x[big]; x[big] = hold; // After this, ignore x[lim] } }

demoSelSort.txt demoSelSort.c demoSelSort.exe

Drill programs: Display the state of the array at the beginning of each
pass through the `for` loop and at the end.

Fixed contents:
drillSelSort.txt drillSelSort.c
drillSelSort.exe

Random contents: drillSelSort2.txt drillSelSort2.c
drillSelSort2.exe

**Enrichment Material: A Faster Sort**

There is another algorithm that we can model on the way bridge players put their cards into order, since fanning 13 cards is unwieldy

- All the cards are face down on the table
- As long as there are any cards on the table
- Pick up one card.
- Put it into its proper place among the cards in your hand

- Your hand now has the cards in the order you prefer

Hand so far

Cards on table

9, 5, K, 7, 3 9 5, K, 7, 3 5, 9 K, 7, 3 5, 9, K 7, 3 5, 7, 9, K 3 3, 5, 7, 9, K

This is called "insertion sort" since it is based on inserting cells into their proper positions as the algorithm progresses. Here the left side is the sorted side and the right side contains the cells to be positioned. Initially there is one cell on the left — an array with one element is necessarily sorted. Then successively, from left to right, the program find the proper position for the first cell on the right, moving cells out of the way until the proper location is found. If the array is already in order, nothing needs to be moved and this proceeds rapidly.

/* * Insertion sort algorithm */ void insSort ( int x[], int n ) { int lim, // start of unsorted region hole; // insertion point in sorted region for ( lim = 1 ; lim < n ; lim++ ) { int save = x[lim]; // The value being positioned for ( hole = lim ; // Not at top AND the save value belongs before next hole > 0 && save < x[hole-1 ; hole-- ) { x[hole] = x[hole-1]; } x[hole] = save; // Plug the hole } // end for (lim... } // end insSort()

demoInsSort.txt demoInsSort.c demoInsSort.exe

Drill program with random contents:

drillInsSort.txt drillInsSort.c
drillInsSort.exe