My program uses merge and insertion sort to sort a set of numbers. It works perfectly fine for small inputs, less than 2 seconds for 1,000 ints. But I need to sort 1,000,000 ints. When I try with 1 million, it takes over 2 hours to sort. Can someone please help me optimize this program so it works faster?
FYI: I have several versions of this program because I have been trying to make it faster. Originally, my program would read 1 million ints from a text file, sort, then output the sorted numbers to a text file. But I assumed that was taking a large portion of the running time so I took that out completely.
Instead, I initialized the vector with 1,000,000 ints in the main program, like so:
vector<int> vec {7000, 8090, 189, 19, 0, 29032, ... ,90};
Again, my program works great with small input sizes. Any advice? Thank you!
#include<iostream>
#include<vector>
#include <time.h>
#include <stdio.h>
#include<fstream>
using namespace std;
void merge(vector<int> &vec, int left, int center, int right, int originalsize)
{
int leftVsize, rightVsize; //left and right vector sizes
vector<int> vec1;
leftVsize = center-left+1; //calculating left and right temporary vector sizes
rightVsize = right - center;
vector<int> tempLeft(leftVsize); //initializing temp left and right vectors
vector<int> tempRight(rightVsize);
for(int i = 0; i < tempLeft.size(); ++i)
{
tempLeft.at(i) = vec.at(left+i); //initializing left vector
}
for(int i = 0; i < tempRight.size(); ++i)
{
tempRight.at(i) = vec.at(i+center+1); //initializing right vector
}
int i = left, j = 0, k = 0;
while((j < tempLeft.size()) && (k < tempRight.size())) //while left and right vector have elements
{
if(tempLeft.at(j) <= tempRight.at(k)) //if left element is smaller
{
vec.at(i) = tempLeft.at(j); //add value to original vector
j++;
}
else //else
{
vec.at(i) = tempRight.at(k); //add value to original vector
k++;
}
i++;
}
while(j < tempLeft.size()) //while left vector has elements
{
vec.at(i++) = tempLeft.at(j++);
}
while(k < tempRight.size()) //while right vector has elements
{
vec.at(i++) = tempRight.at(k++);
}
}
void insertionSort(vector<int> &vec, int originalsize)
{
for(int i = 1; i < originalsize; ++i) //starting from 1 for original vector size
{
int tempval = vec[i]; //set tempval to vector value at 1
int j = i; //j now equals i
for(j = i; ((j > 0)&&(tempval < vec[j-1])); --j) //for j=i while j is greater than 0 and tempval is less than the number before it
{
vec[j] = vec[j-1]; //set vector[j] to vector[j-1]
}
vec[j] = tempval; //tempval now holds vec[j]
}
}
void sort(vector<int> &vec, int left, int right, int originalsize)
{
int insertion = right - left;
if(insertion <= 8) //if righ-left is less than or equal to 8
{
insertionSort(vec, originalsize); // call insertion sort
}
if(left < right)
{
int center = (left+right)/2; //calculating center of vector
sort(vec, left, center, originalsize); //calling sort for temp vector
sort(vec, center+1, right, originalsize); //calling sort for temp vector
merge(vec, left, center, right, originalsize); //calling merge to merge two vectors together
}
}
int main()
{
vector<int> vec { 1 million ints };
int temp;
clock_t q, q1, q2,t;
int orgsize = vec.size();
q=clock();
sort(vec, 0, (vec.size()-1), orgsize); //calling sort function
q=clock()-q;
cout << "Total Time: "<< ((float)q)/CLOCKS_PER_SEC <<"\n";
return 0;
}
insertionSort(vec, originalsize)
. \$\endgroup\$less than 2 seconds for 1,000 ints
. That's not a good sort time. 2 milli seconds would be good. 2 seconds is a time for1'000'000
integers. \$\endgroup\$