Skip to content

Instantly share code, notes, and snippets.

@djg djg/sorting.cpp
Created May 21, 2010

Embed
What would you like to do?
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.