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
|