ex18.c

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

void die(const char *message)
{
  if(errno) {
    perror(message);
  } else {
    printf("ERROR: %s\n", message);
  }

  exit(1);
}

typedef int(*compare_cb)(int a, int b);
typedef int *(*sort_func)(int *numbers, int count, compare_cb cmp);

int *quick_sort(int *numbers, int count, compare_cb cmp)
{
  if(count <= 1)
    return numbers;

  int start = 0;
  int end = count;
  int pivot = numbers[0];
  int temp = 0;

  for(;;) {
    while(cmp(numbers[++start], pivot) < 0 && start < count) { }
    while(cmp(numbers[--end], pivot) > 0) { }

    if(start >= end) {
      break;
    }

    temp = numbers[start];
    numbers[start] = numbers[end];
    numbers[end] = temp;
  }
  temp = numbers[start -1];
  numbers[start - 1] = numbers[0];
  numbers[0] = temp;
  quick_sort(numbers, start - 1, cmp);
  quick_sort(numbers+start, count - start, cmp);
  return numbers;
}

int *bubble_sort(int *numbers, int count, compare_cb cmp)
{
  int temp = 0;
  int i = 0;
  int j = 0;
  int *target = calloc(count, sizeof(int));

  if(!target) die("Memory error.");

  memcpy(target, numbers, count * sizeof(int));

  for(i = 0; i < count; i++) {
    for(j = 0; j < count - 1; j++) {
      if(cmp(target[j], target[j+1]) > 0) {
        temp = target[j+1];
        target[j+1] = target[j];
        target[j] = temp;
      }
    }
  }
  return target;
}

int sorted_order(int a, int b)
{
  return a - b;
}

int reverse_order(int a, int b)
{
  return b - a;
}

int strange_order(int a, int b)
{
  if(a == 0 || b == 0) {
    return 0;
  } else {
    return a % b;
  }
}

void test_sorting(int *numbers, int count, sort_func sort, compare_cb cmp)
{
  int i = 0;
  int *sorted = sort(numbers, count, cmp);

  for(i = 0; i < count; i++) {
    printf("%d ", sorted[i]);
  }
  printf("\n");
}

int main(int argc, char *argv[])
{
  if(argc < 2) die("USAGE: ex18 4 3 1 5 6");

  int count = argc - 1;
  int i = 0;
  char **inputs = argv + 1;

  int *numbers = calloc(count, sizeof(int));
  if(!numbers) die("Memory error.");

  for(i = 0; i < count; i++) {
    numbers[i] = atoi(inputs[i]);
  }

  test_sorting(numbers, count, quick_sort, sorted_order);
  test_sorting(numbers, count, quick_sort, reverse_order);
  test_sorting(numbers, count, quick_sort, strange_order);

  free(numbers);

  return 0;
}