I call the time() function, run a sorting algorithm on a vector, then call time() function again. When I do this, the value returned from time() is the exact same for both calls, so I cannot calculate how long it takes for the sorting to complete. This happens when the vector has any number of elements; it doesn't change. I call time(NULL) in the sort() function at the bottom. Any help is appreciated. Thanks!
main.cpp
#include <cstdlib>
#include <iostream>
#include <vector>
#include <stdio.h>
#include <ctime>
using namespace std;
int listSize, listType;
static const char alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
template <typename E>
void printVector(vector<E>& list)
{
typename vector<E>::iterator it;
for (it = list.begin(); it != list.end(); it++)
cout << *it << " ";
}
template <typename E>
vector<E> generateList(int listType, int listSize)
{
vector<E> list;
if (listType == 1)
{
for (int i = 0; i < listSize; i++)
{
int random = rand() % 10001;
list.push_back(random);
}
}
else if (listType == 2)
{
for (int i = 0; i < listSize; i++)
{
double random = (10000 * (double)rand() / (double)RAND_MAX);
list.push_back(random);
}
}
else if (listType == 3)
{
for (int i = 0; i < listSize; i++)
{
char random = alphabet[rand() % (sizeof(alphabet) - 1)];
list.push_back(random);
}
}
else
{
cout << "Invalid type\n";
exit(0);
}
return list;
}
template <typename E>
void insertionSort(vector<E>& list)
{
E i, j, tmp;
for (i = 1; i < list.size(); i++)
{
j = i;
tmp = list[i];
while (j > 0 && tmp < list[j-1])
{
list[j] = list[j-1];
j--;
}
list[j] = tmp;
}
}
template <typename E>
vector<E> merge(vector<E>& list, vector<E>& left, vector<E>& right)
{
vector<E> result;
unsigned left_it = 0, right_it = 0;
while(left_it < left.size() && right_it < right.size())
{
if(left[left_it] < right[right_it])
{
result.push_back(left[left_it]);
left_it++;
}
else
{
result.push_back(right[right_it]);
right_it++;
}
}
while(left_it < left.size())
{
result.push_back(left[left_it]);
left_it++;
}
while(right_it < right.size())
{
result.push_back(right[right_it]);
right_it++;
}
list = result;
return list;
}
template <typename E>
vector<E> mergeSort(vector<E>& list)
{
if(list.size() == 1)
{
return list;
}
typename vector<E>::iterator middle = list.begin() + (list.size() / 2);
vector<E> left(list.begin(), middle);
vector<E> right(middle, list.end());
left = mergeSort(left);
right = mergeSort(right);
return merge<E>(list, left, right);
}
template <typename E>
void shiftRight(vector<E>& list, int low, int high)
{
int root = low;
while ((root*2)+1 <= high)
{
int leftChild = (root * 2) + 1;
int rightChild = leftChild + 1;
int swapIndex = root;
if (list[swapIndex] < list[leftChild])
{
swapIndex = leftChild;
}
if ((rightChild <= high) && (list[swapIndex] < list[rightChild]))
{
swapIndex = rightChild;
}
if (swapIndex != root)
{
double tmp = list[root];
list[root] = list[swapIndex];
list[swapIndex] = tmp;
root = swapIndex;
}
else
{
break;
}
}
return;
}
template <typename E>
void heapify(vector<E>& list, int low, int high)
{
int midIndex = (high - low - 1)/2;
while (midIndex >= 0)
{
shiftRight(list, midIndex, high);
midIndex--;
}
return;
}
template <typename E>
void heapSort(vector<E>& list, int size)
{
heapify(list, 0, size - 1);
int high = size - 1;
while (high > 0)
{
double tmp = list[high];
list[high] = list[0];
list[0] = tmp;
high--;
shiftRight(list, 0, high);
}
return;
}
template <typename E>
int pivot(vector<E>& list, int first, int last)
{
int p = first;
E pivotElement = list[first];
for(int i = first+1 ; i <= last ; i++)
{
if(list[i] <= pivotElement)
{
p++;
E temp = list[i];
list[i] = list[p];
list[p] = temp;
}
}
E temp = list[p];
list[p] = list[first];
list[first] = temp;
return p;
}
template <typename E>
void quickSort(vector<E>& list, int first, int last)
{
E pivotElement;
if(first < last)
{
pivotElement = pivot(list, first, last);
quickSort(list, first, pivotElement-1);
quickSort(list, pivotElement+1, last);
}
}
template <typename E>
bool sort(vector<E>& list)
{
int again = 0;
int sort = 0;
long int start, finish, duration;
cout << "Which sorting algorithm would you like to use?" << endl;
cout << " 1 for Insertion Sort\n 2 for Merge Sort\n 3 for Heapsort\n 4 for Quicksort" << endl;
cin >> sort;
cout << endl;
printVector(list);
cout << "\n" << endl;
start = time(NULL);
if (sort == 1)
insertionSort(list);
else if (sort == 2)
mergeSort(list);
else if (sort == 3)
heapSort(list, list.size());
else if (sort == 4)
quickSort(list, 0, list.size() - 1);
else {
cout << "Invalid command\n";
exit(0);
}
finish = time(NULL);
duration = finish - start;
cout << start << endl;
cout << "Sorting the list took " << duration << " seconds." << endl;
cout << finish << endl;
printVector(list);
while (again == 0) {
cout << "\n\nWould you like to go again? (1 for yes, 2 for no)\n";
cin >> again;
if (again == 1)
return true;
else if (again == 2)
return false;
}
}
int main(int argc, char** argv)
{
bool again = true;
while (again) {
cout << "How many items do you want to sort? (0 to quit)" << endl;
cin >> listSize;
if (listSize == 0)
exit(0);
else if (listSize < 0) {
cout << "Invalid input.\n";
exit(0);
}
/* Change first parameter of generateList() to 1-3
* 1 for ints, 2 for doubles, 3 for chars
*
* Also change vector types in the three places below to
* the corresponding parameter type.
*/
vector<char> list = generateList<char>(3, listSize);
again = sort<char>(list);
}
}
