C# Introsort
February 27, 2008 – 10:22 amHere is a C# implementation of the Introsort algorithm. Notice that the Introsort method is nearly identical to the Quicksort method. The only difference is the addition of checking for the depth limit (number of recursions — lines 51-59); when the depth limit has been reached, the Heapsort method is called to complete the sort of the remaining items of the present partition. See David Musser’s paper for an in-depth analysis of the Introsort algorithm, as well as a discussion about choosing the correct recursion depth.
This code is used to sort collections of objects of any class that implement IComparable. It is optimized for readability, not performance (if I were worried about performance I would have used the “unsafe” keyword and sorted everything using pointers), and includes functions for Quicksort, Heapsort, and Introsort, as well as some helper methods (Swap, SiftDown).
1: #region Copyright (c) 2008 Michael Ferguson [www.pherg.net]
2: /*****************************************************************************
3: * File: Sorter.cs
4: * Author: Michael Ferguson (http://www.pherg.net)
5: * Date: 19 February 2008
6: *
7: * This program is free software: you can redistribute it and/or modify it
8: * under the terms of the GNU General Public License as published by the Free
9: * Software Foundation, either version 3 of the License, or (at your option)
10: * any later version.
11: *
12: * This program is distributed in the hope that it will be useful, but WITHOUT
13: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15: * more details (http://www.gnu.org/licenses/gpl.txt).
16: ****************************************************************************/
17: #endregion
18:
19: using System;
20: using System.Collections.Generic;
21:
22: namespace Pherg
23: {
24: class Sorter<T> where T:IComparable
25: {
26: public Sorter ()
27: {
28: }
29:
30: public void Introsort (T[] array, int left, int right, int depthLimit)
31: {
32: if (left >= right)
33: {
34: // done sorting
35: return;
36: }
37: else if (left == right - 1)
38: {
39: // two element list
40: if (array[left].CompareTo(array[right]) > 0)
41: {
42: // left is greater than the right — swap them
43: Swap(array, left, right);
44: }
45:
46: // done sorting
47: return;
48: }
49: else if (depthLimit == 0)
50: {
51: // depth limit has reached maximum
52: Heapsort(array, left, right);
53: return;
54: }
55:
56: // decrement depth limit
57: depthLimit -= 1;
58:
59: // since this method is recursive avoid placing these variables on the
60: // stack until the last moment
61: int i = left;
62: int k = right;
63:
64: // choose a pivot and move it to the end of the list
65: int pivotIndex = (left + right) >> 1; // (left + right) / 2
66: T pivot = array[pivotIndex];
67: array[pivotIndex] = array[right];
68: array[right] = pivot;
69:
70: while (i < k)
71: {
72: // move the i index to the k until something is found that is
73: // greater than the pivot
74: while ((array[i].CompareTo(pivot) <= 0) && (i < k))
75: {
76: i++;
77: }
78:
79: // move the k index to the i until something is found that is
80: // less than the pivot
81: while ((pivot.CompareTo(array[k]) <= 0) && (i < k))
82: {
83: k -= 1;
84: }
85:
86: if (i < k)
87: {
88: // swap i and k
89: Swap(array, i, k);
90: }
91: }
92:
93: // put the pivot back
94: array[right] = array[k];
95: array[k] = pivot;
96:
97: // sort the left side
98: Introsort(array, left, i - 1, depthLimit);
99:
100: // sort the right side
101: Introsort(array, k + 1, right, depthLimit);
102:
103: }
104:
105: public void Quicksort (T[] array, int left, int right)
106: {
107: if (left >= right)
108: {
109: // done sorting
110: return;
111: }
112: else if (left == right - 1)
113: {
114: // two element list
115: if (array[left].CompareTo(array[right]) > 0)
116: {
117: // left is greater than the right — swap them
118: Swap(array, left, right);
119: }
120:
121: // done sorting
122: return;
123: }
124:
125: // since this method is recursive avoid placing these variables on the
126: // stack until the last moment
127: int i = left;
128: int k = right;
129:
130: // choose a pivot and move it to the end of the list
131: int pivotIndex = (left + right) >> 1; // (left + right) / 2
132: T pivot = array[pivotIndex];
133: array[pivotIndex] = array[right];
134: array[right] = pivot;
135:
136: while (i < k)
137: {
138: // move the i index to the k until something is found that is
139: // greater than the pivot
140: while ((array[i].CompareTo(pivot) <= 0) && (i < k))
141: {
142: i++;
143: }
144:
145: // move the k index to the i until something is found that is
146: // less than the pivot
147: while ((pivot.CompareTo(array[k]) <= 0) && (i < k))
148: {
149: k -= 1;
150: }
151:
152: if (i < k)
153: {
154: // swap i and k
155: Swap(array, i, k);
156: }
157: }
158:
159: // put the pivot back
160: array[right] = array[k];
161: array[k] = pivot;
162:
163: // sort the left side
164: Quicksort(array, left, i - 1);
165:
166: // sort the right side
167: Quicksort(array, k + 1, right);
168: }
169:
170: public void Heapsort (T[] array, int start, int end)
171: {
172: // to begin, place the array in max-heap order
173:
174: // get the index in array of the last parent node
175: int left = start + ((end - start) >> 1);
176: int right = end;
177: int offset = start;
178:
179: //while (left >= 0)
180: while (left >= start)
181: {
182: // sift down the node at index left to the proper place so that all
183: // nodes below the left index are in heap order
184: //SiftDown(array, left, array.Length - 1);
185: SiftDown(array, offset, left, end);
186: left -= 1;
187: }
188:
189: // all nodes should now be in max-heap order
190:
191: while (right > start)
192: {
193: // swap the maximum value of the heap with the last element of the
194: // heap
195: Swap(array, right, start);
196:
197: // decrease the size of the heap by one so that the previous max
198: // value will stay in its proper placement
199: right -= 1;
200:
201: // put the heap back in max-heap order
202: SiftDown(array, offset, start, right);
203: }
204: }
205:
206: private void SiftDown (T[] array, int offset, int start, int end)
207: {
208: int root = start;
209: int child;
210:
211: // keep going while the root has at least one child
212: while (((root - offset) * 2 + 1) <= (end - offset))
213: {
214: // get the left child
215: child = ((root - offset) * 2 + 1) + offset;
216:
217: // if the child has a sibling and the child’s value is less than its
218: // siblings
219: if (child < end && array[child].CompareTo(array[child + 1]) < 0)
220: {
221: // point to the right child instead
222: child += 1;
223: }
224: if (array[root].CompareTo(array[child]) < 0)
225: {
226: // out of max-heap order
227: Swap(array, root, child);
228:
229: // repeat to continue sifting down the child
230: root = child;
231: }
232: else
233: {
234: // all sifted
235: break;
236: }
237: }
238: }
239:
240: private void Swap (T[] array, int i, int k)
241: {
242: T swap = array[i];
243: array[i] = array[k];
244: array[k] = swap;
245: }
246: }
247: }
1 Trackback(s)