Sleep Sort

sleepsort.c

/***************************************************************************//**

  @file         sleepsort.c

  @author       Stephen Brennan

  @date         Wednesday,  1 July 2015

  @brief        C Sleep Sort Implementation.

  This implementation of Sleep Sort is of high quality, suitable for nearly any
  production bioinformatics applications!  It requires a C99 compiler (due to
  use of VLAs), and also the outdated function "usleep()".  To compile, run:

  gcc -o sleepsort sleepsort.c -lpthread -Wall -pedantic

  Run it like this:

  ./sleepsort 3 6 4 5 1 12 8 7

  You can use as many numbers as you want.

*******************************************************************************/

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdbool.h>

/**
   @brief Arguments passed to each thread.
 */
struct sleeper_args {
  /**
     @brief The number being sorted.
   */
  unsigned int number;
  /**
     @brief Pointer to the array that results are placed in.
   */
  unsigned int *results;
  /**
     @brief Pointer to an index variable that will say where to place the
     result.
   */
  unsigned int *index;
  /**
     @brief The current thread.
   */
  pthread_t thread;
  /**
     @brief Pointer to the mutex covering results and index.
   */
  pthread_mutex_t *mutex;
};

/**
   @brief Thread to sleep and record finishing time.
   @param x Pointer to a struct sleeper_args.
   @returns NULL
 */
void *sleeper(void *x)
{
  struct sleeper_args *args = (struct sleeper_args *)x;

  // usleep is an old, deprecated function, but hey!
  usleep(args->number*1000);

  // acquire the lock, record that this thread is finished
  pthread_mutex_lock(args->mutex);
  args->results[*args->index] = args->number;
  *args->index += 1;
  pthread_mutex_unlock(args->mutex);
  return NULL;
}

/**
   @brief Run a single iteration of sleepsort.

   This helper may or may not completely sort the array.  The longer the array
   is, the more likely it is that part of the array went unsorted.  Thankfully,
   this function is like violence.  If it doesn't work the first time, the
   answer is just to use more of it.

   @param numbers Array to sort.
   @param length Length of the array.
   @returns Nothing (array is modified in place).
 */
void sleepsort_helper(unsigned int numbers[], int length)
{
  // this is a VLA -> requires C99
  struct sleeper_args threads[length];
  pthread_mutex_t mutex;
  unsigned int i;
  unsigned int index = 0;
  void *blah;
  pthread_mutex_init(&mutex, NULL);

  // Fill out the arguments and start threads.
  for (i = 0; i < length; i++) {
    threads[i].number = numbers[i];
    threads[i].results = numbers;
    threads[i].index = &index;
    threads[i].mutex = &mutex;
    pthread_create(&threads[i].thread, NULL, &sleeper, (void*)&threads[i]);
  }

  // Wait for all threads to terminate.
  for (i = 0; i < length; i++) {
    pthread_join(threads[i].thread, &blah);
  }
}

/**
   @brief Check if an array is sorted.
   @param numbers Array to check.
   @param length Length of the array.
 */
bool is_sorted(unsigned int numbers[], int length)
{
  unsigned int i;
  for (i = 0; i < length-1; i++) {
    if (numbers[i] > numbers[i+1])
      return false;
  }
  return true;
}

/**
   @brief Print an array to standard out.
   @param numbers Array to print.
   @param length Length of the array.
 */
void print(unsigned int numbers[], int length)
{
  unsigned int i;
  printf("[");
  for (i = 0; i < length; i++) {
    printf("%u, ", numbers[i]);
  }
  printf("]\n\n");
}

/**
   @brief Sort an array with sleepsort.

   This function runs the sleep sort iteration until the array is completely
   sorted.
   @param numbers Array to sort.
   @param length Length of the array.
 */
void sleepsort(unsigned int numbers[], int length)
{
  while (!is_sorted(numbers, length)) {
    sleepsort_helper(numbers, length);
    print(numbers, length);
  }
}

int main(int argc, char *argv[])
{
  int i;
  unsigned numbers[argc-1];
  for (i = 1; i < argc; i++) {
    sscanf(argv[i], "%u", &numbers[i-1]);
  }
  sleepsort(numbers, argc-1);
  return 0;
}