`' QuickSort. QuickSort, CombSort and ShellSort all exploit the principle of ' exchanging keys that are far apart in the list rather than adjacent. ' QuickSort does this most elegantly and rapidly. The approach is to choose a ' "pivot" value (ideally, the median key) and then to work from each end of the ' list toward the middle. A key at each end is compared to the pivot and ' nothing is done if the left key is less than the pivot or the right key is ' greater. When a left key greater than the pivot and a right key less than ' the pivot have been found, those keys (or their pointers) are swapped,' and the process continues until the left and right pointers cross. We then ' recursively call QuickSort on the left and right sublists until the lists are ' small (and delegate final sorting to low overhead InsertionSort).'' QuickSort does not need any auxiliary arrays, but uses a modest amount of ' stack space for recursion. It is not stable (although its descendent Ternary ' QuickSort is). On average, it is the fastest of the O(N log N) sorts,' but it suffers from rare "worst case" behavior where certain input orders of ' keys cause speed to deteriorate to O(N^2). Naive implementations of ' QuickSort that choose the middle key for pivot exhibit O(N^2) behavior on ' sorted lists. The version of QuickSort presented here makes worst case ' behavior very unlikely by choosing the median of the first,' last and middle keys as pivot. Two versions are provided. pQuickSortS is ' set up for strings and can be adapted to doubles by changing the declaration ' of array A(). QuickSortL is set up for longs, or A() can be redeclared for ' integers. '' Reference: Robert Sedgewick, "Implementing Quicksort Programs",' Comm. of the ACM 21(10):847-857 (1978).'' Speed: pQuickSortS sorts 500,000 random strings in 30.3 sec; sorts 100186 ' library call numbers in 11.3 sec; sorts 25479 dictionary words in 2.0 sec ' (random order), 1.3 sec (presorted) or 1.8 sec (reverse sorted). QuickSortL ' sorts 500,000 random longs in 56 seconds. Timed in Excel 2001 on an 800 mhz ' PowerBook.'' Bottom line: contends with RadixSort for fastest; better adapted than Radix ' for non-string data, but not stable.' Usage: Dim S1(L To R) As StringDim P1(L To R) As LongDim L1(L To R) As Long For I = L To R S1(I) = GetRandomString() P1(I) = I L1(I) = GetRandomLong()Next IpQuickSortS L, R, S1, P1QuickSortL L, R, L1' CODE:Sub pQuickSortS(L As Long, R As Long, A() As String, P() As Long) 'We put "sentinel" values flanking the real keys to avoid an extra test in ' the inner loop. A(L - 1) = MinStr A(R + 1) = MaxStr 'We mostly sort the list with QuickSort. pQuickS L, R, A(), P 'Then we finish up with low overhead InsertionSort pInsertS L, R, A(), PEnd SubSub pQuickS(L As Long, R As Long, A() As String, P() As Long) Dim MED As Long Dim LP As Long Dim RP As Long Dim Pivot As String Dim TMP As Long 'Sublists <= 12 keys will be finished by running the whole list once thru ' InsertionSort. If R - L > 12 Then 'Get the median pointer... MED = (L + R) 2 'and swap it to the leftmost position. TMP = P(MED) P(MED) = P(L) P(L) = TMP 'Now compare the leftmost, next leftmost & rightmost to choose a median of ' 3... If A(P(L + 1)) > A(P(R)) Then TMP = P(L + 1) P(L + 1) = P(R) P(R) = TMP End If If A(P(L)) > A(P(R)) Then TMP = P(L) P(L) = P(R) P(R) = TMP End If If A(P(L + 1)) > A(P(L)) Then TMP = P(L + 1) P(L + 1) = P(L) P(L) = TMP End If 'and use its key as our pivot. Pivot = A(P(L)) 'Now work inward from each end. LP = L RP = R + 1 Do 'Scan right for a pointer whose key >= Pivot. In case Pivot is the ' largest key, we have 'a sentinel value of MaxStr in A(R + 1) that will end a runaway loop. ' Using the sentinel 'avoids having a second test in the inner loop, ' so it can be as fast as possible. Do LP = LP + 1 Loop While A(P(LP)) < Pivot 'Scan left for a pointer whose key <= Pivot. Again, ' we have a sentinel value of MinStr 'in A(L - 1) to stop the loop if Pivot is the smallest value in the ' list. Do RP = RP - 1 Loop While A(P(RP)) > Pivot 'If the pointers have crossed we're done. If RP <= LP Then Exit Do 'Otherwise, swap the pair we've identified. TMP = P(LP) P(LP) = P(RP) P(RP) = TMP Loop 'Swap the pointer of the Pivot value back into place. TMP = P(L) P(L) = P(RP) P(RP) = TMP 'Sort the shorter sublist first so the recursion stack is limited to ' logarithmic depth. If (RP - 1) - L <= R - LP Then pQuickS L, RP - 1, A, P pQuickS LP, R, A, P Else pQuickS LP, R, A, P pQuickS L, RP - 1, A, P End If End IfEnd SubSub pInsertS(L As Long, R As Long, A() As String, P() As Long) Dim LP As Long Dim RP As Long Dim TMP As Long Dim T As String For RP = L + 1 To R TMP = P(RP) T = A(TMP) For LP = RP To L + 1 Step -1 If T < A(P(LP - 1)) Then P(LP) = P(LP - 1) Else Exit For Next LP P(LP) = TMP Next RPEnd SubSub QuickSortL(L As Long, R As Long, A() As Long) A(L - 1) = MinStr A(R + 1) = MaxStr QuickL L, R, A InsertL L, R, AEnd SubSub QuickL(L As Long, R As Long, A() As Long) Dim MED As Long Dim LP As Long Dim RP As Long Dim Pivot As String Dim TMP As Long If R - L > 12 Then MED = (L + R) 2 TMP = A(MED) A(MED) = A(L) A(L) = TMP If A(L + 1) > A(R) Then TMP = A(L + 1) A(L + 1) = A(R) A(R) = TMP End If If A(L) > A(R) Then TMP = A(L) A(L) = A(R) A(R) = TMP End If If A(L + 1) > A(L) Then TMP = A(L + 1) A(L + 1) = A(L) A(L) = TMP End If Pivot = A(L) LP = L RP = R + 1 Do Do LP = LP + 1 Loop While A(LP) < Pivot Do RP = RP - 1 Loop While A(RP) > Pivot If RP <= LP Then Exit Do TMP = A(LP) A(LP) = A(RP) A(RP) = TMP Loop TMP = A(L) A(L) = A(RP) A(RP) = TMP If (RP - 1) - L < R - LP Then QuickL L, RP - 1, A QuickL LP, R, A Else QuickL LP, R, A QuickL L, RP - 1, A End If End IfEnd SubSub InsertL(L As Long, R As Long, A() As Long) Dim LP As Long Dim RP As Long Dim TMP As Long For RP = L + 1 To R TMP = A(RP) For LP = RP To L + 1 Step -1 If TMP < A(LP - 1) Then A(LP) = A(LP - 1) Else Exit For Next LP A(LP) = TMP Next RPEnd Sub`