#include <cstdlib>
#include <iostream>
using namespace std;
#define SELECTSORT 1
#define INSERTSORT 1
#define BUBBLESORT 1
#define SHELLSORT 1
#define QUICKSORT 1
#define MERGESORT 1
template<typename T>
void print(T array[], int len)
{
for (int i=0; i<len; i++) {
cout<<array[i]<<" ";
}
cout<<endl;
}
template<typename T>
void Swap(T& a, T& b)
{
T temp = a;
a = b;
b = temp;
}
#ifdef SELECTSORT
template<typename T>
void SelectSort(T array[], int len)
{
int i = 0;
int j = 0;
int k = -1;
for (i=0; i<len; i++) {
k = i;
for (j=i+1; j<len; j++) {
if (array[j] < array[k]) {
k = j;
}
}
if (k != i) {
swap(array[i], array[k]);
}
}
}
#endif
#ifdef INSERTSORT
template<typename T>
void InsertSort(T array[], int len)
{
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
for (i=1; i<len; i++) {
k = i;
temp = array[k];
for (j=i-1; (j>=0)&&(array[j]>temp); j--) {
array[j+1] = array[j];
k = j;
}
array[k] = temp;
}
}
#endif
#ifdef BUBBLESORT
template<typename T>
void BubbleSort(T array[], int len)
{
int i = 0;
int j = 0;
int exchange = 1;
for (i=0; i<len && exchange; i++) {
exchange = 0;
for (j=len-1; j>0; j--) {
if (array[j] < array[j-1]) {
Swap(array[j], array[j-1]);
exchange = 1;
}
}
}
}
#endif
#ifdef SHELLSORT
template<typename T>
void ShellSort(T array[], int len)
{
int i = 0;
int j = 0;
int k = 0;
int temp = 0;
int gap = len;
do {
gap = gap / 3 + 1;
for (i=gap; i<len; i+=gap) {
k = i;
temp = array[k];
for (j=i-gap; j>=0&&array[j]>temp; j-=gap) {
array[j+gap] = array[j];
k = j;
}
array[k] = temp;
}
} while (gap > 1);
}
#endif
#ifdef QUICKSORT
template<typename T>
int parition(T array[], int low, int high)
{
int pv = array[low];
while (low < high) {
while ((low<high) && (array[high] >= pv)) {
high--;
}
Swap(array[low], array[high]);
while ((low<high) && (array[low] <= pv)) {
low++;
}
Swap(array[low], array[high]);
}
return low;
}
template<typename T>
void QSort(T array[], int low, int high)
{
if (low < high) {
int part = parition(array, low, high);
QSort(array, low, part-1); //You can think of it as the left-hand sequence
QSort(array, part+1, high); //You can think of it as the right-hand sequence & NBSP; & have spent
}
}
template<typename T>
void QuickSort(T array[], int len)
{
QSort(array, 0, len-1);
}
#endif
#ifdef MERGESORT
template<typename T>
void Merge(T src[], T des[], int low, int mid, int high)
{
int i = low;
int j = mid+1;
int k = low;
while (i<=mid && j<=high) {
if (src[i] < src[j]) {
des[k++] = src[i++];
} else {
des[k++] = src[j++];
}
}
while (i<=mid) {
des[k++] = src[i++];
}
while (j<=high) {
des[k++] = src[j++];
}
}
template<typename T>
void MSort(T src[], T des[], int low, int high, int max)
{
if (low == high) {
des[low] = src[low];
} else {
int mid = (low + high) / 2;
T *space = (T *)malloc(sizeof(T)*max);
if (space != NULL) {
MSort(src, space, low, mid, max);
MSort(src, space, mid+1, high, max);
Merge(space, des, low, mid, high);
}
free(space);
space = NULL;
}
}
template<typename T>
void MergeSort(T array[], int len)
{
MSort(array, array, 0, len-1, len);
}
#endif