2 * Copyright 2002 Adrian Thurston <thurston@complang.org>
5 /* This file is part of Aapl.
7 * Aapl is free software; you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License as published by the Free
9 * Software Foundation; either version 2.1 of the License, or (at your option)
12 * Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
13 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with Aapl; if not, write to the Free Software Foundation, Inc., 59
19 * Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 #ifndef _AAPL_QUICKSORT_H
23 #define _AAPL_QUICKSORT_H
25 #include "insertsort.h"
38 * \brief Quick sort an array of data.
40 * QuickSort can be used to sort any array of objects of type T provided a
41 * compare class is given. QuickSort is in-place. It does not require any
44 * Objects are not made aware that they are being moved around in memory.
45 * Assignment operators, constructors and destructors are never invoked by the
48 * QuickSort runs in O(n*log(n)) time in the average case. It is faster than
49 * mergsort in the average case because it does less moving of data. The
50 * performance of quicksort depends mostly on the choice of pivot. This
51 * implementation picks the pivot as the median of first, middle, last. This
52 * choice of pivot avoids the O(n^2) worst case for input already sorted, but
53 * it is still possible to encounter the O(n^2) worst case. For example an
54 * array of identical elements will run in O(n^2)
56 * QuickSort is not a stable sort. Elements with the same key will not have
57 * their relative ordering preserved. QuickSort switches to an InsertSort
58 * when the size of the array being sorted is small. This happens when
59 * directly sorting a small array or when QuickSort calls iteself recursively
60 * on a small portion of a larger array.
66 template <class T, class Compare> class QuickSort :
67 public InsertSort<T, Compare>
70 /* Sorting interface routine. */
71 void sort(T *data, long len);
74 /* Recursive worker. */
75 void doSort(T *start, T *end);
76 T *partition(T *start, T *end);
77 inline T *median(T *start, T *end);
80 #define _QS_INSERTION_THRESH 16
82 /* Finds the median of start, middle, end. */
83 template <class T, class Compare> T *QuickSort<T,Compare>::
84 median(T *start, T *end)
86 T *pivot, *mid = start + (end-start)/2;
88 /* CChoose the pivot. */
89 if ( compare(*start, *mid) < 0 ) {
90 if ( compare(*mid, *end) < 0 )
92 else if ( compare(*start, *end) < 0 )
97 else if ( compare(*start, *end) < 0 )
99 else if ( compare(*mid, *end) < 0 )
107 template <class T, class Compare> T *QuickSort<T,Compare>::
108 partition(T *start, T *end)
110 /* Use the median of start, middle, end as the pivot. First save
111 * it off then move the last element to the free spot. */
112 char pcPivot[sizeof(T)];
113 T *pivot = median(start, end);
115 memcpy( pcPivot, pivot, sizeof(T) );
117 memcpy( pivot, end, sizeof(T) );
121 pivot = (T*) pcPivot;
123 /* Shuffle element to the correct side of the pivot, ending
124 * up with the free spot where the pivot will go. */
126 /* Throw one element ahead to the free spot at last. */
131 if ( compare( *first, *pivot ) > 0 ) {
132 memcpy(last, first, sizeof(T));
137 /* Throw one element back to the free spot at first. */
142 if ( compare( *last, *pivot ) < 0 ) {
143 memcpy(first, last, sizeof(T));
149 /* Put the pivot into the middle spot for it. */
150 memcpy( first, pivot, sizeof(T) );
155 template< class T, class Compare> void QuickSort<T,Compare>::
156 doSort(T *start, T *end)
158 long len = end - start + 1;
159 if ( len > _QS_INSERTION_THRESH ) {
161 T *pivot = partition( start, end );
162 doSort(start, pivot-1);
163 doSort(pivot+1, end);
165 else if ( len > 1 ) {
166 /* Array is small, use insertion sort. */
167 InsertSort<T, Compare>::sort( start, len );
172 * \brief Quick sort an array of data.
174 template< class T, class Compare>
175 void QuickSort<T,Compare>::sort(T *data, long len)
177 /* Call recursive worker. */
178 doSort(data, data+len-1);
181 #ifdef AAPL_NAMESPACE
185 #endif /* _AAPL_QUICKSORT_H */