Sorting Algorithms

Write a program to test the following sorting algorithms:

Selection sort

Bubble s

ort

Modified bubble sort

Insertion sort

Quick sort

Your program should create

five

pointers for dynamic arrays that will be

randomly populated

with values between 50

150

(each array should have the exact same randomness

/values

)

. Using the c time library, the time the interval for sorting each array with

each of the sort algorithms above. Use a loop to

successively increase the size of your

dynamic arrays by a factor of two going from size 2^12 up to

2^20. Each time through the loop, print out the times for each sort

the algorithm in a table with a

heading that

looks like the below:

Size

selSort

bubSort

modBubSort

quickSort

insertSort

file

searchSortAlgorithmsTested.h is below

template

void modifiedBubbleSort(elemType list[], int length)

{

bool isSorted = false;

for (int iteration = 1; (iteration < length) && !isSorted;

iteration++)

{

isSorted = true; //assume that the sublist is sorted

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;

isSorted = false;

}

}

}

}//end modified bubble sort

template

int seqSearch(const elemType list[], int length, const elemType& item)

{

int loc;

bool found = false;

loc = 0;

while (loc < length && !found)

if (list[loc] == item)

found = true;

else

loc++;

if (found)

return loc;

else

return -1;

} //end seqSearch

template

int binarySearch(const elemType list[], int length,

const elemType& item)

{

int first = 0;

int last = length - 1;

int mid;

bool found = false;

while (first <= last && !found)

{

mid = (first + last) / 2;

if (list[mid] == item)

found = true;

else if (list[mid] > item)

last = mid - 1;

else

first = mid + 1;

}

if (found)

return mid;

else

return -1;

} //end binarySearch

template

void bubbleSort(elemType list[], int length)

{

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;

}

}

}

} //end bubbleSort

template

void swap(elemType list[], int first, int second)

{

elemType temp;

temp = list[first];

list[first] = list[second];

list[second] = temp;

} //end swap

template

int 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

void selectionSort(elemType list[], int length)

{

int loc, minIndex;

for (loc = 0; loc < length; loc++)

{

minIndex = minLocation(list, loc, length - 1);

swap(list, loc, minIndex);

}

} //end selectionSort

template

void insertionSort(elemType list[], int length)

{

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;

}

} //end insertionSort

template

void quickSort(elemType list[], int length)

{

recQuickSort(list, 0, length -1);

} //end quickSort

template

void 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

int 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

template

void heapSort(elemType list[], int length)

{

buildHeap(list, length);

for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0;

lastOutOfOrder--)

{

elemType temp = list[lastOutOfOrder];

list[lastOutOfOrder] = list[0];

list[0] = temp;

heapify(list, 0, lastOutOfOrder - 1);

}//end for

}//end heapSort

template

void heapify(elemType list[], int low, int high)

{

int largeIndex;

elemType temp = list[low]; //copy the root node of

//the subtree

largeIndex = 2 * low + 1; //index of the left child

while (largeIndex <= high)

{

if (largeIndex < high)

if (list[largeIndex] < list[largeIndex + 1])

largeIndex = largeIndex + 1; //index of the

//largest child

if (temp > list[largeIndex]) //subtree

//is already in a heap

break;

else

{

list[low] = list[largeIndex]; //move the larger

//child to the root

low = largeIndex; //go to the subtree to

//restore the heap

largeIndex = 2 * low + 1;

}

}//end while

list[low] = temp; //insert temp into the tree,

//that is, list

}//end heapify

template

void buildHeap(elemType list[], int length)

{

for (int index = length / 2 - 1; index >= 0; index--)

heapify(list, index, length - 1);

}