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