Timed trials of selection, merge and quick sort.

vaz-sorting.cpp

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;


typedef void (*sorting_fun)(int[], int);

void selectionSort(int[], int);
void mergeSort(int[], int);
void quickSort(int[], int);
void swap(int*, int*);
void printArray(int[], int);
int* generateArray(int);
int* cloneArray(int[], int);
void runTrials();
double runTrial(sorting_fun, int, int);


int main(int argc, char** argv){
  srand(time(NULL));

  int a[] = {4, 7, 3, 8, 9, 3};
  printArray(a, 6);
  mergeSort(a, 6);
  printArray(a, 6);

  //runTrials();

  return 0;
}

void runTrials(){
  sorting_fun algorithms[] = { selectionSort, mergeSort, quickSort, NULL };

  for(sorting_fun* f = algorithms; *f != NULL ; f++)
    for(int i = 0; i < 5; i++){
      int n = (int)pow(2.0, i) * 1000;
      cout << n << endl;
      cout << runTrial(*f, n, 100 - (i * 20)) << endl;
    }
}

double runTrial(sorting_fun algorithm, int n, int m){
  double totalTime = 0;
  clock_t begin, end;

  for(int i = 0; i < m; i++){
    // note: caller is responsible for this memory:
    int* data = generateArray(n);
    double thisTime = 0;

    begin = clock();

    algorithm(data, n);

    end = clock();

    thisTime = (double)(end - begin) / CLOCKS_PER_SEC;
    totalTime += thisTime;

    free(data);
  }

  return totalTime / m; // mean running time
}

void selectionSort(int A[], int n){
  int max = 0;

  if(n == 1) return;

  for(int i = 1; i < n; i++)
    if(A[i] > A[max]) max = i;

  swap(A[n-1], A[max]);
  selectionSort(A, n - 1);
}

void mergeSort(int A[], int n){
  if(n == 1){
    return;
  }else if(n == 2){
    // unnecessary?
    if(A[0] > A[1]){
      swap(A, A + 1);
    }
  }else{
    int *B = cloneArray(A, n);
    int pivot = n / 2;

    int *left  = B;
    int *right = B + pivot;

    mergeSort(left, pivot);
    mergeSort(right, n - pivot);

    // now merge
    for(int i = 0; i < n; i++)
      if(left >= B + pivot){
        A[i] = *right++;
      }else if(right >= B + n){
        A[i] = *left++;
      }else if(*left < *right){
        A[i] = *left++;
      }else{
        A[i] = *right++;
      }

    free(B);
  }
}

void quickSort(int A[], int n){
  // .... nah
}


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


/* You gotta free this!! */
int* generateArray(int n){
  int* data = (int*)malloc(sizeof(int) * n);

  for(int i = 0; i < n; i++)
    data[i] = rand();

  return data;
}

/* you gotta free this too! */
int* cloneArray(int A[], int n){
  int* B = (int*)malloc(sizeof(int) * n);
  memcpy(B, A, sizeof(int) * n);
  return B;
}

void printArray(int a[], int n){
  cout << "{ ";
  for(int i = 0; i < n-1; i++){
    cout << a[i] << ", ";
  }
  cout << a[n-1] << " }" << endl;
}