Quick sort an array with large number of elements Terminated

[langtu2005]

Hi all,

I have not used C++ for a very long time. Recently I wrote a quick sort code with random pivot, and I wanted to calculate the time needed to run the quick sort function, but it only works with the array size up to 6 million. When I put 7 million, the program will be terminated even though I assign long long data type to all variables. Also can any of you show me how to count the comparisons in this quick sort? Please help!!!

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

void random_quicksort(int *array, int first, int last);
int random_partition(int *array, int first, int last);
void swap(int array[], int i, int j);

int main()
{
	int size;
	clock_t start, end;
	cout << "Enter the size of the array: ";
	cin >> size;
	int *array;
	array = new int [size];
	srand(time(0));
	cout << "Initial array: ";
	for (int i = 0; i < size; i++)
	{
		array[i] = rand() % 100;	// the array consists of numbers from 0 to 99
		cout << array[i] << " ";	// print out the initial array
	}
	cout << endl;
	start = clock();
	random_quicksort(array, 0, size-1);
	end = clock();
	cout << "Sorted array: ";
	for (int i = 0; i < size; i++)
		cout << array[i] << " ";	// print out the sorted array
	cout << endl;
	cout << "Total time: " << (end - start)/((double) CLOCKS_PER_SEC) << " seconds" << endl;
	delete [] array;
	return -1;
}

void random_quicksort(int *array, int first, int last)
{
	int q;
	if (first < last)
	{
		q = random_partition(array, first, last);
		random_quicksort(array, first, q-1);
		random_quicksort(array, q+1, last);
	}
}

int random_partition(int *array, int first, int last)
{
	int pivot_loc;
	srand(time(0));
	pivot_loc = first + rand() % (last-first+1);
	int pivot = array[pivot_loc];
	swap(array, pivot_loc, last);
	pivot_loc = last;
	int i = first - 1;
	for(int j = first; j <= last-1; j++)
	{
		if(array[j] <= pivot)
		{
			i++;
			swap(array, i, j);
		}
	}
	swap(array, i+1, pivot_loc);
	return i+1;
}

void swap(int *array, int i, int j)
{
	int temp;
	temp = array[i];
	array[i] = array[j];
	array[j] = temp;
}