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
|
void QuickSort(int A[], int FirstIdx, int LastIdx){
int PivotIdx;
void Partition(int A[], int FirstIdx, int LastIdx, int &PivotIdx);
if (FirstIdx LT LastIdx){
Partition(A, FirstIdx, LastIdx, PivotIdx);
QuickSort(A, FirstIdx, PivotIdx-1);
QuickSort(A, PivotIdx+1, LastIdx);
}
}
void Partition(int A[], int FirstIdx, int LastIdx, int &PivotIdxPtr){
void Swap(int &x, int &y);
int Pivot;
int FirstUnknownIdx, LastLeftIdx;
Pivot = A[FirstIdx];
LastLeftIdx = FirstIdx;
FirstUnknownIdx = FirstIdx + 1;
while(FirstUnknownIdx LTE LastIdx){
if (A[FirstUnknownIdx] LT Pivot){
Swap(A[FirstUnknownIdk], A[LastLeftIdx + 1]);
FirstUnknownIdx++;
LastLeftIdx++;
}
else
FirstUnknownIdx++;
}
Swap(A[FirstIdx], A[LastLeftIdx]);
PivotIdxPtr = LastLeftIdx;
}
void Swap(int &x, int &y){
int Temp;
Temp = x;
x = y;
y = Temp;
}
|