- Joined
- Jul 10, 2007
- Messages
- 6,306
win
Code:
void qsort2(int arr[], int startIndex, int endIndex) {
/*
* The array is split into two sections. The pivot is the middle point
* of these two sections. In this case, the pivot is the very first
* element in the array. All elements < the pivot are moved to the left
* side of the pivot. All elements > the pivot are moved to the right
* side of the pivot. The algorithm is recursive, meaning that the sections
* become smaller and smaller until they are all sorted ; ).
*
* startIndex and endIndex are the starts/ends of the section.
*
* The left/right represent what's been searched in the section.
* Left is the current left side of the section and right is the current
* right side of the section. The algorithm continues to close in via
* right-- and left++ until left == right. At this point, the pivot
* is swapped to that center position.
*/
int pivot = arr[startIndex], left = startIndex, right = endIndex;
/*
* Partitioning is moving all elements < pivot to left side
* and all elements > pivot to right side. Elements that are
* equal to pivot aren't moved. If the element is already
* on the correct side, it isn't moved.
*/
partition:
while (left < right) {
while (left < right && arr[right] >= pivot) --right;
if (left < right) arr[left++] = arr[right];
while (left < right && arr[left] <= pivot) ++left;
if (left < right) arr[right--] = arr[left];
} //while
/*
* Go left 1 as the element in the center will be > the pivot. The pivot is currently on the far left side, so
* the element to be swapped with the pivot needs to be < the pivot as that element is being moved left.
*/
arr[left] = pivot;
if (right + 1 < endIndex) {
if (startIndex < left) {
qsort2(arr, right + 1, endIndex);
endIndex = left;
left = startIndex;
right = endIndex;
pivot = arr[startIndex];
goto partition;
} //if
else {
startIndex = right + 1;
left = startIndex;
right = endIndex;
pivot = arr[startIndex];
goto partition;
} //else
} //if
else if (startIndex < left) {
endIndex = left;
left = startIndex;
right = endIndex;
pivot = arr[startIndex];
goto partition;
} //else if
} //qsort2
Last edited:
