sorting.cpp

// Compile with cl /O2 sorting.cpp winmm.lib
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>

void exch(int& a, int& b)
{
    int tmp = a; a = b; b = tmp;
}

void bubble_sort(int* A, int n)
{
  bool swapped;
  do 
  { 
      swapped = false;
      for (int i = 1; i < n; ++i)
      {
          if (A[i] < A[i-1])
          {
              exch(A[i-1], A[i]);
              swapped = true;
          }
      }
  }
  while (swapped);
}

void selection_sort(int* A, int n)
{
  for (int i = 0; i < n; ++i)
  {
    int min = i;
    for (int j = i+1; j < n; ++j)
      if (A[j] < A[min])
        min = j;
    exch(A[i], A[min]);
  }
}

void insertion_sort(int* A, int n)
{
    for (int i = 1; i < n; ++i)
        for (int j = i; j > 0 && A[j] < A[j-1]; --j)
            exch(A[j-1], A[j]);
}

void quick_sort(int* A, int l, int r)
{
    if (r <= l) return;
    exch(A[l], A[l + (r-l)/2]);
    int p = l;
    for (int i = l + 1; i <= r; ++i)
        if (A[i] < A[l])
            exch(A[++p], A[i]);
    exch(A[l], A[p]);
    quick_sort(A, l, p-1);
    quick_sort(A, p+1, r);
}

void quick_sort(int* A, int n)
{
    quick_sort(A, 0, n-1);
}

void quick3_sort(int* A, int l, int r)
{
  int i = l-1, j = r, p = l-1, q = r; int v = A[r];
  if (r <= l) return;
  for (;;)
  {
    while (A[++i] < v) ;
    while (v < A[--j]) if (j == l) break;
    if (i >= j) break;
    exch(A[i], A[j]);
    if (A[i] == v) { p++; exch(A[p], A[i]); }
    if (v == A[j]) { q--; exch(A[j], A[q]); }
  }
  exch(A[i], A[r]); j = i-1; i = i+1;
  for (int k = l  ; k < p; k++, j--) exch(A[k], A[j]);
  for (int k = r-1; k > q; k--, i++) exch(A[i], A[k]);
  quick3_sort(A, l, j);
  quick3_sort(A, i, r);
}

void quick3_sort(int* A, int n)
{
  quick3_sort(A, 0, n-1);
}

bool isSorted(int* A, int n)
{
    for (int i = 1; i < n; ++i)
        if (A[i] < A[i-1])
            return false;
    return true;
}

#define N 100000
#define SEED 0xDEADBEEF

typedef void (*sorter)(int*, int);
sorter sorters[] = 
{
  bubble_sort, selection_sort, insertion_sort, quick_sort, quick3_sort
};

int main()
{
    int* A = new int[N];
  
    for (int s = 0; s < sizeof(sorters)/sizeof(sorters[0]); ++s)
    {
      srand(SEED);
      for (int n = 0; n < N; ++n)
        A[n] = rand();

      DWORD start = timeGetTime();     
      sorters[s](A, N);
      DWORD elapsed = timeGetTime() - start;
      printf("%d: elapsed = %u ms\n", s, elapsed);

      assert(isSorted(A, N));
    }

    delete [] A;

    return 0;
}