Shell Sort

#ifndef SHELLSORT
#define SHELLSORT

namespace mystd
{
void ComputeStep(int *step, int size)
{
if (size < step =" size" step =" size"> 100 && size < step =" size" t="">
void ShellSort(T* sortee, int size)
{
int step = 0;
ComputeStep(&step, size);

while(step > 0)
{
for(int loop=0;loop=step
&& *(sortee + index - step) > value)
{
*(sortee + index) = *(sortee + index - step);
index = index - step;
}
*(sortee + index) = value;
}
--step;
}
}
}











#endif

Heap Sort

template
void Heapify(T* sortee, int currentRootIndex,
int size)
{
int finish = 0, maxChildIndex = 0;

while(currentRootIndex * 2 <= size && !finish) { if (currentRootIndex * 2 == size) { maxChildIndex = currentRootIndex * 2; } // To check next leaf with next+1 leaf else if (*(sortee + currentRootIndex * 2) > *(sortee + currentRootIndex *2 + 1))
{
maxChildIndex = currentRootIndex * 2;
}
else
{
maxChildIndex = currentRootIndex *2 + 1;
}

if (*(sortee + maxChildIndex)
> *(sortee + currentRootIndex))
{
int temp = *(sortee + maxChildIndex);
*(sortee + maxChildIndex) = *(sortee + currentRootIndex);
*(sortee + currentRootIndex) = temp;

currentRootIndex = maxChildIndex;
}
else
{
finish = 1;
}
}
}
// ================================================
template
void BuildHeap(T* sortee, int currentRootIndex,
int size)
{
for (int loop = (size / 2) - 1; loop>=0; --loop)
{
Heapify(sortee, loop, size);
}
}
// ================================================
template
void HeapSort(T* sortee, int size)
{
for (int loop = (size / 2) - 1; loop>=0; --loop)
{
BuildHeap(sortee, loop, size);
}

// To swap largest with last
for (int loop = size - 1; loop >= 1; --loop)
{
int temp = *(sortee + 0);
*(sortee + 0) = *(sortee + loop);
*(sortee + loop) = temp;

Heapify(sortee, 0, loop-1);
}
}

Bubble Sort

#ifndef BUBBLESORT
#define BUBBLESORT


namespace mystd
{




template
void BubbleSort(T * sortee, int & size)
{
for (int outerLoop=0;outerLoop *(sortee + innerLoop))
{
char temp = *(sortee + innerLoop-1);
*(sortee + innerLoop-1) = *(sortee + innerLoop);
*(sortee + innerLoop) = temp;
}
}
}
}








}

#endif

Selection Sort

#ifndef SELECTIONSORT
#define SELECTIONSORT


namespace mystd
{

template
void SelectionSort(T * sortee, int & size)
{
int min_index = 0;


for (int loop=0;loop {
min_index = loop;


for (int innerLoop=loop+1;innerLoop
{
if ( *(sortee + innerLoop)
< *(sortee + min_index))
{
min_index = innerLoop; //O(1)
}
}

T temp = *(sortee + loop);
*(sortee + loop) = *(sortee + min_index);
*(sortee + min_index) = temp;
}

/* Therefore, 1 + O(n) + O(n ^ 2)
SelectionSort = O(N ^ 2)
*/
}

/*
loop 0 - Select the minimum first put it index 0
- 1, 4, 7, 3, 2, 9, 10,
6, 8, 5
loop 1 - Select minimum put it index 1 - start innerLoop = 1
- 1, 2, 7, 3, 4, 9, 10,
6, 8, 5
loop 2 - Select minimum put it index 2 - start innerLoop = 2
- 1, 2, 3, 7, 4, 9, 10,
6, 8, 5
loop 3 - Select minimum put it index 3 - start innerLoop = 3
- 1, 2, 3, 4, 7, 9, 10,
6, 8, 5
loop 4 - Select minimum put it index 4 - start innerLoop = 4
- 1, 2, 3, 4, 5, 9, 10,
6, 8, 7
loop 5 - Select minimum put it index 5 - start innerLoop = 5
- 1, 2, 3, 4, 5, 6, 10,
9, 8, 7
loop 6 - Select minimum put it index 6 - start innerLoop = 6
- 1, 2, 3, 4, 5, 6, 7,
9, 8, 10
loop 7 - Select minimum put it index 7 - start innerLoop = 7
- 1, 2, 3, 4, 5, 6, 7,
8, 9, 10


*/
}


#endif

Insertion Sort

Insertion Sort



[code]

template
void InsertionSort(T *sortee, int & size)
{
for (int loop=1;loop < size ; ++loop)
{
int index = loop;
T value = *(sortee + loop);

while(index > 0
&&
*(sortee + index - 1) > value)
// If left > right
{
// Left assign to right
*(sortee + index) = *(sortee + index - 1);
--index;
}
*(sortee + index) = value;
}

}


[/code]