/////////////////////////////////////////////////////////////////////////////////
// The Sort //
// //
/////////////////////////////////////////////////////////////////////////////////
#ifndef _SORT_H_
#define _SORT_H_
/////////////////////////////////////////////////////////////////////////////////
// The QuickSort //
// //
/////////////////////////////////////////////////////////////////////////////////
template<typename T>
int Quick(T* a, int s, int e)
{
T t = a[e];
int i = s - 1;
for(int j = s; j < e; j++ )
if(a[j] <= t)
{
i++;
swap(a[j],a[i]);
}
swap(a[i+1], a[e]);
return i+1;
}
template<typename T>
void QuickSort(T* a, int s, int e)
{
if( s < e )
{
int i = Quick(a, s, e);
//int i = part(a, s, e);
QuickSort(a, s, i-1);
QuickSort(a, i+1, e);
}
}
/////////////////////////////////////////////////////////////////////////////////
// The HeapSort //
// //
/////////////////////////////////////////////////////////////////////////////////
inline int left(int i)
{
return 2*i+1;
}
inline int right(int i)
{
return 2*i+2;
}
template<typename T>
void HeapHy(T* a, int n, int i)
{
int big = i;
//first find the lage of i, left(i),right(i)
if(left(i) < n)
{
big = a[i]>a[left(i)]?(i):(left(i));
if(right(i) < n)
big = a[big]>a[right(i)]?(big):(right(i));
}
//and if the i not the biggest change pos i with the bigest
if(i!=big)
{
swap(a[i], a[big]);
//then HeapHy(a, n, bigest)
HeapHy(a, n, big);
}
}
template<typename T>
void BuildHeap(T* a, int n)
{
for(int i = n/2; i > -1; i--)
HeapHy(a, n, i);
}
template<typename T>
void HeapSort(T* a, int n)
{
BuildHeap(a, n);
for(int i=n-1; i>0; i--)
{
swap(a[0], a[i]);
HeapHy(a, i, 0);
}
}
/////////////////////////////////////////////////////////////////////////////////
// The ShellSort //
// //
/////////////////////////////////////////////////////////////////////////////////
template<typename T>
void ShellSort(T* a, int s)
{
T t;
int i,j,k;
for(i=s/2; i>0; i=i/3)
{
for(j=i; j<s; j++)
{
t = a[j];
for(k=j-i; k>-1; k-=i)
{
if(a[k]>t)
a[k+i] = a[k];
}
a[k+i] = t;
}
}
}
#endif //_SORT_H_