sorts.c

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

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

  exit(1);
}

void swap(int *a, int *b)
{
  int temp = *a;
  *a  = *b;
  *b = temp;
}

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

int *bubble_sort(int *numbers, int count, compare_cb cmp)
{
  int *target = malloc(count * sizeof(int));

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

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

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

  return target;
}

int partition(int target[], int low, int high)
{
  int i;
  int p_index;
  int firsthigh;
  int cur;
  int below_p;

  p_index = high;
  int p_value = target[p_index];
  firsthigh = low;
  for (i = low; i < high; i++) {
    cur = target[i];
    below_p = cur < p_value;
    if (below_p) {
      swap(&target[i], &target[firsthigh]);
      firsthigh ++;
    }
  }
  swap(&target[p_index], &target[firsthigh]);

  return(firsthigh);
}

void quicksort(int *target, int low, int high)
{
  int partition_index;

  // Base case
  int inbounds = (high - low) > 0;

  if (inbounds) {
    partition_index = partition(target, low, high);
    quicksort(target, low, partition_index-1);
    quicksort(target, partition_index+1, high);
  }
}

int *do_quick_sort(int *numbers, int count, compare_cb cmp)
{
  int *target = malloc(count * sizeof(int));

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

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

  quicksort(target, 0, count-1);

  return target;
}

int sorted_order(int a, int b)
{
  int a_larger = (a > b); // 1 or 0
  int b_larger = (a < b); //1 or 0
  return a_larger - b_larger; // 1-0, 0-1, 0
}

int reverse_sorted(int a, int b)
{
  int a_larger = (a > b); // 1 or 0
  int b_larger = (a < b); //1 or 0

  // 0-1, 1-0, 0 (but the reverse of above for a given test
  return b_larger - a_larger ;
}

int strang_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);

  if (!sorted)
    die("Failed to sort as requested");

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

  free(sorted);
}

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

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

   int *numbers = malloc(count * sizeof(int));
   if (!numbers) die("Memory error");

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

   printf("BubbleSort:\n");
   test_sorting(numbers, count, bubble_sort, sorted_order);
   test_sorting(numbers, count, bubble_sort, reverse_sorted);
   test_sorting(numbers, count, bubble_sort, strang_order);

   printf("Quicksort\n");
   test_sorting(numbers, count, do_quick_sort, sorted_order);
   test_sorting(numbers, count, do_quick_sort, reverse_sorted);
   test_sorting(numbers, count, do_quick_sort, strang_order);

   free(numbers);

   return 0;
 }