A few simple sorting algorithms

sort.c

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


/* ==========================================================================
 * COMPARATORS
 * ========================================================================== */

/* A comparator function pointer type that we can pass to sort functions. */
typedef int (*IntComparator)(int a, int b);

/* Function: AscendingOrder(int a, int b)
 * Usage: int *sortedArray = BubbleSort( array, len, AscendingOrder );
 * -----------------------------------------------------------------------------
 * A comparator function that causes an array's values to be sorted in ascending 
 * order. Returns a positive value if a > b, 0 if a == b, and a negative value 
 * if a < b.
 */
int AscendingOrder(int a, int b) {
  return a - b;
}

/* Function: DescendingOrder(int a, int b)
 * Usage: int *sortedArray = BubbleSort( array, len, DescendingOrder );
 * -----------------------------------------------------------------------------
 * A comparator function that causes an array's values to be sorted in 
 * descending order. Returns a negative value if a > b, 0 if a == b, and a 
 * positive value if a < b.
 */
int DescendingOrder(int a, int b) {
  return b - a;
}

/* Function: RandomOrder(int a, int b)
 * Usage: int *sortedArray = BubbleSort( array, len, RandomOrder );
 * -----------------------------------------------------------------------------
 * A comparator function that causes an array's values to be shuffled in 
 * random order.
 */
int RandomOrder(int a, int b) {
  #define MAX 4
  return (rand() % MAX) - (MAX/2);
}


/* ==========================================================================
 * HELPER FUNCTIONS
 * ========================================================================== */

/* Function: PrintArray(int *array, int len)
 * Usage: PrintArray( array, len );
 * -----------------------------------------------------------------------------
 * Prints the provided array to the console. The len parameter should equal the 
 * number of elements in the array.
 */
void PrintArray(int *array, int len) {
  for ( int i = 0; i < len; ++i ) {
    printf( "%d ", array[i] );
  }
  printf("\n");
}

/* Function: DuplicateArray( int *array, int len )
 * Usage: int *dupArray = DuplicateArray( array, len );
 * -----------------------------------------------------------------------------
 * Returns a deep copy of the provided array, where len is the number of 
 * elements in the array. The copy is allocated on the heap; it should be freed 
 * by the caller after use.
 */
int *DuplicateArray(int *array, int len) {
  int *result = malloc( len * sizeof(int) );
  memcpy( result, array, len * sizeof(int) );
  return result;
}

/* Function: SwapElements(int *a, int *b)
 * Usage: SwapElements( &array[0], &array[1] );
 * -----------------------------------------------------------------------------
 * A helper function that swaps two integers in memory.
 */
void SwapElements(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}


/* ==========================================================================
 * SORTING ALGORITHMS
 * ========================================================================== */

typedef int* (*SortFunction)(int *array, int len, IntComparator cmp);

/* Function: BubbleSort(int* array, int len, int_comparator cmp)
 * Usage: int *sortedArray = BubbleSort( array, len, AscendingOrder );
 * -----------------------------------------------------------------------------
 * A simple sorting algorithm that works by repeatedly stepping through the list 
 * to be sorted, comparing each pair of adjacent items and swapping them if they 
 * are in the wrong order.
 * 
 * --Wikipedia (http://en.wikipedia.org/wiki/Bubblesort)
 */
int *BubbleSort(int *array, int len, IntComparator cmp) {
  
  int *result = DuplicateArray( array, len );
  
  for ( int i = len - 1; i > 0; --i ) {
    for ( int j = 0; j < i; ++j ) {
      if ( cmp( result[j], result[j+1] ) > 0 ) {
        SwapElements( &result[j], &result[j+1] );
      }
    }
  }
  
  return result;
}

/* Function: SelectionSort(int* array, int len, int_comparator cmp)
 * Usage: int *sortedArray = SelectionSort( array, len, AscendingOrder );
 * -----------------------------------------------------------------------------
 * An in-place comparison sort algorithm that divides the input list into two 
 * parts: the sublist of items already sorted, which is built up from left to 
 * right at the front (left) of the list, and the sublist of items remaining to 
 * be sorted that occupy the rest of the list. Initially, the sorted sublist is 
 * empty and the unsorted sublist is the entire input list. The algorithm 
 * proceeds by finding the smallest (or largest, depending on sorting order) 
 * element in the unsorted sublist, exchanging it with the leftmost unsorted 
 * element (putting it in sorted order), and moving the sublist boundaries one 
 * element to the right.
 * 
 * --Wikipedia (http://en.wikipedia.org/wiki/Selection_sort)
 */
int *SelectionSort(int *array, int len, IntComparator cmp) {
  
  int *result = DuplicateArray( array, len );
  
  for ( int i = 0; i < len; ++i ) {
    int minIndex = i;
    
    for ( int j = i + 1; j < len; ++j ) {
      if ( cmp( result[j], result[minIndex] ) < 0 ) {
        minIndex = j;
      }
    }
    
    SwapElements( &result[i], &result[minIndex] );
  }
  
  return result;
}

/* Function: InsertionSort(int* array, int len, int_comparator cmp)
 * Usage: int *sortedArray = InsertionSort( array, len, AscendingOrder );
 * -----------------------------------------------------------------------------
 * A simple sorting algorithm that builds the final sorted array (or list) one 
 * item at a time. Insertion sort iterates, consuming one input element each 
 * repetition, and growing a sorted output list. On a repetition, insertion sort 
 * removes one element from the input data, finds the location it belongs within 
 * the sorted list, and inserts it there. It repeats until no input elements 
 * remain.
 *
 * --Wikipedia (http://en.wikipedia.org/wiki/Insertion_sort)
 */
int *InsertionSort(int *array, int len, IntComparator cmp) {
  int *result = DuplicateArray( array, len );
  
  for ( int i = 1; i < len; ++i ) {
    int valueToInsert = result[i];
    int holePos = i;
    
    while ( holePos > 0 && valueToInsert < result[holePos - 1]) {
      SwapElements( &result[holePos], &result[holePos - 1] );
      holePos -= 1;
    }
    
    result[holePos] = valueToInsert;
  }
  
  return result;
}


/* ==========================================================================
 * MAIN PROGRAM
 * ========================================================================== */

int *GetShuffledArray(int len) {
  int *array = malloc( len * sizeof(int) );
  
  for (int i = 0; i < len; ++i) {
    array[i] = i;
  }
  
  return SelectionSort( array, len, RandomOrder );
}

/* Function: DoSort(int *array, int len, char *algorithmName,
 *                  SortFunction sortFunc, IntComparator cmp)
 * Usage: DoSort( array, len, "BubbleSort", BubbleSort, AscendingOrder );
 * -----------------------------------------------------------------------------
 * A wrapper function that runs the specified sorting algorithm on the provided 
 * array, printing both the original unsorted array and the final sorted array.
 */
void DoSort(int *array, int len, char *algorithmName,
            SortFunction sortFunc, IntComparator cmp) {
  printf("\n---------------------------------------------------------------\n");
  printf("%s\n", algorithmName);
  printf("---------------------------------------------------------------\n");
  
  printf("Before: ");
  PrintArray( array, len );
  
  int *sortedArray = sortFunc( array, len, cmp );
  
  printf("After:  ");
  PrintArray( sortedArray, len );
  
  free( sortedArray );
}

int main(int argc, char *argv[]) {
  
  /* Seeds the random number generator in case the RandomOrder comparator is 
   * needed.
   */
  srand ( time( NULL ) );
  
  /* Create a shufled array of N elements. */
  int len = 30;
  int *array = GetShuffledArray( len );
  
  DoSort( array, len, "BubbleSort",     BubbleSort,    AscendingOrder );
  DoSort( array, len, "Selection Sort", SelectionSort, AscendingOrder );
  DoSort( array, len, "Insertion Sort", InsertionSort, AscendingOrder );
  
  free( array );
  
  return 0;
}