/* ++[ Machine Problem #3 ]++++++++++++++++++++++++++++++++++++++
   +                                                            +
   + Zaczek, Mariusz                                            +
   + CS 223 - Monday 11:00am - 1:00 pm                          +
   + 3/7/98                                                     +
   +                                                            +
   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

/* Include declarations */
#include <iostream.h>
#include <string.h>
#include <ctype.h>
#include "sarr.h"

/* Declare helper function - partition */
int partition(char *A[], int fst, int lst, int method);

/* ++[  A  ]+++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                                                            +
   + Function - sort						+
   +								+
   + This function receives the array to be sorted, the first   +
   + and last positions of the array, as well a 'method' number +
   + corresponding to the type of sorting to be performed:      +
   +    ( 2 ) Sort in ASCENDING order				+
   +    ( 3 ) Sort in DESCENDING order				+
   +                                                            +
   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

void sort(char *A[], int first, int last, int method)
{
  int split;
  
    /* If first position is less than the last then perform sort. */
    if (first < last)
    {
      /* Define split position by calling partition function */
      split = partition(A, first, last, method);
    
      /* Sort the two parititions of the array defined by 'split' */
      sort(A, first, split, method);
      sort(A, split+1, last, method);
    }
return;
}

/* ++[  B  ]+++++++++++++++++++++++++++++++++++++++++++++++++++++   
   +                                                            +
   + Function - partition                                       +
   +                                                            +
   + - Helper function which returns position of partition of   +
   +   the array. Also if performs element swapping based on    +
   +   how the elements of the array are to be ordered.		+
   +								+
   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ */

int partition(char *A[], int fst, int lst, int method)
{
  /* Intialize variables */
  char pivot[200], temp[200];
  strcpy(pivot,*(A+fst));
  int i = fst - 1;
  int j = lst + 1;

  while (1)
  {
    /* Compare elements of array based on method of sorting selected */
    if (method == 3)
    {
    do { j--; } while (strcmp(*(A+j), pivot) < 0);
    do { i++; } while (strcmp(*(A+i), pivot) > 0);
    }
    else if (method == 2)
    {
    do { j--; } while (strcmp(*(A+j), pivot) > 0);
    do { i++; } while (strcmp(*(A+i), pivot) < 0);
    }
    /* Perform swap of elements if i < j */
    if (i < j)
    {
       strcpy(temp,*(A+i));
       strcpy(*(A+i),*(A+j));   
       strcpy(*(A+j),temp);
    }
    else
      return j;    
  }
return -1;
}

