/* Program  Description
** -------  ---------------------------------------------------------
** sort.c   This small C program demonstrates an optimized shell sort
**          that compiles under all standard C compilers.
**
**          Function call:  shellsort(words, 200, 0);   
**
**          Parameter 1:  Pointers to pointers to char:  start of strings
**                        (could be rewritten as char *words[])
**          Parameter 2:  Number of items to sort 
**          Parameter 3:  Direction (0 ascending, 1 descending)
**
**          In the function call above, we are effectively 
**          sorting 200 words alphabetically (in ascending order.)
**
**          This small program was brought to you by
**          Scott Wenger, Box 802, Stevens Point, WI 54481, USA
**          panther@wctc.net
**          http://www.private-files.com/sware.html
**        
**          Note:  You may want to add an index into the 
**          data to be sorted for certain applications.
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


// function prototype
void shellsort(register char **v, int n, int direction);

//  Optimized shell sort for strings (parameters described below):
//  v is pointer to pointer to char:  strings to be sorted
//  (could also be written "char *v[]" for array of pointers to char)
//  n is number of elements to be sorted 
//  direction is 0 for ascending sort or 1 for reverse order sort 

void shellsort(register char **v, int n, int direction)
{
  register int gap, i, j;
  char *temp;
  
  gap = 1;
  do (gap = 3 * gap + 1); while (gap <= n);
  for (gap /= 3; gap > 0; gap /= 3)
    for (i = gap; i < n; i++) {
      temp = *(v + i);

      if (direction == 0) {   // ascending order sort 
        for (j = i - gap; (j >= 0) && (strcmp( *(v + j) , temp) > 0); j -= gap) {
          *(v + j + gap) = *(v + j);
        }          
      }

      if (direction == 1) {  // descending order sort 
        for (j = i - gap; (j >= 0) && (strcmp( *(v + j), temp) < 0); j -= gap) {
          *(v + j + gap) = *(v + j);
        }          
      }
      *(v + j + gap) = temp;
  }                 
}

/*---------------------------------------------------------------*/

//  now, to see the optimized shell sort in action...

main()
{
  // In your program, you can dynamically create and maintain an
  // array of pointers to char (pointers to start of strings) and
  // perhaps place the strings themselves in memory. 
  
  // Since this program shows an optimized shell sort, let's just
  // initialize an array of pointers to char (start of strings)
  // to show the sort in action.

  int i;
  static char *words[] = {"Gates, Bill", "Nash, Mike", "Allen, Paul G.",
                          "Ballmer, Steve", "Herbold, Bob", 
                          "Boren, Caroline", "Maritz, Paul", 
                          "Lacombe, Michel"};    

  for (i = 0; i < 80; i++) printf("\n");  // primitive clear screen
    
  printf("\nDemonstration of Optimized Shell Sort\n\n");   
  printf("\nThe unsorted list:\n------------------"); 
  for (i = 0; i < 8; i++)  printf("\n%s", words[i]);  // show unsorted list      
  printf("\n\n");        
  
  shellsort(words, 8, 0);    //  call the sort function

  printf("\nThe sorted list:\n----------------"); 
  for (i = 0; i < 8; i++)  printf("\n%s", words[i]);  // show sorted list 
  printf("\n");
  fflush(stdout);             
  exit(0);
}


/*------------------------------END------------------------------------*/