Theory

Optimization is mature root of evil
Inheritance is source of error

R & B is key to FP
Object is key to OOP

BST

#ifndef TreeNode
#define TreeNode


#ifdef WIN32
// Windows Function


template
class treeNode
{
public:

T key;
T value;
int level;

treeNode *leftNode;
treeNode *rightNode;


treeNode() : key(T()), value(T()), level(1),
leftNode(0),
rightNode(0)
{}

treeNode(const T& aKey) : key(aKey),
value(T()), level(1)
leftNode(0),
rightNode(0)
{}

treeNode(const T& aKey, const T& aValue)
: key(aKey),
value(aValue), level(1)
leftNode(0),
rightNode(0)
{}

~treeNode()
{
}
};


#else
// POSIX Function


#endif



#endif



#ifndef BST
#define BST

#include
#include
#include "TreeNode.h"


#ifdef WIN32
// Window Function


template
class BSearchTree
{
private:

treeNode* root;
BSearchTree (treeNode *);
BSearchTree& operator=(const BSearchTree);

public:
BSearchTree();

~BSearchTree();

void Insert(const T&, const T&);
treeNode* InsertSearch(treeNode*, const T&);

void Remove(const T&);

void destroy()const;
void PostOrderDestroy(treeNode*)const;

// Root->Left->Right
void PreOrder()const;
void RecursivePreOrder(treeNode*)const;

// Left->Root->Right
void InOrder()const;
void RecursiveInOrder(treeNode*)const;

// Left->Right->Root
void PostOrder()const;
void RecursivePostOrder(treeNode*)const;


// Utility Function
int size()const;
int RecursiveCount(treeNode*, int&)const;

T& minValue()const;
T& maxValue()const;

int maxDepth()const;
int RecursiveMaxDepth(const treeNode*, int&, int&)const;

treeNode* successor(const T&)const;
treeNode* predecessor(const T&)const;
treeNode* search(const T&)const;

void mirrorSwap()const;
void RecursiveMirrorSwap(treeNode*)const;

void generatePath()const;
void RecursiveGeneratePaths(treeNode *, T [],
int)const;
void displayPath(T [], int)const;

void doubleTree();
void doubleTreeInsert(treeNode*, std::deque&, std::deque&);
void RecursiveDoubleTreeinsert(treeNode*, std::deque&, std::deque&);
void RecursiveCopy(treeNode*, std::deque&, std::deque&)const;

void display(treeNode*)const;

};

// ================================================
template
BSearchTree::BSearchTree() : root(0)
{
}
// ================================================
template
BSearchTree::~BSearchTree()
{
if (root != 0)
{
destroy();
}
}
// ================================================
template
void BSearchTree::Insert(const T &key, const T &value)
{
if (root != 0)
{
treeNode* newNode = new treeNode(key, value);
treeNode* iteratorNode = root;

iteratorNode = InsertSearch(this->root, key);

if (key <>key)
{
iteratorNode->leftNode = newNode;
}
else
{
iteratorNode->rightNode = newNode;
}
}
else
{
treeNode* newNode = new treeNode(key, value);
root = newNode;
}

/*
Top Down construction - Create root first
Bottom Up construction - Create child first
*/
}
// ================================================
template
treeNode* BSearchTree::InsertSearch(treeNode *iteratorNode,
const T& key)
{
if (iteratorNode != 0)
{
if (key <>key)
{
if (iteratorNode->leftNode != 0)
{
return InsertSearch(iteratorNode->leftNode, key);
}
}
else
{
if (iteratorNode->rightNode != 0)
{
return InsertSearch(iteratorNode->rightNode, key);
}
}
}

return iteratorNode;
}
// ================================================
template
void BSearchTree::Remove(const T &key)
{
/*
if no child, just delete
if one child, point by grandparent

if two children, swap with it with
inorder-successor
(Left child of right sub Tree)

Smallest in right sub tree
Traverse once to right , then continue
traverse to left

or inorder-predecessor
(Right child of Left sub Tree)
Largest in left sub tree
*/
if (root != 0 && (root->leftNode != 0
&& root->rightNode != 0))
{
treeNode* iteratorNode = root;
treeNode* parentRemoveNode = root;

while (iteratorNode->key != key
&& (iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
(iteratorNode->leftNode != 0)
? iteratorNode = iteratorNode->leftNode
: iteratorNode;

(iteratorNode->key != key)
? parentRemoveNode = parentRemoveNode->leftNode
: parentRemoveNode;
}
else
{
(iteratorNode->rightNode != 0)
? iteratorNode = iteratorNode->rightNode
: iteratorNode;

(iteratorNode->key != key)
? parentRemoveNode = parentRemoveNode->rightNode
: parentRemoveNode;
}
}

if (iteratorNode->key == key)
{
// Key is equal root's key/remove root
if (this->root->key == key
|| root->key == iteratorNode->key)
{
treeNode* iteratorNode = root;
treeNode* tempRightNode = root;
treeNode* previousLeftNode = root->leftNode;

// root got right node
if (iteratorNode->rightNode != 0)
{
iteratorNode = iteratorNode->rightNode;
tempRightNode = iteratorNode->rightNode;

if (iteratorNode->leftNode != 0)
{
while (iteratorNode->leftNode != 0)
{
iteratorNode = iteratorNode->leftNode;
}
}

treeNode* newRoot = iteratorNode;
treeNode* removeNode = root;

root = newRoot;
root->leftNode = previousLeftNode;
root->rightNode = tempRightNode;

delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;

}// root no right node
else
{
treeNode* removeNode = root;
treeNode* newRoot = root;

if (root->leftNode != 0)
{
newRoot = root->leftNode;
root->leftNode = newRoot;
}
delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}

} // remove child
else
{
// two children
if (iteratorNode->leftNode != 0
&& iteratorNode->rightNode != 0)
{
treeNode* removeNode = iteratorNode;
treeNode* tempLeftNode = iteratorNode->leftNode;

iteratorNode = iteratorNode->rightNode;
while(iteratorNode->leftNode != 0)
{
iteratorNode = iteratorNode->leftNode;
}

if (parentRemoveNode->key
> iteratorNode->key)
{
parentRemoveNode->leftNode = iteratorNode;
}
else
{
parentRemoveNode->rightNode = iteratorNode;
}

iteratorNode->leftNode = tempLeftNode;

delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}
// one children
else if ((iteratorNode->leftNode != 0
&& iteratorNode->rightNode == 0)
|| (iteratorNode->leftNode == 0
&& iteratorNode->rightNode != 0))
{
if (iteratorNode->leftNode != 0
&& iteratorNode->rightNode == 0)
{
treeNode* removeNode = iteratorNode;
treeNode* nextNode = iteratorNode->leftNode;

parentRemoveNode->leftNode = nextNode;
delete removeNode;
}
else
{
treeNode* removeNode = iteratorNode;
treeNode* nextNode = iteratorNode->rightNode;

parentRemoveNode->rightNode = nextNode;
delete removeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}

}
// no children
else if (iteratorNode->leftNode == 0
&& iteratorNode->rightNode == 0)
{
if (parentRemoveNode->leftNode
== iteratorNode)
{
parentRemoveNode->leftNode = 0;
}
else
{
parentRemoveNode->rightNode = 0;
}

delete iteratorNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
removeNode = 0;
}
}
}
else
{
cout << "\nKey Node not found\n"; } } else { cout << "\nRoot no child"; } } // ================================================ template
void BSearchTree::destroy() const
{
PostOrderDestroy(this->root);
}
// ================================================
template
void BSearchTree::PostOrderDestroy(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
PostOrderDestroy(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
PostOrderDestroy(aTreeNode->rightNode);
}

delete aTreeNode;
/*
set delete memory to 0
in order to avoid bug
when delete twice happen
*/
aTreeNode = 0;
}
}
// ================================================
template
void BSearchTree::PreOrder() const
{
if (root != 0)
{
cout << "Pre Order Display \n"; RecursivePreOrder(this->root);
}
}
// ================================================
template
void BSearchTree::RecursivePreOrder(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
display(aTreeNode);

if (aTreeNode->leftNode != 0)
{
RecursivePreOrder(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
RecursivePreOrder(aTreeNode->rightNode);
}
}
}
// ================================================
template
void BSearchTree::InOrder() const
{
if (root != 0)
{
cout << "In Order Display \n"; RecursiveInOrder(this->root);
}
}
// ================================================
template
void BSearchTree::RecursiveInOrder(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
RecursiveInOrder(aTreeNode->leftNode);
}

display(aTreeNode);

if (aTreeNode->rightNode != 0)
{
RecursiveInOrder(aTreeNode->rightNode);
}
}
}
// ================================================
template
void BSearchTree::PostOrder() const
{
if (root != 0)
{
cout << "Post Order Display \n"; RecursivePostOrder(this->root);
}
}
// ================================================
template
void BSearchTree::RecursivePostOrder(treeNode *aTreeNode) const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
RecursivePostOrder(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
RecursivePostOrder(aTreeNode->rightNode);
}

display(aTreeNode);
}
}
// ================================================

template
int BSearchTree::size()const
{
int numberNodes = 1;

if (this->root != 0)
{
numberNodes = RecursiveCount(this->root, numberNodes);
}

return numberNodes;
}
// ================================================
template
int BSearchTree::RecursiveCount(treeNode* aTreeNode,
int& numberNodes)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
numberNodes++;
numberNodes = RecursiveCount(aTreeNode->leftNode, numberNodes);
}

if (aTreeNode->rightNode != 0)
{
numberNodes++;
numberNodes = RecursiveCount(aTreeNode->rightNode, numberNodes);
}
}

return numberNodes;
}
// ================================================
template
T& BSearchTree::minValue()const
{
treeNode* iteratorNode = root;

if (this->root != 0)
{
while(iteratorNode->leftNode != 0)
{
iteratorNode = iteratorNode->leftNode;
}
}

return iteratorNode->value;
}
// ================================================
template
T& BSearchTree::maxValue()const
{
treeNode* iteratorNode = root;

if (this->root != 0)
{
while(iteratorNode->rightNode != 0)
{
iteratorNode = iteratorNode->rightNode;
}
}

return iteratorNode->value;
}
// ================================================
template
int BSearchTree::maxDepth()const
{
int depth = 1, tempHeight = 1;
if (this->root != 0)
{
depth = RecursiveMaxDepth(root, depth, tempHeight);
}
return depth;
}
// ================================================
template
int BSearchTree::RecursiveMaxDepth(const treeNode* aTreeNode,
int& depth, int& tempHeight)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
tempHeight++;
depth = tempHeight;
depth = RecursiveMaxDepth(aTreeNode->leftNode, depth, tempHeight);
--tempHeight;
}

if (aTreeNode->rightNode != 0)
{
tempHeight++;
depth = tempHeight;
depth = RecursiveMaxDepth(aTreeNode->rightNode, depth, tempHeight);
--tempHeight;
}
}

return depth;
}
// ================================================
template
treeNode* BSearchTree::successor(const T& key)const
{
treeNode* iteratorNode = root;
treeNode* successorNode = root;

while ((key != iteratorNode->key) &&
(iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
iteratorNode = iteratorNode->leftNode;
}
else
{
iteratorNode = iteratorNode->rightNode;
}
}

if (iteratorNode->leftNode != 0)
{
successorNode = iteratorNode->leftNode;
}

if (iteratorNode->rightNode != 0)
{
successorNode = iteratorNode->rightNode;
}

/*
return pointer was allowed here
because the pointee is in heap
Local pointer to pointee
&& references to local variable is
not allowed to return
*/
return successorNode;
}
// ================================================
template
treeNode* BSearchTree::predecessor(const T& key)const
{
treeNode* iteratorNode = root;
treeNode* parent = root;

while ((key != iteratorNode->key) &&
(iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
(iteratorNode->leftNode != 0)
? iteratorNode = iteratorNode->leftNode
: iteratorNode;

(iteratorNode->key != key)
? parent = iteratorNode->leftNode
: parent;
}
else
{
(iteratorNode->rightNode != 0)
? iteratorNode = iteratorNode->rightNode
: iteratorNode;

(iteratorNode->key != key)
? parent = parent->rightNode
: parent;
}
}

/*
return pointer was allowed here
because the pointee is in heap
Local pointer to pointee
&& references to local variable is
not allowed to return
*/
return parent;
}
// ================================================
template
treeNode* BSearchTree::search(const T& key)const
{
treeNode* iteratorNode = root;

while ((iteratorNode->key != key) &&
(iteratorNode->leftNode != 0
|| iteratorNode->rightNode != 0))
{
if (key <>key)
{
(iteratorNode->leftNode != 0)
? iteratorNode = iteratorNode->leftNode
: iteratorNode;
}
else
{
(iteratorNode->rightNode != 0)
? iteratorNode = iteratorNode->rightNode
: iteratorNode;
}
}
/*
return pointer was allowed here
because the pointee is in heap
Local pointer to pointee
&& references to local variable is
not allowed to return
*/
return iteratorNode;
}
// ================================================
template
void BSearchTree::mirrorSwap()const
{
if (this->root != 0)
{
RecursiveMirrorSwap(this->root);
}
}
// ================================================
template
void BSearchTree::RecursiveMirrorSwap(treeNode* aTreeNode)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode != 0)
{
if (aTreeNode->leftNode != 0
|| aTreeNode->rightNode!= 0)
{
treeNode* tempLeftNode = aTreeNode->leftNode;
aTreeNode->leftNode = aTreeNode->rightNode;
aTreeNode->rightNode = tempLeftNode;
}
RecursiveMirrorSwap(aTreeNode->leftNode);
}

if (aTreeNode->rightNode != 0)
{
RecursiveMirrorSwap(aTreeNode->rightNode);
}
}
}
// ================================================
template
void BSearchTree::generatePath()const
{
T valuePath[99];
if (this->root != 0)
{
valuePath[0] = this->root->value;
RecursiveGeneratePaths(this->root, valuePath, 1);
}
}
// ================================================
template
void BSearchTree::RecursiveGeneratePaths(treeNode *aTreeNode,
T valuePath [],
int index)const
{
if (aTreeNode != 0)
{
if (aTreeNode->leftNode == 0
&& aTreeNode->rightNode == 0)
{
displayPath(valuePath, index);
}

if (aTreeNode->leftNode != 0)
{
valuePath[index] = aTreeNode->leftNode->value;
index++;
RecursiveGeneratePaths(aTreeNode->leftNode, valuePath, index);
--index;
/*
Backtracking
Previous stack code here
Return from next stack to
previous stack
*/
}

if (aTreeNode->rightNode != 0)
{
valuePath[index] = aTreeNode->rightNode->value;
index++;
RecursiveGeneratePaths(aTreeNode->rightNode, valuePath, index);
--index;
/*
Backtracking
Previous stack code here
Return from next stack to
previous stack
*/
}
}
}
// ================================================
template
void BSearchTree::displayPath(T valuePath [], int index)const
{
int loop=0;
cout << "\nRoot to Leaf Path is : "; while (loop<<> ";
loop++;
}
}
// =================================================
template
void BSearchTree::doubleTree()
{
/*
std::queue is not itself a container, but
an adaptor (a facade) around a
container offering a limited interface.
Therefore, std::queue does not offer
iterators
*/
std::deque tempTreeKey;
std::deque tempTreeValue;

if (this->root != 0)
{
RecursiveCopy(this->root, tempTreeKey, tempTreeValue);
}

while (!tempTreeKey.empty()
&& !tempTreeValue.empty())
{
doubleTreeInsert(this->root, tempTreeKey, tempTreeValue);

tempTreeKey.pop_front();
tempTreeValue.pop_front();
}
}
// =================================================
template
void BSearchTree::RecursiveCopy(treeNode* aTreeNode,
std::deque& tempTreeKey, std::deque& tempTreeValue)const
{
if (aTreeNode != 0)
{
tempTreeKey.push_back(aTreeNode->key);
tempTreeValue.push_back(aTreeNode->value);

if (aTreeNode->leftNode != 0)
{
RecursiveCopy(aTreeNode->leftNode, tempTreeKey, tempTreeValue);
}

if (aTreeNode->rightNode != 0)
{
RecursiveCopy(aTreeNode->rightNode, tempTreeKey, tempTreeValue);
}
}
}
// ================================================
template
void BSearchTree::doubleTreeInsert(treeNode* aTreeNode,
std::deque& tempTreeKey,
std::deque& tempTreeValue)
{
if (aTreeNode != 0)
{
RecursiveDoubleTreeinsert(aTreeNode,
tempTreeKey, tempTreeValue);
}
}
// ================================================
template
void BSearchTree::RecursiveDoubleTreeinsert(treeNode* aTreeNode,
std::deque& tempTreeKey,
std::deque& tempTreeValue)
{
if (aTreeNode != 0)
{
if (tempTreeKey.front() <= aTreeNode->key)
{
if (aTreeNode->leftNode != 0)
{
RecursiveDoubleTreeinsert(aTreeNode->leftNode,
tempTreeKey, tempTreeValue);
}
else
{
treeNode* newNode = new treeNode(tempTreeKey.front(), tempTreeValue.front());
aTreeNode->leftNode = newNode;
}
}
else
{
if (aTreeNode->rightNode != 0)
{
RecursiveDoubleTreeinsert(aTreeNode->rightNode,
tempTreeKey, tempTreeValue);
}
else
{
treeNode* newNode = new treeNode(tempTreeKey.front(), tempTreeValue.front());
aTreeNode->rightNode = newNode;
}
}
}
}
// ================================================
template
void BSearchTree::display(treeNode* aTreeNode) const
{
cout << "Key is " <<>key << "\n"; cout << "Value is " <<>value << "\n";
}
// ================================================






#else

// POSIX function

#endif



#endif

Median of Three Quick Sort

#ifndef MEDIAN3QUICKSORT
#define MEDIAN3QUICKSORT

#include
#include "InsertionSort.h"

namespace mystd
{
template
void Median(T* sortee, T* pivotValue,
int left, int right)
{
int middle = (left + right) / 2 ;

if (*(sortee + left) > *(sortee + middle))
{
std::swap(*(sortee + left),
*(sortee + middle));
}

if (*(sortee + left) > *(sortee + right))
{
std::swap(*(sortee + left),
*(sortee + right));
}

if (*(sortee + middle) > *(sortee + right))
{
std::swap(*(sortee + middle),
*(sortee + right));
}

// Put middle element in right - 1
std::swap(*(sortee + middle),
*(sortee + right -1));

*pivotValue = *(sortee + right -1);

}

template
void Partition(T* sortee, T* pivotValue,
int left, int right)
{
int leftIncrement = left;
int rightDecrement = right - 1;

while(leftIncrement <> *pivotValue)
{
}

if (leftIncrement <>
int FindIndex(T* sortee, T pivotValue,
int right)
{
int pivotIndex = 0;

for (int loop=0;loop
void M3QuickSort(T* sortee, int left, int right)
{
int size = right;
const int CUTOFF = 0; T pivotValue = 0, pivotIndex = 0;

if (left + CUTOFF < right)
{
Median(sortee, &pivotValue, left, right);
Partition(sortee, &pivotValue, left, right);

pivotIndex = FindIndex(sortee, pivotValue, right);

M3QuickSort(sortee, left, pivotIndex - 1);
M3QuickSort(sortee, pivotIndex + 1, right);
}
}

}

#endif

Decimal To Binary

#include
#include
#include
#include
#include
#include
#include
#include
#include


using namespace std;

// ================================================
string DecimalToBinary(int&);

// ================================================
int main()
{
int number = 139;

string result = DecimalToBinary(number);
cout << result;
return 0;
}
// ================================================
string DecimalToBinary(int& number)
{
string result;
int temp = number;

std::stringstream aStm;
if (number < 255)
{
while(temp != 0)
{
int remainder = temp % 2;
temp = temp / 2;

aStm.str("");
aStm << remainder;
string aStr(aStm.str());

result.append(aStr);
}
}

std::reverse(result.begin(), result.end());

return result;
}

Quick Sort

#ifndef QUICKSORT

#define QUICKSORT

#include

namespace mystd

{

template

void Partition(T* sortee, int *pivotIndex,

int leftIncreaseIterator, 

int rightDecreaseIterator)

{

*pivotIndex = leftIncreaseIterator; 

if (leftIncreaseIterator 

<>

{

while(leftIncreaseIterator 

<>

{

while(*(sortee + leftIncreaseIterator)

< *(sortee + *pivotIndex))

{

++leftIncreaseIterator;

}

while(*(sortee + rightDecreaseIterator)

> *(sortee + *pivotIndex))

{

--rightDecreaseIterator;

}

if (leftIncreaseIterator 

<>

{

std::swap(*(sortee + leftIncreaseIterator), 

*(sortee + rightDecreaseIterator));

}

}

}

*pivotIndex = rightDecreaseIterator;

}

template  

void QuickSort(T* sortee, int left, int right)

{

int pivotIndex = 0;

if (left <>

{

Partition(sortee, &pivotIndex, left, right);

QuickSort(sortee, left, pivotIndex - 1);

QuickSort(sortee, pivotIndex + 1, right);

}

else

{

if (left <>

{

std::sort((sortee + left), (sortee + right));

}

}

}

}

/*

If size drop to below 20 the called

Shell Sort

*/

#endif

Merge Sort

#ifndef MERGESORT

#define MERGESORT

namespace mystd

{

template

void MergeSort(T* sortee, T* temp,

int left, int right)

{

int middle;

// Recursion base case

if (right > left)

{

middle = (left + right) / 2;

MergeSort(sortee, temp, left, middle);

MergeSort(sortee, temp, middle + 1, right);

Merge(sortee, temp, left, middle, middle + 1, right);

}

}

template

void Merge(T* sortee, T* temp,

int left, int leftEnd, int right, int rightEnd)

{

int size = rightEnd - left + 1;

int tempIndex =  left;

while(left <= leftEnd && right <= rightEnd)

{

if( *(sortee + left) < *(sortee + right) )

{

*(temp + tempIndex) = *(sortee + left);

left++;

tempIndex++;

}

else

{

*(temp + tempIndex) = *(sortee + right);

tempIndex++;

right++;

}

}

// To handle element in original

while(left <= leftEnd)

{

*(temp + tempIndex) = *(sortee + left);

left++;

tempIndex++;

}

// To handle Odd division

while(right <= rightEnd)

{

*(temp + tempIndex) = *(sortee + right);

right++;

tempIndex++;

}

for (int loop=0;loop<=size;++loop)

{

*(sortee + rightEnd) = *(temp + rightEnd);

--rightEnd;

}

}

template

void display(T*sortee, int size)

{

for (int loop=0;loop

{

cout << "Value is " << *(sortee + loop) << "\n";

}

}

}

/*

The height h of merge sort tree is O(lg n)

The overall amount or work done at 

the nodes of depth i is O(n)

We partition and merge 2i 

sequences of size n/2i

We make 2i+1 recursive calls

Thus, the total running time of merge-sort 

is O(n log n)

*/

#endif

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]