[WikiDyd] [TitleIndex] [WordIndex

Sortowanie wektorów C#

Prosty przykładzik w C# pokazujący implementację różnych algorytmów sortowania. Nieco zmodyfikowana wersja programów z laboratorium.

Definicja wzorca f. porównującej dwie liczby całkowite.

   1 namespace SortDemo 
   2 {
   3     public delegate int INT_CMP_FUNCTION( int i1, int i2 );
   4 }

Klasa Wektor - wektor liczb całkowitych z konstruktorem, operacjami get i set, operatorem[], metodą swap oraz metodą wypisującą wektor na konsolę.

   1 using System;
   2 
   3 namespace SortDemo 
   4 {
   5     /// <summary>
   6     /// Tested class: a vector of integers.
   7     /// </summary>
   8     /// <param name="n">The n.</param>
   9     class Wektor
  10     {
  11         private int[] v;
  12         public int Length = 0;
  13 
  14         /// <summary>
  15         /// Initializes a new instance of the <see cref="Wektor"/> class.
  16         /// </summary>
  17         /// <param name="n">The length of the vector.</param>
  18         public Wektor(int n)
  19         {
  20             v = new int[n];
  21             for (int i = 0; i < v.Length; i++)
  22                 v[i] = 0;
  23             Length = v.Length;
  24         }
  25 
  26         /// <summary>
  27         /// Sets the specified v[i]= value.
  28         /// </summary>
  29         /// <param name="i">The index.</param>
  30         /// <param name="value">The new value of v[i].</param>
  31         public void set(int i, int value)
  32         {
  33             v[i] = value;
  34         }
  35 
  36         /// <summary>
  37         /// Gets the specified v[i].
  38         /// </summary>
  39         /// <param name="i">The index.</param>
  40         /// <returns></returns>
  41         public int get(int i)
  42         {
  43             return v[i];
  44         }
  45 
  46         /// <summary>
  47         /// Swaps i-th and j-th elements.
  48         /// </summary>
  49         /// <param name="i">First index.</param>
  50         /// <param name="j">Second index.</param>
  51         public void swap(int i, int j)
  52         {
  53             int tmp = v[i];
  54             v[i] = v[j];
  55             v[j] = tmp;
  56         }
  57 
  58         /// <summary>
  59         /// [] operator.
  60         /// </summary>
  61         public int this [ int i ]
  62         {
  63             get { return v[i]; }
  64             set { v[i] = value; }
  65         }
  66 
  67         /// <summary>
  68         /// Prints this to Console.
  69         /// </summary>
  70         public void outToConsole()
  71         {
  72             System.Console.Write("[ ");
  73             for (int i = 0; i < v.Length; i++)
  74                 System.Console.Write("{0} ", v[i]);
  75             System.Console.WriteLine("]");
  76         }
  77     }
  78 }

Kontener metod sortujących: udostępnia sortujące Wektor funkcje inSort (sortowanie przez wstawianie) i qSort (sortowanie szybkie)

   1 using System;
   2 
   3 namespace SortDemo 
   4 {
   5     class WektorUtils
   6     {
   7         /// <summary>
   8         /// Sorts with the insertion sort algorithm
   9         /// </summary>
  10         /// <param name="w">The Wektor to be sorted.</param>
  11         /// <param name="cmp_func">Comparing function.</param>
  12         public static void inSort(Wektor w, INT_CMP_FUNCTION cmp_func)
  13         {
  14             for (int i = 1; i < w.Length; i++)
  15             {
  16                 int tmp = w[i];
  17                 int j;
  18                 for (j = i; j > 0 && cmp_func( w[j-1], tmp) > 0; j--)
  19                     w[j] = w[j - 1];
  20                 w[j] = tmp;
  21             }
  22         }
  23 
  24         /// <summary>
  25         /// Sorts with the quick sort algorithm
  26         /// </summary>
  27         /// <param name="w">The Wektor to be sorted.</param>
  28         /// <param name="cmp_func">Comparing function.</param>
  29         public static void qSort(Wektor w, INT_CMP_FUNCTION cmp_func)
  30         {
  31             rec_qsort(w, 0, w.Length - 1, cmp_func);
  32         }
  33 
  34         // Recursive qsort algorithm (wrapped by qSort) - private method.
  35         private static void rec_qsort(Wektor w, int p, int k, INT_CMP_FUNCTION cmp_func)
  36         {
  37             if (p < k)
  38             {
  39                 int m = divide(w, p, k, cmp_func);
  40                 rec_qsort(w, p, m - 1, cmp_func);
  41                 rec_qsort(w, m + 1, k, cmp_func);
  42             }
  43         }
  44 
  45         // Help function for qsort algorithm: divides elements with respect to selected one
  46         private static int divide(Wektor w, int p, int k, INT_CMP_FUNCTION cmp_func)
  47         {
  48             int ridx= (new Random()).Next(p, k);  // random element from w[p..k]
  49             w.swap(p,ridx); // swap w[p] <-> w[ridx]
  50             int tmp= w[p]; // set dividing element
  51             // divide:
  52             int i= p;
  53             int j= k;
  54             do
  55             {
  56                 while (i < j && cmp_func(w[i], tmp) <= 0)
  57                     i++; // skip elements <= tmp
  58                 while (i < j && cmp_func(w[j], tmp) > 0)
  59                     j--; // skip element > tmp
  60                 if (i < j)
  61                     w.swap(i, j);
  62             } while (i < j);
  63             if (cmp_func(w[i], tmp) > 0) // patch when w[p] is the biggest one
  64                 i--;
  65             w.swap(p, i);
  66             return i;
  67         }
  68     }
  69 }

Program testujący.

   1 using System;
   2 
   3 namespace SortDemo 
   4 {
   5     /// <summary>
   6     /// Testing class. Checks all methods of the Wektor class
   7     /// </summary>
   8     class Program
   9     {
  10         // Comparing funct. for sort in increasing order
  11         public static int cmp_func_4_incr(int i1, int i2)
  12         {
  13             return i1 - i2;
  14         }
  15 
  16         // Comparing funct. for sort in decreasing order
  17         public static int cmp_func_4_decr(int i1, int i2)
  18         {
  19             return i2 - i1;
  20         }
  21 
  22         static void Main(string[] args)
  23         {
  24             int n = int.Parse(args[0]);
  25             Wektor w = new Wektor(n);
  26             w.outToConsole();
  27             Random r = new Random();
  28             for (int i = 0; i < w.Length; i++)
  29                 w.set(i, r.Next(0, 100));  // alternatywnie: w[i] = r.Next(0,100);
  30             w.outToConsole();
  31             System.Console.WriteLine("v[{0}]= {1}", n / 2, w.get( n/2 ));
  32             WektorUtils.inSort(w,cmp_func_4_incr);
  33             w.outToConsole();
  34             WektorUtils.inSort(w,cmp_func_4_decr);
  35             w.outToConsole();
  36             WektorUtils.qsort(w, new INT_CMP_FUNCTION(cmp_func_4_incr));
  37             w.outToConsole();
  38             WektorUtils.qsort(w, new INT_CMP_FUNCTION(cmp_func_4_decr));
  39             w.outToConsole();
  40         }
  41 
  42 
  43     }
  44 }

2015-09-23 06:32