[WikiDyd] [TitleIndex] [WordIndex

Algorytmy sortowania dla typów generycznych C#

   1 using System;
   2 using System.Collections.Generic;
   3 using System.Text;
   4 
   5 namespace aisd
   6 {
   7     public class Sort<T> where T : IComparable<T>
   8     {
   9         public static void InSort(T[] a)
  10         {
  11             for (int i = 1; i < a.Length; i++)
  12             {
  13                 T tmp = a[i];
  14                 int j = i;
  15                 for (; j > 0 && a[j - 1].CompareTo( tmp ) > 0; j--)
  16                     a[j] = a[j - 1];
  17                 a[j] = tmp;
  18             }
  19         }
  20         public static void MergeSort(T[] a)
  21         {
  22             T[] w = new T[a.Length];
  23             for (int ml = 1; ml < a.Length; ml *= 2)
  24             {
  25                 for (int i = 0; i <= a.Length-ml; i += 2*ml)
  26                 {
  27                     merge(a, w, i,
  28                                 i + ml < a.Length ? i+ml : a.Length,
  29                                 i + 2*ml <= a.Length ? i+2*ml : a.Length
  30                     );
  31                 }
  32             }
  33         }
  34         private static void merge(T[] s, T[] d, int f, int m, int t)
  35         {
  36             int i = f;
  37             int j = m;
  38             int k = f;
  39             while (i < m && j < t)
  40                 if (s[i].CompareTo(s[j]) <= 0)
  41                     d[k++] = s[i++];
  42                 else
  43                     d[k++] = s[j++];
  44             while (i < m)
  45                 d[k++] = s[i++];
  46             while (j < t)
  47                 d[k++] = s[j++];
  48             for (k = f; k < t; k++)
  49                 s[k] = d[k];
  50         }
  51         public static void QuickSort(T[] a)
  52         {
  53             Stack<int> s = new Stack<int>();
  54             s.Push(0);
  55             s.Push(a.Length - 1);
  56             int f, t;
  57             while( s.Count > 0 ) {
  58                 t = s.Pop();
  59                 f = s.Pop();
  60                 int m = divide(a, f, t);
  61                 if( t-m > 1 ) {
  62                     s.Push(m+1);
  63                     s.Push(t);
  64                 }
  65                 if( m-f > 1 ) {
  66                     s.Push( f );
  67                     s.Push(m-1);
  68                 }
  69             }
  70         }
  71 
  72         private static int divide(T[] a, int f, int t)
  73         {
  74             int x = (new Random()).Next(f,t);
  75             T tmp = a[x];
  76             a[x] = a[f];
  77             a[f] = tmp;  // tmp holds dividing element
  78             int i = f + 1;
  79             int j = t;
  80             while (i < j)
  81             {
  82                 while ( i < j && a[i].CompareTo(tmp) <= 0) i++;
  83                 while ( j > i &&a [j].CompareTo(tmp) > 0) j--;
  84                 if (i < j) {
  85                     T w = a[i];
  86                     a[i] = a[j];
  87                     a[j] = w;
  88                 }
  89             }
  90             if (a[i].CompareTo(tmp) > 0) i--;
  91             a[f] = a[i];
  92             a[i] = tmp;
  93             return i;
  94         }
  95 
  96         public static void HeapSort(T[] a)
  97         {
  98             for (int i = 1; i < a.Length; i++)
  99             {
 100                 int c = i;
 101                 int p = (c - 1) / 2;
 102                 while (c > 0 && a[p].CompareTo(a[c]) < 0)
 103                 {
 104                     T tmp = a[c];
 105                     a[c] = a[p];
 106                     a[p] = tmp;
 107                     c = p;
 108                     p = (c - 1) / 2;
 109                 }
 110             }
 111             for (int i = a.Length - 1; i > 0; i--)
 112             {
 113                 T tmp = a[0];
 114                 a[0] = a[i];
 115                 a[i] = tmp;
 116                 int p = 0;
 117                 int c = 2 * p + 1;
 118                 while (c < i)
 119                 {
 120                     if (c + 1 < i && a[c + 1].CompareTo(a[c]) > 0)
 121                         c++;
 122                     if (a[c].CompareTo(a[p]) <= 0)
 123                         break;
 124                     tmp = a[c];
 125                     a[c] = a[p];
 126                     a[p] = tmp;
 127                     p = c;
 128                     c = 2 * p + 1;
 129                 }
 130             }
 131         }
 132     }
 133 }

2015-09-23 06:32