quicksort 1 million elems

closed account (4ET0pfjN)
Why does the quicksort crash when I want to sort 1000000 elems. I used a random number generator to create 1000000 elems and store to an array. I am using in place quicksort, which I think means only moving elems about same original array.
The code is working with 1000, 10000, 100000 array sizes, just not 1000000.

Here is code if anyone has patience:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <sstream>
#include <fstream>
#include <iostream>
#include <ctime>
using namespace std;
//NB: need start and end to determine where to divide each level's lower and 
//	upper sublist; params: start, end refer to indices of cur list
	void quickSort(int *list, int start, int end)//initially:start=0, end=size-1
	{
		//STEP 1 - get pivot and initalize smallIndex to point to first itm where 
		//	pivot is temporarily placed to sort rest of list(smallIndex pts to end 
		//	of lower sublist(=> elems < pivot)
		int pivot = (start + end)/2;
		int smallIndex = start;//lower sublist holds items >= pivot but 
		//	initially smallIndex initialized to first item (which is where pivot
		//	elem temporarily stored (moved out of the way to sort rest of sublist)
		
		/**DIVIDE STAGE**/
		if ( start < end )//if more than one elem, then partition
		{
			//STEP 2 - mov pivot to first index and iterate to sort cur sublist
			int tempA = list[start];
			list[start] = list[pivot];
			list[pivot] = tempA;
			
			//iterate cur sublist and mov items to lower or upper sublist
			for ( int i = start + 1; i <= end; i++ )//DON'T compare pivot, start @ indx one over
			{
				//"add" to lower sublist
				if ( list[i] <= list[start] )//NB: we temporarily moved pivot elm to list front
				{
					smallIndex+=1;
					int tempB = list[i];
					list[i] = list[smallIndex];
					list[smallIndex] = tempB;
				}
			}
			//STEP 3 - mov pivot to where it belongs (=> swap positions w. end of
			//	cur sublist (so the indx smallIndex is boundary b/t lower and upper
			//	sublist
			//Once you reach end of list, time to move pivot where it belongs
			//	=> trade places with index smallIndex
			int tempC = list[start];//pivot elem is here, need to move to where 
			//	indx smallIndx is
			list[start] = list[smallIndex];
			list[smallIndex] = tempC;
			
			//STEP 4 - update the pivot index to use for dividing potential
			//	next level's lower and upper sublists
			pivot = smallIndex;

			quickSort(list,start,pivot - 1);//partition lower sublist
			quickSort(list,pivot + 1,end);//partition upper sublist
			
			/**COMBINE STAGE, trivial array all sorted in place, no extra 
			array needed!**/	
		}//END BIG IF
	}//END quickSort

int main()
{
	//read data into array and sort
	ifstream ifs;
	ifs.open("reversedData1000000.txt");/*CHANGE TO OPEN APPROPRIATE DATA FILE*/
	int arraySize = 1000000;/*CHANGE TO APPROPRIATE SIZE*/
	int *list = new int[arraySize];
	
	for ( int i = 0; i < arraySize; i++ )
	{
		ifs >> list[i];//read from a file into each index in array
	}
	
	clock_t startTime = clock();
	quickSort(list, 0, arraySize - 1);
	clock_t endTime = clock();
	clock_t duration = double(endTime - startTime);
	
	string quickSortedList = printList(list,arraySize);
	
	ifs.close();
	
	//store sorted list to new file
	ofstream ofs;
	ofs.open("reversedData1000000QuickSorted_3.txt");/*CHANGE TO APPROPRIATE SORTED FILE NAME TO SAVE RESULTS TO*/
	
	ofs <<"Sort time: "<<duration<<" ms"<<endl<<endl<< quickSortedList;
	ofs.close();
	
	cout<<"Sort time:"<<duration<<" ms"<<endl;

	return 0;
}
Last edited on
The code works fine on my PC, perhaps you have a hardware / software limitation?
I tried it with 10,000,000 items and it worked fine too...
What "crash" are you getting? If the code works on TPTM's machine, it's probably one of your settings. Are you working in Debug mode? If so, switch to Release mode. It has a larger allowed space. If that still doesn't cut it, dig through your IDE settings to find a way to increase it.

Anyway, make sure to post your crash next time. Pretty useless for us to be guessing like this.
closed account (4ET0pfjN)
I'm running it directly from windows cmd.
Windows Command Prompt is not a compiler or IDE ;)
closed account (4ET0pfjN)
I know, but it's faster than running in IDEs, is it not, and I just showed my prof in the lab today and it worked, he said it's the "prof distortion field", it took ~ 293 ms when I ran it!
Congrats ;) now can you explain what a Prof Distortion Field is?
Topic archived. No new replies allowed.