/*----------------------------------------------------------------------
  File    : hardsort.c
  Contents: generate a list of numbers
            that is hard to sort with quicksort
  Author  : Christian Borgelt
  History : 01.03.1998 file created
            04.03.1998 median of three version added
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

int main (int argc, char *argv[])
{                               /* --- main function */
  int i, k;                     /* loop variables, counters */
  int m;                        /* sort method, element index */
  int cnt;                      /* number of numbers */
  int *nums;                    /* vector of numbers */
  int t;                        /* exchange buffer */

  if (argc != 3) {              /* if wrong number of arguments given */
    printf("usage: %s m n\n", argv[0]);
    printf("generate a list of n numbers "
           "that is hard to sort with method m\n");
    printf("m = 0: quicksort with first or last element as pivot\n");
    printf("m = 1: quicksort with middle element as pivot\n");
    printf("m = 2: quicksort with median of first, middle, "
                  "and last element as pivot\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */
  m = atoi(argv[1]);            /* get the sort method identifier */
  if ((m < 0) || (m > 2)) {     /* and check it */
    printf("%s: illegal method id %d\n", argv[0], m); return -1; }
  cnt = atoi(argv[2]);          /* get the number of numbers */
  if (cnt <= 0) {               /* and check it */
    printf("%s: n must be > 0\n", argv[0]); return -1; }
  nums = (int*)malloc(cnt *sizeof(int));
  if (!nums) { printf("%s: not enough memory\n", argv[0]); return -1; }
  for (i = 0; i < cnt; i++)     /* allocate and initialize */
    nums[i] = i;                /* the number vector */
  if (m == 1) {                 /* if middle element as pivot */
    for (k = 1, i = cnt -1; --i >= 0; ) {    /* work backwards */
      m = i +(++k >> 1);        /* get index of middle element */
      t = nums[m]; nums[m] = nums[i]; nums[i] = t;
    } }                         /* exchange first and middle element */
  else if (m == 2) {            /* if median of three as pivot */
    for (k = cnt & 1, i = cnt -k; (i -= 2) >= 0; ) {
      m = i +((k += 2) >> 1);   /* get index of middle element */
      t = nums[m]; nums[m] = nums[i+1]; nums[i+1] = t;
    }                           /* exchange second and */
  }                             /* middle element */
  for (i = 0; i < cnt; i++)     /* traverse the number vector */
    printf("%d\n", nums[i]);    /* and print all numbers */
  return 0;                     /* return 'ok' */
}  /* main() */