mcs/class/System.Core/System.Linq.Parallel/ParallelQuickSort.cs

   1 //
   2 // ParallelQuickSort.cs
   3 //
   4 // Author:
   5 //       Jérémie "Garuma" Laval <jeremie.laval@gmail.com>
   6 //
   7 // Copyright (c) 2010 Jérémie "Garuma" Laval
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining a copy
  10 // of this software and associated documentation files (the "Software"), to deal
  11 // in the Software without restriction, including without limitation the rights
  12 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  13 // copies of the Software, and to permit persons to whom the Software is
  14 // furnished to do so, subject to the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be included in
  17 // all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  22 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  24 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  25 // THE SOFTWARE.
  26
  27 #if NET_4_0 || MOBILE
  28 using System;
  29 using System.Linq;
  30 using System.Collections;
  31 using System.Threading;
  32 using System.Threading.Tasks;
  33 using System.Collections.Generic;
  34
  35 namespace System.Linq.Parallel
  36 {
  37         // HACK: ATM: parallelization of the sort is disabled as task
  38         // add more overhead than gain
  39         internal class ParallelQuickSort<T>
  40         {
  41                 readonly Comparison<T> comparison;
  42                 readonly IList<T> list;
  43                 readonly int[] indexes;
  44
  45                 class SortedCollection : IList<T>
  46                 {
  47                         int[] indexes;
  48                         IList<T> source;
  49
  50                         public SortedCollection (IList<T> source, int[] indexes)
  51                         {
  52                                 this.indexes = indexes;
  53                                 this.source = source;
  54                         }
  55
  56                         public int IndexOf (T item)
  57                         {
  58                                 throw new NotImplementedException();
  59                         }
  60
  61                         public void Insert (int index, T item)
  62                         {
  63                                 throw new NotImplementedException();
  64                         }
  65
  66                         public void RemoveAt (int index)
  67                         {
  68                                 throw new NotImplementedException();
  69                         }
  70
  71                         public T this[int index] {
  72                                 get {
  73                                         return source[indexes[index]];
  74                                 }
  75                                 set {
  76                                         throw new NotImplementedException();
  77                                 }
  78                         }
  79
  80                         public void Add (T item)
  81                         {
  82                                 throw new NotImplementedException();
  83                         }
  84
  85                         public void Clear ()
  86                         {
  87                                 throw new NotImplementedException();
  88                         }
  89
  90                         public bool Contains (T item)
  91                         {
  92                                 throw new NotImplementedException();
  93                         }
  94
  95                         public void CopyTo (T[] array, int arrayIndex)
  96                         {
  97                                 throw new NotImplementedException();
  98                         }
  99
 100                         public bool Remove (T item)
 101                         {
 102                                 throw new NotImplementedException();
 103                         }
 104
 105                         public int Count {
 106                                 get {
 107                                         return source.Count;
 108                                 }
 109                         }
 110
 111                         public bool IsReadOnly {
 112                                 get {
 113                                         return true;
 114                                 }
 115                         }
 116
 117                         IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 118                         {
 119                                 return null;
 120                         }
 121
 122                         IEnumerator IEnumerable.GetEnumerator ()
 123                         {
 124                                 return null;
 125                         }
 126                 }
 127
 128                 private ParallelQuickSort (IList<T> list, Comparison<T> comparison)
 129                 {
 130                         this.comparison = comparison;
 131                         this.list = list;
 132                         this.indexes = CreateIndexes (list.Count);
 133                 }
 134
 135                 static int[] CreateIndexes (int length)
 136                 {
 137                         var indexes = new int[length];
 138                         for (int i = 0; i < length; i++)
 139                                 indexes [i] = i;
 140
 141                         return indexes;
 142                 }
 143
 144                 SortedCollection DoSort ()
 145                 {
 146                         if (list.Count > 1) {
 147                                 if (list.Count < 5)
 148                                         InsertionSort (0, list.Count - 1);
 149                                 else
 150                                         Sort (0, list.Count - 1);
 151                         }
 152
 153                         return new SortedCollection (list, indexes);
 154                 }
 155
 156                 int Comparison (int index1, int index2)
 157                 {
 158                         return comparison (list[index1], list[index2]);
 159                 }
 160
 161                 void Sort (int left, int right)
 162                 {
 163                         if (left + 3 <= right) {
 164                                 int l = left, r = right - 1, pivot = MedianOfThree (left, right);
 165                                 while (true) {
 166                                         while (Comparison (indexes [++l], pivot) < 0) { }
 167                                         while (Comparison (indexes [--r], pivot) > 0) { }
 168                                         if (l < r)
 169                                                 Swap (l, r);
 170                                         else
 171                                                 break;
 172                                 }
 173
 174                                 // Restore pivot
 175                                 Swap (l, right - 1);
 176                                 // Partition and sort
 177                                 Sort (left, l - 1);
 178                                 Sort (l + 1, right);
 179                         } else
 180                                 // If there are three items in the subarray, insertion sort is better
 181                                 InsertionSort (left, right);
 182                 }
 183
 184                 /*void Sort (int left, int right, int depth)
 185                 {
 186                         int l = left, r = right - 1, pivot = MedianOfThree (left, right);
 187                         while (true) {
 188                                 while (Comparison (indexes[++l], pivot) < 0);
 189                                 while (Comparison (indexes[--r], pivot) > 0);
 190                                 if (l < r)
 191                                         Swap (l, r);
 192                                 else
 193                                         break;
 194                         }
 195
 196                         // Restore pivot
 197                         Swap (l, right - 1);
 198
 199                         // Partition and sort in parallel if appropriate
 200                         /*if (depth < maxDepth) {
 201                                 depth <<= 1;
 202                                 Task t = Task.Factory.StartNew (() => Sort (left, l - 1, depth));
 203                                 Sort (l + 1, right, depth);
 204
 205                                 t.Wait ();
 206                         } else {*/
 207                                 // Sequential
 208                 /*              Sort (left, l - 1);
 209                                 Sort (l + 1, right);
 210                         //}
 211                 }*/
 212
 213                 /*void ShellSort (int left, int right)
 214                 {
 215                         int[] gaps = new int[] { 4, 1};
 216
 217                         for (int ic = 0; ic < gaps.Length; ic++) {
 218                                 int inc = gaps[ic];
 219                                 int l = left + inc;
 220                                 for (int i = l; i <= right; i++) {
 221                                         T temp = list[i];
 222                                         int j = i;
 223                                         for (; j >= l && comparison (list[j - inc], temp) > 1; j -= inc)
 224                                                 list[j] = list[j - inc];
 225                                         list[j] = temp;
 226                                 }
 227                         }
 228                 }*/
 229
 230                 void InsertionSort (int left, int right)
 231                 {
 232                         for (int i = left + 1; i <= right; i++) {
 233                                 int j, tmp = indexes [i];
 234
 235                                 for (j = i; j > left && Comparison (tmp, indexes [j - 1]) < 0; j--)
 236                                         indexes [j] = indexes [j - 1];
 237
 238                                 indexes [j] = tmp;
 239                         }
 240                 }
 241
 242                 /*
 243                 void InsertionSort (int left, int right)
 244                 {
 245                         for (int i = left + 1; i <= right; i++) {
 246                                 int j;
 247                                 T tmp = list[i];
 248
 249                                 for (j = i; j > left && comparison (tmp, list [j - 1]) < 0; j--)
 250                                         list [j] = list [j - 1];
 251
 252                                 list [j] = tmp;
 253                         }
 254                 }*/
 255
 256                 void Swap (int left, int right)
 257                 {
 258                         int temp = indexes [right];
 259                         indexes [right] = indexes [left];
 260                         indexes [left] = temp;
 261                 }
 262
 263                 int MedianOfThree (int left, int right)
 264                 {
 265                         int center = (left + right) >> 1;
 266                         if (Comparison (indexes[center], indexes[left]) < 0)
 267                                 Swap (left, center);
 268                         if (Comparison (indexes[right], indexes[left]) < 0)
 269                                 Swap (left, right);
 270                         if (Comparison (indexes[right], indexes[center]) < 0)
 271                                 Swap (center, right);
 272                         Swap (center, right - 1);
 273
 274                         return indexes[right - 1];
 275                 }
 276
 277                 public static IList<T> Sort (IList<T> list, Comparison<T> comparison)
 278                 {
 279                         ParallelQuickSort<T> qs = new ParallelQuickSort<T> (list, comparison);
 280
 281                         return qs.DoSort ();
 282                 }
 283         }
 284 }
 285 #endif