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!
|
