My implementations of some sorting algorithms. You can use them in your code or for educational purposes. The code is mostly uncommented except for the radix sort, so I guess it could be a bit tricky to understand the workings; the variables themselves are descriptive of what they are used for, though.
// ==================================================================//
//
// Sorting algorithms:
// O(n2) Bubble, Selection, Insertion
// O(nlogn) Quick, Merge (both iterative & recursive), Heap
//
// Radix Sort (LSD)
// http://en.wikipedia.org/wiki/Radix_sort#Efficiency
//
// Author: 0poitr @ evilzone.org, 2014
// Permission for use and modification of the code.
//
// For knowledge and some interestng discussion on the algorithms,
// you can consider their wikipedia pages and references.
//
// ==================================================================//
#include <iostream>
#define ULONG unsigned long
#define MIN(a, b) (a) < (b) ? (a) : (b)
#define mergeSortRecursive(x, y, len) mergeSortRecursive_(x, y, len-1);
using namespace std;
// prototype declarations
template <class T> void selectSort(T *a, int size);
template <class T> void bubbleSort(T *a, int size);
template <class T> void insSort(T *a, int size);
template <class T> int partition(T *a, int lb, int ub);
template <class T> void quickSort(T *a, int size);
template <class T> void quickSortRecursive(T *a, int lb, int ub);
template <class T> void reHeap(T *a, int start, int end);
template <class T> void heapSort(T *a, int size);
template <class T> void mergeParts(T *a, int lb, int mid, int ub);
template <class T> void mergeSort(T *a, int size);
template <class T> void mergeSortRecursive_(T *a, int lb, int ub);
template <class T> void display(T *a, int size);
template <class T> void radixSort(T *a, int size);
template <class T> void reNew(T **ptr, int *size);
template <class T> void push(T *a, T data);
template <class T> int pop(T *a);
int stackEmpty();
template <class T> void swap(T *a, int h, int l);
void freeMem(int **b);
// =====================
// auxiliary functions
int stack_top=0;
template <class T> void push(T *a, T data)
{
a[stack_top++] = data;
}
template <class T> int pop(T *a)
{
return a[--stack_top];
}
int stackEmpty()
{
if (!stack_top) return 1;
return 0;
}
template <class T> void swap(T *a, int h, int l)
{
int tmp = a[l];
a[l] = a[h];
a[h] = tmp;
}
// ==================
// selection sort
template <class T> void selectSort(T *a, int size)
{
int i, lowest;
for (i=0; i<size-1; i++) {
lowest = i;
for (int j=i+1; j<size; j++)
if (a[j] < a[lowest]) lowest = j;
if (i!=lowest) swap(a, i, lowest);
}
}
// ==================
// bubble sort
template <class T> void bubbleSort(T *a, int size)
{
for (int i=0; i<size; i++) {
bool work = false;
for (int j=0; j<size-i-1; j++) {
if (a[j] > a[j+1]) {
swap(a, j, j+1);
work = true;
}
}
if (!work) break;
}
}
// ==================
// insertion sort
template <class T> void insSort(T *a, int size)
{
int j, i;
for (i=1; i<size; i++) {
int tmp = a[i];
for (j=i-1; j>=0 && tmp < a[j]; j--)
a[j+1] = a[j];
a[j+1] = tmp;
}
}
// ===================
// quick sort
template <class T> int partition(T *a, int lb, int ub)
{
// considering the middle element as pivot avoids unnecessary
// passes in case array is already sorted. Never suffer O(n2).
swap(a, lb, (lb+ub)/2);
int small_end = lb;
for (int large_end=lb; large_end<ub; large_end++) {
if (a[large_end+1] < a[lb])
swap(a, ++small_end, large_end+1);
}
swap(a, lb, small_end);
return small_end;
}
template <class T> void quickSort(T *a, int size)
{
int lb=0, ub=size, pivot;
int stack[size*2];
push(stack, lb);
push(stack, ub);
while (!stackEmpty()) {
ub = pop(stack);
lb = pop(stack);
if (lb >= ub) continue;
pivot = partition(a, lb, ub);
push(stack, lb);
push(stack, pivot-1);
push(stack, pivot+1);
push(stack, ub);
}
}
template <class T> void quickSortRecursive(T *a, int lb, int ub)
{
if (lb >= ub) return;
int p_end = partition(a, lb, ub);
quickSortRecursive(a, lb, p_end-1);
quickSortRecursive(a, p_end+1, ub);
}
// =================
// heap sort
template <class T> void reHeap(T *a, int start, int end)
{
while (start*2+1 <= end) {
int ch_indx = start*2 +1;
int sw_indx = start;
if (a[sw_indx] < a[ch_indx])
sw_indx = ch_indx;
if (ch_indx+1 <= end && a[sw_indx] < a[ch_indx+1])
sw_indx = ++ch_indx;
if (sw_indx != start)
swap(a, sw_indx, start);
else
return;
start = sw_indx;
}
}
template <class T> void heapSort(T *a, int size)
{
int last_root = (size-2)/2;
while (last_root >= 0) {
reHeap(a, last_root, size-1);
last_root--;
}
int last = size-1;
while (last > 0) {
swap(a, 0, last);
reHeap(a, 0, --last);
}
}
// =================
// mergesort
template <class T> void mergeParts(T *a, int lb, int mid, int ub)
{
T storage[ub-lb+1];
int i, j, k;
//cout<<"lb: "<<lb<<" ub: "<<ub<<endl;
for (i=lb, k=0, j=mid+1; i<=mid && j<=ub; k++)
storage[k] = a[i] < a[j] ? a[i++] : a[j++];
while (i <= mid)
storage[k++] = a[i++];
while (j <= ub)
storage[k++] = a[j++];
j=lb;
for (i=0; i<=ub-lb; i++)
a[j++] = storage[i];
}
template <class T> void mergeSort(T *a, int size)
{
int i,j;
for (i=1; i<=size; i=i*2) {
for (j=0; j<size-i; j=j+i*2)
// mid = (j + j+2*i)/2 = i+j
mergeParts(a, j, j+i-1, MIN(j+2*i-1, size-1));
}
}
template <class T> void mergeSortRecursive_(T *a, int lb, int ub)
{
if (lb >= ub) return;
int mid = (ub+lb)/2;
mergeSortRecursive_(a, lb, mid);
mergeSortRecursive_(a, mid+1, ub);
mergeParts(a, lb, mid, ub);
}
// ===================
// radix sort
#define BASE 10
#define MAX 32
template <class T> void reNew(T **ptr, int *size)
{
T *tmp = new T [*size+MAX];
for (int i=0; i<*size; i++)
tmp[i] = *((*ptr)+i);
delete *ptr;
*ptr = tmp;
(*size) += MAX;
}
void freeMem(int **b)
{
for (int i=0; i<BASE; i++)
delete b[i];
}
template <class T> void radixSort(T *a, int size)
{
int *buckets[BASE]; // BASE number of buckets
int indx_t[BASE][BASE] = { 0 }; // tracks current index for each bucket and bucket size
int i; // indx on row [0], bucket size on [1]
long highest = a[0];
for (i=0; i<BASE; i++) { // initially fixed amount of mem for each bucket
buckets[i] = new T [MAX];
indx_t[1][i] = MAX;
}
for (i=0; i<size; i++)
if (a[i] > highest) highest=a[i];
ULONG m=10, n=1;
ULONG indx;
while (highest*10 >= m) {
// put numbers into buckets
for (i=0; i<size; i++) {
indx = (a[i] % m) / n;
buckets[indx][indx_t[0][indx]++] = a[i];
// if next indx > current size, reallocate mem for bucket
if ( !(indx_t[0][indx] % indx_t[1][indx]) )
reNew(&buckets[indx], &indx_t[1][indx]);
}
// copy back and reset index counters
indx=0;
for (i=0; i<BASE; i++) {
int j = 0;
while (j < indx_t[0][i])
a[indx++] = buckets[i][j++];
indx_t[0][i] = 0;
}
m *= BASE;
n *= BASE;
}
freeMem(buckets);
}
// ===================
// display
template <class T> void display(T *a, int size)
{
for (int i=0; i<size; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
}
// ==================
int main()
{
int data[] = {5,382,132,22,702,52,62,102,52,26};
int len = sizeof(data)/sizeof(data[0]);
display(data, len);
mergeSort(data, len);
//mergeSortRecursive(data, 0, len);
//quickSortRecursive(data, 0, len);
//radixSort(data, len);
display(data, len);
}
