2 * Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca>
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_INSERTSORT_H
23 #define _AAPL_INSERTSORT_H
36 * \brief Insertion sort an array of data.
38 * InsertSort can be used to sort any array of objects of type T provided a
39 * compare class is given. InsertSort is in-place. It does not require any
42 * Objects are not made aware that they are being moved around in memory.
43 * Assignment operators, constructors and destructors are never invoked by the
46 * InsertSort runs in O(n^2) time. It is most useful when sorting small arrays.
47 * where it can outperform the O(n*log(n)) sorters due to its simplicity.
48 * InsertSort is a not a stable sort. Elements with the same key will not have
49 * their relative ordering preserved.
55 template <class T, class Compare> class InsertSort
59 /* Sorting interface routine. */
60 void sort(T *data, long len);
65 * \brief Insertion sort an array of data.
67 template <class T, class Compare>
68 void InsertSort<T,Compare>::sort(T *data, long len)
70 /* For each next largest spot in the sorted array... */
71 for ( T *dest = data; dest < data+len-1; dest++ ) {
72 /* Find the next smallest element in the unsorted array. */
74 for ( T *src = dest+1; src < data+len; src++ ) {
75 /* If src is smaller than the current src, then use it. */
76 if ( compare( *src, *smallest ) < 0 )
80 if ( smallest != dest ) {
81 /* Swap dest, smallest. */
83 memcpy( tmp, dest, sizeof(T) );
84 memcpy( dest, smallest, sizeof(T) );
85 memcpy( smallest, tmp, sizeof(T) );
94 #endif /* _AAPL_INSERTSORT_H */