3 // ParallelQuickSort.cs
6 // Jérémie "Garuma" Laval <jeremie.laval@gmail.com>
8 // Copyright (c) 2010 Jérémie "Garuma" Laval
10 // Permission is hereby granted, free of charge, to any person obtaining a copy
11 // of this software and associated documentation files (the "Software"), to deal
12 // in the Software without restriction, including without limitation the rights
13 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
14 // copies of the Software, and to permit persons to whom the Software is
15 // furnished to do so, subject to the following conditions:
17 // The above copyright notice and this permission notice shall be included in
18 // all copies or substantial portions of the Software.
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
23 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
25 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
30 using System.Collections;
31 using System.Threading;
32 using System.Threading.Tasks;
33 using System.Collections.Generic;
37 // HACK: ATM: parallelization of the sort is disabled as task
38 // add more overhead than gain
39 internal class ParallelQuickSort<T>
41 readonly Comparison<T> comparison;
42 readonly IList<T> list;
43 readonly int[] indexes;
45 class SortedCollection : IList<T>
50 public SortedCollection (IList<T> source, int[] indexes)
52 this.indexes = indexes;
56 public int IndexOf (T item)
58 throw new NotImplementedException();
61 public void Insert (int index, T item)
63 throw new NotImplementedException();
66 public void RemoveAt (int index)
68 throw new NotImplementedException();
71 public T this[int index] {
73 return source[indexes[index]];
76 throw new NotImplementedException();
80 public void Add (T item)
82 throw new NotImplementedException();
87 throw new NotImplementedException();
90 public bool Contains (T item)
92 throw new NotImplementedException();
95 public void CopyTo (T[] array, int arrayIndex)
97 throw new NotImplementedException();
100 public bool Remove (T item)
102 throw new NotImplementedException();
111 public bool IsReadOnly {
117 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
122 IEnumerator IEnumerable.GetEnumerator ()
128 private ParallelQuickSort (IList<T> list, Comparison<T> comparison)
130 this.comparison = comparison;
132 this.indexes = CreateIndexes (list.Count);
135 static int[] CreateIndexes (int length)
137 var indexes = new int[length];
138 for (int i = 0; i < length; i++)
144 SortedCollection DoSort ()
146 if (list.Count > 1) {
148 InsertionSort (0, list.Count - 1);
150 Sort (0, list.Count - 1);
153 return new SortedCollection (list, indexes);
156 int Comparison (int index1, int index2)
158 return comparison (list[index1], list[index2]);
161 void Sort (int left, int right)
163 if (left + 3 <= right) {
164 int l = left, r = right - 1, pivot = MedianOfThree (left, right);
166 while (Comparison (indexes [++l], pivot) < 0) { }
167 while (Comparison (indexes [--r], pivot) > 0) { }
176 // Partition and sort
180 // If there are three items in the subarray, insertion sort is better
181 InsertionSort (left, right);
184 /*void Sort (int left, int right, int depth)
186 int l = left, r = right - 1, pivot = MedianOfThree (left, right);
188 while (Comparison (indexes[++l], pivot) < 0);
189 while (Comparison (indexes[--r], pivot) > 0);
199 // Partition and sort in parallel if appropriate
200 /*if (depth < maxDepth) {
202 Task t = Task.Factory.StartNew (() => Sort (left, l - 1, depth));
203 Sort (l + 1, right, depth);
208 /* Sort (left, l - 1);
213 /*void ShellSort (int left, int right)
215 int[] gaps = new int[] { 4, 1};
217 for (int ic = 0; ic < gaps.Length; ic++) {
220 for (int i = l; i <= right; i++) {
223 for (; j >= l && comparison (list[j - inc], temp) > 1; j -= inc)
224 list[j] = list[j - inc];
230 void InsertionSort (int left, int right)
232 for (int i = left + 1; i <= right; i++) {
233 int j, tmp = indexes [i];
235 for (j = i; j > left && Comparison (tmp, indexes [j - 1]) < 0; j--)
236 indexes [j] = indexes [j - 1];
243 void InsertionSort (int left, int right)
245 for (int i = left + 1; i <= right; i++) {
249 for (j = i; j > left && comparison (tmp, list [j - 1]) < 0; j--)
250 list [j] = list [j - 1];
256 void Swap (int left, int right)
258 int temp = indexes [right];
259 indexes [right] = indexes [left];
260 indexes [left] = temp;
263 int MedianOfThree (int left, int right)
265 int center = (left + right) >> 1;
266 if (Comparison (indexes[center], indexes[left]) < 0)
268 if (Comparison (indexes[right], indexes[left]) < 0)
270 if (Comparison (indexes[right], indexes[center]) < 0)
271 Swap (center, right);
272 Swap (center, right - 1);
274 return indexes[right - 1];
277 public static IList<T> Sort (IList<T> list, Comparison<T> comparison)
279 ParallelQuickSort<T> qs = new ParallelQuickSort<T> (list, comparison);