My assignment is:
Your goal is to write a program that sorts a list of 4-letter words using different sorting algorithms and report the fastest method. First your program should prompt the user to indicate the number of words to generate. Your program should then generate a list of random 4-letter words. These do not have to be actual words in the dictionary, just a string of 4 random characters like "zzbq" or "ybha". Next your program should ask the user for the name of an output file where each of the sorted results will be shown. Your program should run the 5 sorting algorithms listed below, timing each run and writing each result to the output file. After all 5 sorts are complete, report which sorting algorithm was the fastest.
* Selection Sort
* Insertion Sort
* Merge Sort
* Quick Sort
* Heap Sort
The sorted result should be written to the output file specified by the user. Since we are running 5 sorts, the output file will contain 5 sorted versions of the data.
#include <ctime>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// min_position()
// returns index of minimum in the part of the vector v[from] to v[to]
template <typename T>
int min_position (vector<T>& v, int from, int to) {
int min_pos = from;
for (int i = from+1; i <= to; i++)
if (v[i] < v[min_pos])
min_pos = i;
return min_pos;
}
// swap()
// swap two integer values
template <typename T>
void swap (T& x, T& y) {
T temp = x;
x = y;
y = temp;
return;
}
// selection_sort()
template <typename T>
void selection_sort (vector<T>& v) {
int next;
for (next=0; next<v.size()-1; next++) {
int min_pos = min_position(v, next, v.size()-1);
if (min_pos != next)
swap(v[min_pos], v[next]);
}
}
// insertion_sort()
template <typename T>
void insertion_sort (vector<T>& v) {
int i, value, length;
for (length=1; length < v.size(); length++) {
i = length-1;
value = v[length];
while (i >= 0 && v[i] > value) {
v[i+1] = v[i];
i--;
}
v[i+1] = value;
}
}
// merge_sort()
template <typename T>
void merge_sort (vector<T>& v, int from, int to) {
if (from==to)
return;
int mid = (from+to)/2;
merge_sort (v, from, mid);
merge_sort (v, mid+1, to);
merge (v, from, mid, to);
}
// merge()
template <typename T>
void merge(vector<T>& a, int from, int mid, int to) {
int n = to-from+1; //size of range to be merged.
vector<T> b(n); //temporary vector to copy into
int i1 = from; //position to consider in first half
int i2 = mid+1; //position to consider in second half
int j=0; //next open position in vector b
while (i1 <= mid && i2 <= to) {
if (a[i1] < a[i2]) {
b[j] = a[i1];
i1++;
}
else {
b[j] = a[i2];
i2++;
}
j++;
}
while (i1 <= mid) {
b[j] = a[i1];
i1++;
j++;
}
while (i2 <= to) {
b[j] = a[i2];
i2++;
j++;
}
for (j=0; j < n; j++)
a[from+j] = b[j];
return;
}
// partition()
template <typename T>
int partition (vector<T>& v, int left, int right, int pivot) {
T pivotValue = v[pivot];
swap (v[pivot], v[right]);
int store = left;
for (int i=left; i<right; i++)
if (v[i] <= pivotValue) {
swap(v[store], v[i]);
store++;
}
swap(v[right], v[store]);
return store;
}
// quick_sort()
template <typename T>
void quick_sort (vector<T>& v, int left, int right) {
if (right > left) {
int newPivot = partition(v, left, right, left);
quick_sort(v, left, newPivot-1);
quick_sort(v, newPivot+1, right);
}
return;
}
// heap_sort ()
template <typename T>
void heap_sort (vector<T>& v, int count) {
heapify (v, count); //place vector in max-heap order
int end = count - 1;
while (end > 0) {
swap (v[end], v[0]); //swap the root of the heap with the last element
siftDown (v, 0, end - 1); //put heap back in max-heap order
end = end - 1; /* decrease heap size by one so the previous max. value
will stay in its proper placement */
}
}
// heapify ()
template <typename T>
void heapify (vector<T>& v, int count) {
int start = (count - 2) / 2; //start is assigned the index of the last parent node
while (start >= 0) {
/* sift down the node at index start to the proper
place such that all nodes below the start
index are in heap order */
siftDown (v, start, count - 1);
start = start - 1;
}
// after sifting down the root all nodes/elements are in heap order
}
// siftDown()
template <typename T>
void siftDown (vector<T>& v, int start, int end) { // end is the limit of how far down to sift
int root = start;
int child;
while (root*2 + 1 <= end) // while the root has at least one child
child = root*2 + 1; // root*2+1 points to the left child
if (child + 1 <= end && v[child] < v[child +1]) /* if the child has a sibling and the
child's value is less than its sibling's... */
child = child + 1; // point to left child instead
if (child <= end && v[root] < v[child]) { // if out of max-heap order
swap (v[root], v[child]);
root = child;
}
else
return;
}
int main () {
// Prompt user for number of words.
int numWords;
cout << "Enter the number of 4-letter words: ";
cin >> numWords;
// Generate data set.
cout << "Generating data set...";
vector<string> dataSet;
string word = "aaaa"; // default string
for (int i=0; i < numWords; i++) {
for (int j=0; j<4; j++)
word[j] = (char) (rand()%26+(int)'a');
dataSet.push_back(word);
}
cout << "\nData set created.";
// Prompt user for file name.
string fileName;
cout << "\n\nEnter the name of the output file: ";
cin >> fileName;
ofstream fout;
fout.open(fileName.c_str( ));
cout << "\n";
/*******************************
** Selection Sort
*******************************/
vector<string> dataSetToSort = dataSet;
cout << "Starting Selection Sort... ";
int start_time = clock();
selection_sort (dataSetToSort);
// Print to file.
for (int i=0; i < numWords; i++)
fout << dataSetToSort[i] << " ";
// Calculate run time.
cout << "\nRun time = "
<< (double)(clock()-start_time)/CLOCKS_PER_SEC
<< " seconds";
/*******************************
** Insertion Sort
*******************************/
dataSetToSort = dataSet;
cout << "\n\nStarting Insertion Sort... ";
start_time = clock();
selection_sort (dataSetToSort);
// Print to file.
fout << "\n\n";
for (int i=0; i < numWords; i++)
fout << dataSetToSort[i] << " ";
// Calculate run time.
cout << "\nRun time = "
<< (double)(clock()-start_time)/CLOCKS_PER_SEC
<< " seconds";
/*******************************
** Insertion Sort
*******************************/
dataSetToSort = dataSet;
cout << "\n\nStarting Insertion Sort... ";
start_time = clock();
selection_sort (dataSetToSort);
// Print to file.
fout << "\n\n";
for (int i=0; i < numWords; i++)
fout << dataSetToSort[i] << " ";
// Calculate run time.
cout << "\nRun time = "
<< (double)(clock()-start_time)/CLOCKS_PER_SEC
<< " seconds";
/*******************************
** Merge Sort
*******************************/
dataSetToSort = dataSet;
cout << "\n\nStarting Merge Sort... ";
start_time = clock();
merge_sort (dataSetToSort, 0, dataSetToSort.size()-1);
// Print to file.
fout << "\n\n";
for (int i=0; i < numWords; i++)
fout << dataSetToSort[i] << " ";
// Calculate run time.
cout << "\nRun time = "
<< (double)(clock()-start_time)/CLOCKS_PER_SEC
<< " seconds";
/*******************************
** Quick Sort
*******************************/
dataSetToSort = dataSet;
cout << "\n\nStarting Quick Sort... ";
start_time = clock();
quick_sort (dataSetToSort, 0, dataSetToSort.size()-1);
// Print to file.
fout << "\n\n";
for (int i=0; i < numWords; i++)
fout << dataSetToSort[i] << " ";
// Calculate run time.
cout << "\nRun time = "
<< (double)(clock()-start_time)/CLOCKS_PER_SEC
<< " seconds";
/*******************************
** Heap Sort
*******************************/
dataSetToSort = dataSet;
cout << "\n\nStarting Heap Sort... ";
start_time = clock();
heap_sort (dataSetToSort, dataSetToSort.size());
// Print to file.
fout << "\n\n";
for (int i=0; i < numWords; i++)
fout << dataSetToSort[i] << " ";
// Calculate run time.
cout << "\nRun time = "
<< (double)(clock()-start_time)/CLOCKS_PER_SEC
<< " seconds";
cout << "\n";
fout.close ();
return 0;
}Whenever I run the program, everything works fine except for heap sort. Even after five minutes, my program doesn't print the run time of heap sort, and I can't seem to figure out what's wrong.
Any help would be greatly appreciated.