basic sorting algorithms implemented in C.

sorts.cpp

/*
 * =====================================================================================
 *
 *       Filename:  sorts.c
 *
 *    Description:  basic sorting algorithms
 *
 *        Version:  1.0
 *        Created:  09/23/2013 03:58:30 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ji.Zhilong (), [email protected]
 *   Organization:  SJTU
 *
 * =====================================================================================
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/* 
 * name: insertion sort
 * bad time complexity: n^2
 * good time complexity: n
 * space complexity: 1
 * stable: yes
 *
*/
template <typename T>
void insertion_sort(vector<T> &arr)
{
  T tmp;
  int j;
  for (int i = 1; i < arr.size(); i++) {
	tmp = arr[i];
	for (j = i - 1; j >= 0 && arr[j] > tmp; j--)
	  arr[j+1] = arr[j];
	arr[j+1] = tmp;
  }
}

/* 
 * name: bubble sort
 * bad time complexity: n^2
 * good time complexity: n
 * space complexity: 1
 * stable: yes
 *
*/
template <typename T>
void bubble_sort(vector<T> &arr)
{
  bool flag = true;
  for (int i = arr.size() - 1; i > 0 && flag; i--)
  {
	flag = false;
	for (int j = 0; j < i; j++)
	{
	  if (arr[j] > arr[j+1]) {
		swap(arr[j], arr[j+1]);
		flag = true;
	  }
	}
  }
}

/* 
 * name: selection sort
 * bad time complexity: n^2
 * good time complexity: n^2
 * space complexity: 1
 * stable: no 
 *
*/
template <typename T>
void selection_sort(vector<T> &arr)
{
  for (int i = 0; i < arr.size(); i++)
  {
	int mini = i;
	for (int j = i+1; j < arr.size(); j++)
	{
	  if (arr[j] < arr[mini])
		mini = j;
	}
	if (mini != i)
	{
	  swap(arr[i], arr[mini]);
	}
  }
}

/* 
 * name: heap sort
 * bad time complexity: nlgn
 * good time complexity: nlgn
 * space complexity: 1
 * stable: no
 *
*/
#define left(i) (2*(i)+1)
#define right(i) (2*(i)+2)
#define parent(i) (((i)-1)/2)

template <typename T>
void max_heap_fixup(vector<T> &arr, int i)
{
  for (int j = parent(i); (j >= 0 && i != 0) && arr[i] < arr[j];i = j, j=parent(i))
	swap(arr[i], arr[j]);
}

template <typename T>
void max_heap_fixdown(vector<T> &arr, int i, int n)
{
  int j = left(i);
  T tmp = arr[i];

  while (j < n)
  {
	if (j+1 < n && arr[j+1] > arr[j])
	  j++;
	if (arr[j] <= tmp)
	  break;

	arr[i] = arr[j];
	i = j;
	j = left(i);
  }
  arr[i] = tmp;
}

template <typename T>
void max_heap_add(vector<T> &arr, int n, const T &t)
{
  arr[n] = t;
  max_heap_fixup(arr, n);
}

template <typename T>
void max_heap_del(vector<T> &arr, int i)
{
  swap(arr[0], arr[i]);
  max_heap_fixdown(arr, 0, i);
}

template <typename T>
void make_max_heap(vector<T> &arr)
{
  int n = arr.size();
  for (int i = n/2 - 1; i >= 0; i--)
	max_heap_fixdown(arr, i, n);
}

template <typename T>
void heap_sort(vector<T> &arr)
{
  make_max_heap(arr);
  for (int i = arr.size() - 1; i >= 0; i--)
	max_heap_del(arr, i);
}

/* 
 * name: quick sort
 * bad time complexity: n^2
 * good time complexity: nlgn
 * space complexity: 1
 * stable: mostly false
 *
*/
template <typename T>
void quick_sort(vector<T> &arr, int first, int last)
{
  if (first >= last)
	return;
  T key = arr[first];
  int i = first + 1;
  int j = last;
  while(1)
  {
	while(arr[j] > key) j--;
	while(arr[i] < key && i < j) i++;
	if (i >= j) break;
	swap(arr[i], arr[j]);
	if (arr[i] == key) j--;
	else i++;
  }
  arr[first] = arr[j];
  arr[j] = key;
	
  quick_sort(arr, first, i - 1);
  quick_sort(arr, j+1, last);
}

/* 
 * name: merge sort
 * bad time complexity: n
 * good time complexity: nlgn
 * space complexity: n
 * stable: yes
 *
*/
template <typename T>
void merge_arry(vector<T> &arr, int first, int mid, int last, vector<T> &tmp)
{
  int i, j, m , n, k;
  i = first, j = mid + 1;
  m = mid, n = last;
  k = 0;
  while (i <= m && j <= n)
  {
	if (arr[i] < arr[j])
	  tmp[k++] = arr[i++];
	else
	  tmp[k++] = arr[j++];
  }

  while (i <= m)
	tmp[k++] = arr[i++];
  while (j <= n)
	tmp[k++] = arr[j++];

  for (i = 0; i < k; i++)
	arr[first+i] = tmp[i];
}

template <typename T>
void _merge_sort(vector<T> &arr, int first, int last, vector<T> &tmp)
{
  int mid = first + (last - first) / 2;
  if (first >= last)
	return;
  _merge_sort(arr, first, mid, tmp);
  _merge_sort(arr, mid + 1, last, tmp);
  merge_arry(arr, first, mid, last, tmp);
}

template <typename T>
void merge_sort(vector<T> &arr)
{
  vector<T> tmp(arr.size());
  _merge_sort(arr, 0, arr.size() - 1, tmp);
}

/* 
 * name: shell sort
 * bad time complexity: n*(lgn)^2
 * good time complexity: n
 * space complexity: 1
 * stable: no 
 *
*/
template <typename T>
void shell_sort(vector<T> &a)
{
  int i, j, gap, n;
  T tmp;
  n = a.size();
  while(gap <= n)
	gap = gap*3 + 1;

  while (gap > 0)
  {
	for (i = gap; i < n; i++)
	{
	  j = i - gap;
	  tmp = a[i];
	  while ((j >= 0) && (a[j] > tmp))
	  {
		a[j+gap] = a[j];
		j = j - gap;
	  }
	  a[j+gap] = tmp;
	}
	gap = (gap - 1) / 3;
  }
}

int
main(void)
{
  int test[10] = {5,1,3,7,8,10,4,-9,54,12};
  int i;
  vector<int> intv;
  for (i = 0; i < 10; i++) {
	cout << test[i] << " ";
	intv.push_back(test[i]);
  }
  cout << endl;
//  insertion_sort(intv);
//  bubble_sort(intv);
//  selection_sort(intv);
//  heap_sort(intv);
//  quick_sort(intv, 0, intv.size() - 1);
//  merge_sort(intv);
  shell_sort(intv);
  for (vector<int>::iterator it=intv.begin(); it != intv.end(); it++)
	cout << *it << " ";
  cout << endl;
}