QuickSort troubles

Hi, I have this quicksort but it's not running, any thoughts? It compiles, but I can't get it to run, it just crashes.

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
//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 item where pivot is temporarily placed to sort rest 
		// of list (smallIndex pts to end of lower sublist so=> elems < pivot
		int pivot = (start + end)/2;
		int pivotElem = list[pivot];//actual elem @ the pivot
		int smallIndex = start;//lower sublist holds items >= pivot
		
		/**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
			{
				if ( list[i] <= list[pivot] )
				{
					//"add" to lower sublist
					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);
			quickSort(list,pivot + 1,end);

                        /**COMBINE STAGE, trivial array all sorted in place, no extra 
			array needed!**/
		}
	}//END quickSort 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main()
{
 int quickList[8] = {20,30,10,5,17,18,16,32};//NB: int is 4B and each
	//elem is 4B and we have 8 elems in total so 32B
	
	int arraySize = sizeof(quickList)/sizeof(int);
	
	quickSort(quickList,0,arraySize - 1);
	
	//print quicksort sorted list
	cout<<"Sorted list via Quick sort:"<<endl;
	for ( int i = 0; i < arraySize; i++ )
	{
		cout<<quickList[i]<<" ";
	}
	
	cout<<endl;
 return 0;
}


Btw, this is the output:
Sorted list via Quick sort:
16 10 17 20 5 18 30 32


Any help for my code would be appreciated, thanks!
Last edited on
Read the wikipedia article on quicksort and then use the debugger to step through your code. This is the kind of problem that debuggers were made for.
Topic archived. No new replies allowed.