#include <j2k/DataType/Const.hpp>
#include <j2k/DataType/Sort/Sort.hpp>
Go to the source code of this file.
Defines | |
#define | QSTHRESHOLD 8 |
Functions | |
void | QuickSort (Elem *array, int Size) |
|
Definition at line 9 of file Qsort4.cpp. |
|
Definition at line 11 of file Qsort4.cpp. 00012 { 00013 int i = 0; 00014 int j = Size - 1; 00015 int listsize = Size; 00016 00017 struct QEntry Stack[100]; 00018 00019 int top = 0; 00020 int pivot; 00021 int pivotindex, l, r; 00022 00023 Stack[top].Left = i; 00024 Stack[top].Right = j; 00025 00026 while ( top >= 0 ) 00027 { 00028 // Pop Stack 00029 i = Stack[top].Left; 00030 j = Stack[top--].Right; 00031 00032 // Findpivot 00033 pivotindex = (i+j)/2; 00034 pivot = array[pivotindex]; 00035 swap( array, pivotindex, j ); // Stick pivot at end 00036 00037 // Partition 00038 l = i-1; 00039 r = j; 00040 00041 do { 00042 while ( array[++l] < pivot ); 00043 while (r && array[--r] > pivot ); 00044 00045 swap(array, l, r); 00046 00047 } while (l < r); 00048 00049 swap(array, l, r); // Undo final swap 00050 swap(array, l, j); // Put pivot value in place 00051 00052 // Load up Stack 00053 if ( (l-i) > QSTHRESHOLD ) // Left partition 00054 { 00055 Stack[++top].Left = i; 00056 Stack[ top].Right = l-1; 00057 } 00058 00059 if ( (j-l) > QSTHRESHOLD ) // Right partition 00060 { 00061 Stack[++top].Left = l+1; 00062 Stack[ top].Right = j; 00063 } 00064 } 00065 00066 InsertionSort( array, listsize ); // Final Insertion Sort 00067 } |