Help with sorting algorithm

[yankerick]

Hey guys,

I have an school assignment that asks me to measure the most famous sorting algorithms for performance in terms of number of steps and CPU running time. ( Here I'm testing for running time)

I decided to test for bubble sort first:

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

void bubbleSort(int ar[], int size)
{
	int temp;
	for (int i = 0; i < size; i++)
	for (int j = 0; j < size - i - 1; j++)
	if (ar[j] > ar[j + 1])
	{
		temp = ar[j];
		ar[j] = ar[j + 1];
		ar[j + 1] = temp;
	}
}

int main(){

	clock_t start = clock();
	
	int *array;
	int size;
	cout << "Enter size of array: ";
	cin >> size;
	array = new int[size];
	for (int x = 0; x < size; x++)
	{
		cout << "Enter value for index " << x + 1 << ": ";
		cin >> array[x];
	}
	cout << "Before sorting: ";
	for (int i = 0; i < size; i++)
	{
		if (i == (size - 1))
			cout << array[i];
		else
			cout << array[i] << ", ";
	}
	bubbleSort(array, size*);
	cout << "\nAfter sorting: ";
	for (int j = 0; j < size; j++)
	{
		if (j == (size - 1))
			cout << array[j];
		else
			cout << array[j] << ", ";
	}
	
	delete array;
	|
	clock_t ends = clock();
	cout << "Running time: " << (double)(ends - start) / CLOCKS_PER_SEC << endl;

	return 0;
}

So basically what I want to know is:
1. Is this clock function giving the correct CPU running time?

2. Is there any way to write code that would help me measure the number of steps for each algorithm?

3.I need to test it for number of integers=100 then 200, then 300... Well you get my point, and I don't want to have to actually input 200 numbers with my keyboard. Is there any way to generate as many entries as I want?

[dhayden]

Is this clock function giving the correct CPU running time?

Yes, but look at where you're calling it. You're including the time to input the numbers and the time to print out the results. I think you want:

clock_t start = clock();
bubbleSort(array, size*);
clock_t ends = clock();

Is there any way to write code that would help me measure the number of steps for each algorithm?

Usually what this means is counting the number of times you swap two numbers in the sorting algorithm. Try changing bubbleSort() to return an int instead of void. Then increment a local variable each time you swap numbers in bubbleSort(). Return the total.

I need to test it for number of integers=100 then 200, then 300

Once you have the code working with the prompts just remove the prompts.

	cin >> size;
	array = new int[size];
	for (int x = 0; x < size; x++)
	{
		cin >> array[x];
	}

Put the input in a file and redirect cin to the file when you run the program.
myProg < inputfile.100
myProg < inputfile.200
myProg < inputfile.300

[Smac89]

I agree with @dhayden to a certain point, but I don't agree with his method of measuring the number of steps the algorithm takes. The number of steps (big O notation) for a sorting algorithm should be calculated by tallying the number of comparisons made.

If number of steps is calculated using the number of swaps then it is possible for the function to return 0 for already sorted sequences, which will only make sense if the function body were empty.

[MiiNiPaa]

clock is so imprecise on many platforms and modern PC are so fast, so you need sample size in thousands to get meaningful answer.

Also it is might be a good idea to randomly generate values for array.

[dhayden]

Smac89 is right. I should have said that you should count the number of comparisons, not the number of swaps. Sorry about that.