Sorting algorithms

#include <iostream>
using namespace std;
// ascending order
template<class T>
bool ascending(T first, T second){
	return first<=second;
}
// descending order
template<class T>
bool descending(T first, T second){
	return first>=second;
}
// swap two elements of a given array
template<class T>
void swap(T arr[],unsigned ii,unsigned jj){
	T temp;
	temp=arr[ii];
	arr[ii]=arr[jj];
	arr[jj]=temp;
}
// bubble sort
/*
The idea is: For a particular ii, compare it with all the next element, if there is any element that breaks out the expected order than swap positions
*/
template<class T>
void bubbleSort(T arr[],unsigned size,bool(*comparison)(T,T)){
	for (unsigned ii=0;ii<size-1;++ii){
		for (unsigned jj=ii+1;jj<size;++jj){
			if (!comparison(arr[ii],arr[jj])) swap(arr,ii,jj);
		}
	}
}
// insertion sort
/*
The idea is: For a particular ii, compare it with the previous subarray
*/
template<class T>
void insertionSort(T arr[],unsigned size,bool(*comparison)(T,T)){
	for(unsigned ii=0;ii<size;++ii){ 		unsigned jj=ii; 		while (jj>0){
			if (!comparison(arr[jj-1],arr[jj])) swap(arr,jj-1,jj);
			jj--;
		}
	}
}
// selection sort
/*
The idea is: For a particular ii, seek for the min(max) of the subarray after it, if the found element is different from ii, then swap
*/
template<class T>
void selectionSort(T arr[],unsigned size,bool(*comparison)(T,T)){
	for(unsigned ii=0;ii<size-1;++ii){
		unsigned iMin=ii;
		for (unsigned jj=ii+1;jj<size;++jj){
			if (!comparison(arr[iMin],arr[jj])) iMin=jj;
		}
		if (iMin!=ii) swap(arr,iMin,ii);
	}
}
//merge sort
/*
The idea is: divide and conquer.
*/
// merge function
template<class T>
void merge(T arr[],unsigned start,unsigned mid,unsigned end){
	unsigned ii(start),jj(mid+1),kk(0);
	T temp[end-start+1];
	while (ii<=mid && jj<=end){
		if (arr[ii]<arr[jj]){
			temp[kk]=arr[ii];
			ii++;
		}else{
			temp[kk]=arr[jj];
			jj++;
		}
		kk++;
	}
	if (ii<=mid){
		for (unsigned tt=ii;tt<=mid;++tt,++kk){
			temp[kk]=arr[tt];
		}
	}
	if (jj<=end){
		for(unsigned tt=jj;tt<=end;++tt,++kk){
			temp[kk]=arr[tt];
		}
	}
	for (unsigned tt=0;tt<kk;++tt){
		arr[start+tt]=temp[tt];
	}
}
// recursion function
template<class T>
void mergeSort(T arr[],unsigned start,unsigned end){
	if (start<end){
		unsigned mid=(start+end)/2;
		mergeSort(arr,start,mid);
		mergeSort(arr,mid+1,end);
		merge(arr,start,mid,end);
	}
}
// Shell sort
/*
The idea is: Develop from insertion sort and use gap to avoid moving too far
*/
template<class T>
void shellSort(T arr[],unsigned size){
	for (unsigned gap=size/2;gap>0;gap/=2){
		cout<<"ga="<<gap<<endl;
		for (unsigned ii=gap;ii<size;++ii){
			cout<<"ii="<<ii<<endl; 			T temp=arr[ii]; 			unsigned jj; 			for(jj=ii;jj>=gap && arr[jj-gap]>temp;jj-=gap){
				cout<<"jj="<<jj<<endl;
				arr[jj]=arr[jj-gap];
			}
			arr[jj]=temp;
		}
	}
}

Advertisements