# CSCD-2552015-02-12

## Sorting Arrays (Ch. 23)

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]
}
}```

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()```

Drill program with random contents:
drillInsSort.txt   drillInsSort.c   drillInsSort.exe