#include <stdio.h>
#include <assert.h>

/* Note: the menu interface to this program is currently
   pretty disgusting -- don't confuse it with good code. */

#define ARRAY_MAX 8
typedef int array_item_type;
typedef array_item_type array_type[ARRAY_MAX];

typedef int BOOL;
#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif

void
swap(array_item_type *a, array_item_type *b)
{
  array_item_type temp;

  temp = *a;
  *a = *b;
  *b = temp;
}
void
selection_sort(array_type items,
               int low,
               int high,
               BOOL (*comparator)(array_item_type, array_item_type))
{
  int pos_to_fill;

  for (pos_to_fill = low; pos_to_fill < high; pos_to_fill++) {
    int pos_of_lowest_remaining;
    int i;

    /* find the position of the lowest remaining value. */
    pos_of_lowest_remaining = pos_to_fill;
    for (i = pos_to_fill + 1; i <= high; i++)
      if (comparator(items[i], items[pos_of_lowest_remaining]))
        pos_of_lowest_remaining = i;
    /* move the lowest remaining value to its proper place. */
    swap(&items[pos_to_fill], &items[pos_of_lowest_remaining]);
  }
}
void
merge(array_type arr,
      int low1, int high1,
      int low2, int high2,
      BOOL (*precedes)(array_item_type, array_item_type))
{
  array_type temp;
  int temp_index = low1;
  int index1 = low1;
  int index2 = low2;
  int i;

  /* Make sure that the two areas are contiguous. */
  assert(high1 + 1 == low2);
  
  /* While there are elements in both halves, copy the lowest one */
  while (index1 <= high1 && index2 <= high2) {
    if (precedes(arr[index1], arr[index2]))
      temp[temp_index++] = arr[index1++];
    else temp[temp_index++] = arr[index2++];
  }
  /* Copy all the remaining elements */
  while (index1 <= high1)
    temp[temp_index++] = arr[index1++];
  while (index2 <= high2)
    temp[temp_index++] = arr[index2++];
  /* Copy the now-sorted elements back into the original array */
  for (i = low1; i <= high2; i++)
    arr[i] = temp[i];
}

void
merge_sort(array_type arr,
           int low,
           int high,
           BOOL (*comparator)(array_item_type, array_item_type))
{
  int mid;

  if (low < high) {
    mid = (low + high) / 2;
    merge_sort(arr, low, mid, comparator);
    merge_sort(arr, mid + 1, high, comparator);
    merge(arr, low, mid, mid + 1, high, comparator);
  }
}
  /* function split places all elements that precede the median_guess
     at the left of arr, and all elements that do not precede the
     median_guess at the right of arr.  Split returns the index of the
     first element in the last half. */
int
split(array_type arr,
      int left,
      int right,
      array_item_type median_guess,
      BOOL (*precedes)(array_item_type, array_item_type))
{
  while (left < right) {
    /* Find two items that are not in the half they should be in */
    while (left < right && precedes(arr[left], median_guess))
      left++;
    while (left < right && !precedes(arr[right], median_guess))
      right--;
    /* Put these two items in their correct halves. */
    if (left < right) {
      swap(&arr[left], &arr[right]);
      left++;
      right--;
    }
  }
  /* Calculate the position of the first element of the second half and
     return it.  Either right == the desired position, or left == right
     and the value at that position belongs in the first half.  Note
     that the return value can be outside of the original range, if there
     are no numbers in that range that belong in the second half. */
  if (precedes(arr[right], median_guess))
    return(right + 1);
  else return(right);
}

void
quick_sort(array_type arr,
           int low,
           int high,
           BOOL (*precedes)(array_item_type, array_item_type))

{
  /* Make sure that there are at least two elements to sort.  If
     not, then the items between low and high are already sorted. */
  if (low < high) {
    int mid;
    array_item_type median_guess;

    /* Select arr[high] as the median_guess, and split the array into items
       that precede it and items that do not.  A better approach would be to
       select an element at random to serve as the median_guess. */
    median_guess = arr[high];
    mid = split(arr, low, high - 1, median_guess, precedes);
    swap(&arr[high], &arr[mid]);
    quick_sort(arr, low, mid - 1, precedes);
    quick_sort(arr, mid + 1, high, precedes);
  }
}
BOOL
precedes(int num1, int num2)
{
  return(num1 < num2);
}

void
show_array(array_type arr)
{
  int i;

  for (i = 0; i < ARRAY_MAX; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

void
main()
{
  int menu_choice;
  BOOL get_new_numbers;
  int i;
  array_type array;
  array_type temp_array;

  get_new_numbers = TRUE;
  do {
    if (get_new_numbers) {
      printf("Enter %d numbers to sort: ", ARRAY_MAX);
      fflush(stdout);
      for (i = 0; i < ARRAY_MAX; i++)
        scanf("%d", &array[i]);
      get_new_numbers = FALSE;
    }
    for (i = 0; i < ARRAY_MAX; i++)
      temp_array[i] = array[i];
    printf("What should I do?\n"
           "  0: quit\n"
           "  1: sort using selection sort\n"
           "  2: sort using merge sort\n"
           "  3: sort using quicksort\n"
           "  4: show the numbers to be sorted\n"
           "  5: change the numbers to be sorted\n"
           "Please enter the number of your selection: ");
    fflush(stdout);
    scanf("%d", &menu_choice);
    switch(menu_choice) {
    case 0:
      printf("Goodbye.\n");
      break;
    case 1:
      selection_sort(temp_array, 0, ARRAY_MAX - 1, precedes);
      break;
    case 2:
      merge_sort(temp_array, 0, ARRAY_MAX - 1, precedes);
      break;
    case 3:
      quick_sort(temp_array, 0, ARRAY_MAX - 1, precedes);
      break;
    case 4:
      break;
    case 5:
      get_new_numbers = TRUE;
      continue;
    default:
      printf("Nice day if it don't rain.\n");
      continue;
    }
    if (menu_choice != 0)
      show_array(temp_array);
  } while (menu_choice != 0);
}