comparing two sorts...

[Indianna32]

Hello,
I am supposed to write a program that will compare the run times of shell sort and insertion sort with two separate sets of data in files. One of the files is10,000 ints long otherwise I would put them up here. This is what I have so far. I am trying to get it to output the length of time each sort takes for each set of data. Then I have to make graphs comparing them. The graphs and big O stuff I get no problem, but I have not had to actually write a program in about a year and a half so am a bit rusty. Any help is appreciated. Thank you.
//--------------------------------------

#include <iomanip>
#include <ctime>
#include <iostream>
#include <fstream>  
using namespace std;

void shell_sort(int arr[], int length);
void insertion_sort(int arr[], int length);

int main()
{
	ifstream inputFile;
	int counter_s = 0;  
    int number = 0;
    int numbers_s [101];
    int numbers_l [10000]; 
    //----------------------------------------------------
    inputFile.open("Input_Small.txt");

    for (int i = 0; i < 101; i++)
       	inputFile >> numbers_s[i];	

	shell_sort(numbers_s, 101);
	insertion_sort(numbers_s, 101);

    inputFile.close();  
    //---------------------------------------------------    
    inputFile.open("Input_Large.txt");
    
    for (int i = 0; i < 10000; i++)
       	inputFile >> numbers_l[i];
        return 0;  
        
    shell_sort(numbers_l, 10000);   
	insertion_sort(numbers_l, 10000); 
        
    inputFile.close();
    
return 0;    
}  

void shell_sort (int arr[], int length)
{
	clock_t startTime = clock();
	int j;
	for (int gap = length / 2; gap > 0; gap /= 2)
	{
		for (int i = gap; i < length; ++i)
		{
			int temp = arr[i];
			for (j = i; j >= gap && temp < arr[j - gap]; j -= gap)
			{
				arr[j] = arr[j - gap];
		    }
		    arr[j] = temp;
	    } 
	}
	clock_t endTime = clock();
	clock_t duration = double(endTime - startTime)/CLOCKS_PER_SEC*1000;
	cout << "Elapsed time: " << duration << " ms" << endl;
}

void insertion_sort(int arr[], int length)
{
	clock_t startTime = clock();
	int i, j ,tmp;
 	
	for (i = 1; i < length; i++) 
	{
		j = i;
 		while (j > 0 && arr[j - 1] > arr[j]) 
		{
 			tmp = arr[j];
 			arr[j] = arr[j - 1];
 			arr[j - 1] = tmp;
 			j--;
 		}
 	}
 	clock_t endTime = clock();
 	clock_t duration = double(endTime - startTime)/CLOCKS_PER_SEC*1000;
	cout << "Elapsed time: " << duration << " ms" << endl;
}

[dhayden]

What is your question?

Looking at the code, a few things come to mind:

- It would be better to use vector<int> instead of arrays. That way you could write
bool readFile(const char *name, vector<int> &numbers)
and have it read all the numbers from the file into the vector, regardless of the file size. You could also pass the vector by itself to the sort functions.

- Passing the vector to the sort functions will avoid the big bug you have: Right now line 23 sorts the array so line 24 is passing the sorted array to insertion_sort. You need to pass the same unsorted data to both sort algorithms.

- In your sort functions, I'd print out the algorithm name, size of the vector, and the sort time, separated by tabs or commas. That will make it much easier to import into a spreadsheet. For example:

insertion,1000,0.0034

- Are you sure that your sorting algorithms are correct? I'd create an isSorted() function that checks the vector to ensure it's sorted. Call this in main() after each call to a sort algorithm.

[Indianna32]

Thank you very much for your feedback. That helps a great deal. It always irritates me; I can write some code, look at it, and have no idea where to go next. But the second someone points out an error it is so obvious. Thank you again