Notes

#ifndef H_SSorting
#define H_SSorting

#include <iostream>
#include <ctime>

using namespace std;

template <class elemType>
class SSorting {

public:
//Search Algorithms
int seqSearch(const elemType list[], int length, int& comparisons, const elemType& item);
int binarySearch(const elemType list[], int length, int& comparisons, const elemType& item);

//Sorting Algorithms
void bubbleSort(elemType list[], int length);

void selectionSort(elemType list[], int length);
int minLocation(elemType list[], int first, int last);

void insertionSort(elemType list[], int length);

void quickSort(elemType list[], int length);
void recQuickSort(elemType list[], int first, int last);
int partition(elemType list[], int first, int last);

void swap(elemType list[], int first, int second);
void printListInfo(const int list[], int length);

};


template <class elemType>
int SSorting<elemType>::seqSearch(const elemType list[], int length, int& comparisons, const elemType& item)
{
int loc;
bool found = false;

loc = 0;

while (loc < length && !found) {

if (list[loc] == item)
found = true;
else
loc++;

comparisons++;
}


if (found)
return loc;
else
return -1;
} //end seqSearch

template <class elemType>
int SSorting<elemType>::binarySearch(const elemType list[], int length, int& comparisons,
const elemType& item)
{
int first = 0;
int last = length - 1;
int mid;

bool found = false;

while (first <= last && !found)
{
mid = (first + last) / 2;

comparisons++;

if (list[mid] == item)
found = true;
else
{

comparisons++;

if (list[mid] > item)
last = mid - 1;
else
first = mid + 1;


}
}

if (found)
return mid;
else
return -1;
} //end binarySearch

template <class elemType>
void SSorting<elemType>::bubbleSort(elemType list[], int length)
{
clock_t time_req;
time_req = clock();


for (int iteration = 1; iteration < length; iteration++)
{
for (int index = 0; index < length - iteration;
index++)
{
if (list[index] > list[index + 1])
{
elemType temp = list[index];
list[index] = list[index + 1];
list[index + 1] = temp;
}
}
}

time_req = clock() - time_req;
cout << "Using bubbleSort function, it took " << (float)time_req / CLOCKS_PER_SEC << " seconds" << endl;

} //end bubbleSort

template <class elemType>
void SSorting<elemType>::selectionSort(elemType list[], int length)
{
int loc, minIndex;

clock_t time_req;
time_req = clock();


for (loc = 0; loc < length; loc++)
{
minIndex = minLocation(list, loc, length - 1);
swap(list, loc, minIndex);
}

time_req = clock() - time_req;
cout << "Using selectionSort function, it took " << (float)time_req / CLOCKS_PER_SEC << " seconds" << endl;


} //end selectionSort

template <class elemType>
void SSorting<elemType>::swap(elemType list[], int first, int second)
{
elemType temp;

temp = list[first];
list[first] = list[second];
list[second] = temp;
} //end swap

template <class elemType>
int SSorting<elemType>::minLocation(elemType list[], int first, int last)
{
int loc, minIndex;

minIndex = first;

for (loc = first + 1; loc <= last; loc++)
if (list[loc] < list[minIndex])
minIndex = loc;

return minIndex;
} //end minLocation

template <class elemType>
void SSorting<elemType>::insertionSort(elemType list[], int length)
{


clock_t time_req;
time_req = clock();

for (int firstOutOfOrder = 1; firstOutOfOrder < length;
firstOutOfOrder++)
if (list[firstOutOfOrder] < list[firstOutOfOrder - 1])
{
elemType temp = list[firstOutOfOrder];
int location = firstOutOfOrder;

do
{
list[location] = list[location - 1];
location--;
} while (location > 0 && list[location - 1] > temp);

list[location] = temp;
}

time_req = clock() - time_req;
cout << "Using insertionSort function, it took " << (float)time_req / CLOCKS_PER_SEC << " seconds" << endl;

} //end insertionSort

template <class elemType>
void SSorting<elemType>::quickSort(elemType list[], int length)
{
clock_t time_req;
time_req = clock();


recQuickSort(list, 0, length - 1);

time_req = clock() - time_req;
cout << "Using quickSort function, it took " << (float)time_req / CLOCKS_PER_SEC << " seconds" << endl;


} //end quickSort

template <class elemType>
void SSorting<elemType>::recQuickSort(elemType list[], int first, int last)
{
int pivotLocation;

if (first < last)
{
pivotLocation = partition(list, first, last);
recQuickSort(list, first, pivotLocation - 1);
recQuickSort(list, pivotLocation + 1, last);
}
} //end recQuickSort

template <class elemType>
int SSorting<elemType>::partition(elemType list[], int first, int last)
{
elemType pivot;

int index, smallIndex;

swap(list, first, (first + last) / 2);

pivot = list[first];
smallIndex = first;

for (index = first + 1; index <= last; index++)
if (list[index] < pivot)
{
smallIndex++;
swap(list, smallIndex, index);
}

swap(list, first, smallIndex);

return smallIndex;
} //end partition

#endif