CSCD-255
2015-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:

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

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