Quicksort and variations

// Demosntration of a few sorting algorithms
// by Nicolau Werneck<nwerneck@gmail.com>, Sept. 2012

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/times.h>

void print_array(unsigned int* arr, unsigned int size) {
  unsigned int k;
  for (k=0; k<size; k++) {
    printf("%05u %16u\n", k, arr[k]);
  }
}

void fill_array(unsigned int* arr, unsigned int size, unsigned int bits) {
  unsigned int k;
  for(k = 0; k < size; k++)
    arr[k] = rand() % (1<<(bits)) ;
}

unsigned int* insertion_sort(unsigned int* arr, unsigned int size) {
  if (size <= 1)
    return;

  unsigned int p, q;
  unsigned int tmp;

  for(p=1; p<size; p++) {
    if (arr[p-1] <= arr[p])
      continue;
    for(q=p; (q > 0) && !(arr[q-1] <= arr[q]); q--) {
      tmp = arr[q];
      arr[q] = arr[q-1];
      arr[q-1] = tmp;
    }
  }
}

unsigned int* mixsort(unsigned int* arr, unsigned int size, unsigned int pivot) {

  // If the list size is small, just run insertion sort and get done with it.
  if (size <= 8){
    return insertion_sort(arr, size);
  }

  // Just for safety really.
  if (pivot == 0){
    return;
  }

  unsigned int k; // Loop variable
  unsigned int tmp; // Temp variable to switch values

  // This variable points to the first item that is larger or equal
  // than the pivot.
  unsigned int sep;

  // Look for the first item that is larger or equal than the pivot.
  for (k = 0; k < size && !(arr[k] & pivot); k++);
  sep = k;

  // Now iterate through the remaining list items, and move the
  // smaller ones to the first half of the list.
  for (; k < size; k++) {
    // If the current item is smaller than the pivot,
    if (!(arr[k] & pivot)) {
      // switch the current small value with head of second half
      tmp = arr[sep];
      arr[sep] = arr[k];
      arr[k] = tmp;
      // and increment head of the second half.
      sep++;
    }
  }

  // Make the recursive calls for the two sublists, and the next less
  // significant bit.
  mixsort(arr, sep, pivot >> 1);
  mixsort(arr+sep, size-sep, pivot >> 1);
}

unsigned int* mixquicksort(unsigned int* arr, unsigned int size) {

  // If the list size is small, just run insertion sort and get done with it.
  if (size <= 8){
    return insertion_sort(arr, size);
  }

  unsigned int k; // Loop variable
  unsigned int tmp; // Temp variable to switch values

  // Select item to be the pivot using the median from 3 values.
  unsigned int piv = 0;

  if (arr[0] < arr[size/2] && arr[size/2] < arr[size-1] || \
      arr[size-1] < arr[size/2] && arr[size/2] < arr[0]) {
  }
  else if (arr[size/2] < arr[size-1] && arr[size-1] < arr[0] || \
       arr[0] < arr[size-1] && arr[size-1] < arr[size/2]) {
  }
  else {
    piv = 0;
  }
  unsigned int pivot = arr[piv];

  // This variable points to the first item that is larger or equal
  // than the pivot.
  unsigned int sep;

  // Switch pivot with last list item.
  tmp = arr[size-1];
  arr[size-1] = arr[piv];
  arr[piv] = tmp;

  // Look for the first item that is larger or equal than the pivot.
  for (k = 0; (k < size) && (arr[k] < pivot); k++);
  sep = k;

  // Now iterate through the remaining list items, and move the
  // smaller ones to the first half of the list.
  for (; k < size; k++) {
    // If the current item is smaller than the pivot,
    if (arr[k] < pivot) {
      // switch the current small value with head of second half
      tmp = arr[sep];
      arr[sep] = arr[k];
      arr[k] = tmp;
      // and increment head of the second half.
      sep++;
    }
  }

  // Switch last item (pivot) with first.
  tmp = arr[size-1];
  arr[size-1] = arr[sep];
  arr[sep] = tmp;

  // Make the recursive calls for the two sublists, and the next less
  // significant bit.
  mixquicksort(arr, sep);
  mixquicksort(arr+sep+1, size-sep-1);
}



unsigned int* radixsort(unsigned int* arr, unsigned int size, unsigned int pivot) {

  // Return if there are no more bits to test or if the list is empty.
  if (pivot == 0 || size <= 1){
    return;
  }

  unsigned int k; // Loop variable
  unsigned int tmp; // Temp variable to switch values

  // This variable points to the first item that is larger or equal
  // than the pivot.
  unsigned int sep;

  // Look for the first item that is larger or equal than the pivot.
  for (k = 0; k < size && !(arr[k] & pivot); k++);
  sep = k;

  // Now iterate through the remaining list items, and move the
  // smaller ones to the first half of the list.
  for (; k < size; k++) {
    // If the current item is smaller than the pivot,
    if (!(arr[k] & pivot)) {
      // switch the current small value with head of second half
      tmp = arr[sep];
      arr[sep] = arr[k];
      arr[k] = tmp;
      // and increment head of the second half.
      sep++;
    }
  }

  // Make the recursive calls for the two sublists, and the next less
  // significant bit.
  radixsort(arr, sep, pivot >> 1);
  radixsort(arr+sep, size-sep, pivot >> 1);
}

unsigned int* quicksort(unsigned int* arr, unsigned int size) {

  // Return if there are no more bits to test or if the list is empty.
  if (size <= 1){
    return;
  }

  unsigned int k; // Loop variable
  unsigned int tmp; // Temp variable to switch values

  // Select item to be the pivot using the median from 3 values.
  unsigned int piv = 0;

  if (arr[0] < arr[size/2] && arr[size/2] < arr[size-1] || \
      arr[size-1] < arr[size/2] && arr[size/2] < arr[0]) {
  }
  else if (arr[size/2] < arr[size-1] && arr[size-1] < arr[0] || \
       arr[0] < arr[size-1] && arr[size-1] < arr[size/2]) {
  }
  else {
    piv = 0;
  }
  unsigned int pivot = arr[piv];

  // This variable points to the first item that is larger or equal
  // than the pivot.
  unsigned int sep;

  // Switch pivot with last list item.
  tmp = arr[size-1];
  arr[size-1] = arr[piv];
  arr[piv] = tmp;

  // Look for the first item that is larger or equal than the pivot.
  for (k = 0; (k < size) && (arr[k] < pivot); k++);
  sep = k;

  // Now iterate through the remaining list items, and move the
  // smaller ones to the first half of the list.
  for (; k < size; k++) {
    // If the current item is smaller than the pivot,
    if (arr[k] < pivot) {
      // switch the current small value with head of second half
      tmp = arr[sep];
      arr[sep] = arr[k];
      arr[k] = tmp;
      // and increment head of the second half.
      sep++;
    }
  }

  // Switch last item (pivot) with first.
  tmp = arr[size-1];
  arr[size-1] = arr[sep];
  arr[sep] = tmp;

  // Make the recursive calls for the two sublists, and the next less
  // significant bit.
  quicksort(arr, sep);
  quicksort(arr+sep+1, size-sep-1);
}

int main(int argc, char* argv[]) {

  // Return if there is no argument.
  if (argc < 5) {
    return 1;
  }

  // Select algorithm to use.
  char func = argv[1][0];

  // Read word size from input argument.
  int bits = atoi(argv[2]);

  // Read array size from input argument.
  int size = atoi(argv[3]);

  // Read number of iterations from input argument.
  int iters = atoi(argv[4]);

  // Return if conversion of arguments was not successful.
  if (size == 0 || bits == 0 || bits > 31) {
    return 1;
  }

  // Allocate memory for the array to be sorted
  unsigned int* arr = (unsigned int*) malloc(sizeof(int)*size);

  // Initialize random generator from current time.
  srand ( time(NULL) );

  //////////////////////////////////////////////////////////////////////////
  // Where the real action begins.
  //

  // Stuff to measure time.
  struct tms tta;
  struct tms ttb;
  times(&tta);


  // If iters = 0 just run once and print stuff.
  if (iters == 0) {

    // Initialize array.
    fill_array(arr, size, bits);
    print_array(arr, size);

    // Make the initial call to the sort procedure.
    if (func=='q') {
      quicksort(arr, size);
    } else if (func=='r') {
      radixsort(arr, size,  1 << (bits-1));
    } else if (func=='i') {
      insertion_sort(arr, size);
    } else if (func=='m') {
      mixsort(arr, size,  1 << (bits-1));
    } else if (func=='n') {
      mixquicksort(arr, size);
    }

    printf("\nSorting...\n\n");

    print_array(arr, size);

    return 0;
  }


  // Re-fill array and run quicksort for the specified number of iterations.
  int k;
  for(k=0;k<iters;k++) {
    // Initialize array.
    fill_array(arr, size, bits);

    // Make the initial call to the sort procedure.
    if (func=='q') {
      quicksort(arr, size);
    } else if (func=='r') {
      radixsort(arr, size,  1 << (bits-1));
    } else if (func=='i') {
      insertion_sort(arr, size);
    } else if (func=='m') {
      mixsort(arr, size,  1 << (bits-1));
    } else if (func=='n') {
      mixquicksort(arr, size);
    } else if (func=='0') {
      continue;
    }
  }

  times(&ttb);
  printf("%d %e\n", size, \
     ((double) (ttb.tms_utime - tta.tms_utime)*.01/iters ));

  return 0;
}