By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,680 Members | 2,123 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,680 IT Pros & Developers. It's quick & easy.

stack overflow before it attempts to sort 1 & 2 million int arrays

P: n/a
#include <iostream>
#include <ctime>
using namespace std;

// function declarations
void swap(int *a, int *b);
void sort(int arr[], int beg, int end);

int main()
{
system("cls");
// timer "stuff"
clock_t start1,start2,start3,start4,start5;
clock_t end1,end2,end3,end4,end5;
double time;

// integer arrays
int rand1[1000],rand2[10000],rand3[100000];
int *rand4,*rand5,i;
rand4 = new int[1000000];
rand5 = new int[2000000];

// fill arrays with random numbers
for (i = 0;i < 1000; i++)
rand1[i] = (rand() % 101);
for (i = 0;i < 10000; i++)
rand2[i] = (rand() % 101);
for (i = 0;i < 100000; i++)
rand3[i] = (rand() % 101);
for (i = 0;i < 1000000; i++)
rand4[i] = (rand() % 101);
for (i = 0;i < 2000000; i++)
rand5[i] = (rand() % 101);

cout << "*********************" << endl;
cout << "Quick Sort Algorithm:" << endl;
cout << "*********************\n" << endl;
// ***************************

// 1,000 numbers
start1 = clock();
sort(rand1,0,999);
end1 = clock();
cout << "\nCalculation Times:" << endl;
cout << "------------------" << endl;
time = double(end1 - start1)/CLOCKS_PER_SEC;
cout << "1,000 = " << time << " seconds." << endl;

// 10,000 numbers
start2 = clock();
sort(rand2,0,9999);
end2 = clock();
time = double(end2 - start2)/CLOCKS_PER_SEC;
cout << "10,000 = " << time << " seconds." << endl;

// 100,000 numbers
start3 = clock();
sort(rand3,0,99999);
end3 = clock();
time = double(end3 - start3)/CLOCKS_PER_SEC;
cout << "100,000 = " << time << " seconds." << endl;

// 1,000,000 numbers
start4 = clock();
sort(rand4,0,999999); // CRASHES HERE
end4 = clock();
time = double(end4 - start4)/CLOCKS_PER_SEC;
cout << "1,000,000 = " << time << " seconds." << endl;

delete [] rand4;

// 2,000,000 numbers
start5 = clock();
sort(rand5,0,1999999);
end5 = clock();
time = double(end5 - start5)/CLOCKS_PER_SEC;
cout << "2,000,000 = " << time << " seconds.\n" << endl;

delete [] rand5;

system("pause");
return 0;
}

void swap(int *a,int *b)
{
int t=*a; *a=*b; *b=t;
}
void sort(int arr[], int beg, int end)
{
if (end > beg + 1)
{
int piv = arr[beg], l = beg + 1, r = end;
while (l < r)
{
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
sort(arr, beg, l);
sort(arr, r, end);
}
}

Aug 13 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
* st*****@gmail.com attempts to implement QuickSort:

void swap(int *a,int *b)
{
int t=*a; *a=*b; *b=t;
}
void sort(int arr[], int beg, int end)
{
if (end > beg + 1)
{
int piv = arr[beg], l = beg + 1, r = end;
while (l < r)
{
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
sort(arr, beg, l);
sort(arr, r, end);
}
}


This is not really a C++ question, except the reason why you get
a crash.

The reason it crashes is you do a million or so recursive calls, or possibly
an infinite number (I'm not in the mood for analyzing the details), and on
current personal computers a million is about how much stack space you have.

The reason you do a million or so recursive calls, or possibly an infinite
number, has nothing to do with C++, and figuring this out is presumably part
of your assignment (which we won't do for you!), so therefore crossposted to
[comp.programming] with follow-ups there.
XFUT: [comp.programming]

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Aug 13 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.