Sorting an array

[Teerlinc]

Hello, I am writing a program that measures the time that it takes to sort a large array. The sort algorithms that I have came directly from my programming book, but I seem to be getting an infinite loop. Can anyone tell me why and what I need to do to fix it? Please note, I have only listed the part of my program that I think is causing the problem.

 

#include<iostream>
#include<ctime>
#include<cstdlib>
#include<iomanip>
#include <time.h>
#include "SortAlgorithms.h"

using namespace std;

template<typename T>
void bubbleSort(T list[], int arraySize)
{
	bool needNextPass = true;

	for (int k = 1; (k < arraySize) && needNextPass; k++)
	{
		//Array may be sorted and next pass not needed
		needNextPass = false;
		for (int i = 0; i < (arraySize - k); i++)
		{
			if (list[i] > list[i + 1])
			{
				//Swap list[i] with list[i +1]
				T temp = list[i];
				list[i] = list[i + 1];
				list[i + 1] = temp;

				//Next Pass still needed
				needNextPass = true;  
			}
		}
	}
}


int main()
{
	cout << "\n\n  Array Size " << "|  Bubble Sort " << "     Merge Sort " << "     Quick Sort " << "     Heap Sort " << endl;
	cout << "_____________|______________________________________________________________" << endl;
	
	//set a seed for random number generation
	srand((unsigned int)time(0));
	
	//define first array size 
	int size = 500000;

	//While loop creates array for three sizes: 500,000 1000000 and 2000000
	while(size <= 2000000)
	{
		//create an array dynamically using new keyword
		int *randomArray = new int[size];

		//assign random integers to array
		for(int i = 0; i < size; i++)
		{
			randomArray[i] = rand();
			//cout << randomArray[i] << " ";
		}
//OBTAIN EXECUTION TIME OF SORTING ALGORITHMS FOR THIS ARRAY SIZE

		//Display table of sort times	
		cout << setw(13) <<  size << "| ";

//Take start time
		time_t startTime = time(0);

//Call Sort function
		bubbleSort(randomArray, size);
//Take end time
		time_t endTime = time(0);
		time_t executionTime = endTime - startTime;
//Display execution time
		cout << setw(13) << executionTime;

	//free memory so that memory it can be used for next array
		delete [] randomArray;

		//increment size by X2
		size = size * 2;
	}
	system ("pause");
	return 0;
}

[R0mai]

If you decrease size (and the while loop condition as well of course), then it finishes in reasonable time. It's not an infinite loop, Bubble sort is really that slow ;)

[ui uiho]

yes it is. try the sort function in the algorithms library. that usually works within a decent time. also removing/replacing the system ("pause"); is a good idea.

[Teerlinc]

Wow! I considered that maybe it was just sorting really slowly, but I thought that this was a little ridiculous. The size was assigned by my prof, so I will run it again and wait longer! :-P
Thanks for your responses!