starbeamrainbowlabs

Insertion sorter

Jan 8th, 2015
202
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2.  
  3. /*
  4.  * Insertion sorter
  5.  **************************
  6.  * Built by Starbeamrainbowlabs <https://starbeamrainbowlabs.com>
  7.  * Binary available at https://starbeamrainbowlabs.com/binaries/reverseinsertion.exe
  8.  *
  9.  */
  10.  
  11. public class InsertionSort
  12. {
  13.     /// <summary>
  14.     /// Swaps the values in an array of ints at the posistions a and b.
  15.     /// </summary>
  16.     /// <param name="array">A reference to the array to operate on.</param>
  17.     /// <param name="a">The index of the first value.</param>
  18.     /// <param name="b">The index of the second value.</param>
  19.     static void swap_places(ref int[] array, int a, int b)
  20.     {
  21.         int temp = array[a];
  22.         array[a] = array[b];
  23.         array[b] = temp;
  24.     }
  25.  
  26.     /// <summary>
  27.     /// Generates a array of ints to a given size.
  28.     /// </summary>
  29.     /// <param name="size">The size of the array to generate</param>
  30.     /// <param name="min">The minimum number that should appear in the array.</param>
  31.     /// <param name="max">The maxmimum number that should appear in the array.</param>
  32.     /// <returns>An array of random ints that is `size` in length.</returns>
  33.     static int[] generate_array(int size, int min = 0, int max = 25)
  34.     {
  35.         if (min >= max)
  36.             throw new Exception("The min was bigger than max.");
  37.  
  38.         int[] newarray = new int[size];
  39.         Random generator = new Random();
  40.  
  41.         for (int i = size - 1; i >= 0; i--)
  42.         {
  43.             newarray[i] = generator.Next(min, max);
  44.         }
  45.  
  46.         return newarray;
  47.     }
  48.  
  49.     /// <summary>
  50.     /// Prints an array of ints to the console.
  51.     /// </summary>
  52.     /// <param name="array">The array to print.</param>
  53.     static void print_array(ref int[] array, bool new_line = true)
  54.     {
  55.         Console.Write("[ {0} ]", String.Join(", ", array));
  56.         if (new_line)
  57.             Console.WriteLine();
  58.     }
  59.  
  60.     /// <summary>
  61.     /// Performs an insertion sort in the array.
  62.     /// </summary>
  63.     /// <param name="array">A reference to the array to sort.</param>
  64.     static void insertion_sort(ref int[] array)
  65.     {
  66.         /*
  67.          *           v
  68.          * [1, 4, 2, 5, 3]
  69.          *             ¦
  70.          *
  71.          *        v
  72.          * [1, 4, 2, 3, 5]
  73.          *          ¦
  74.          *
  75.          *     v
  76.          * [1, 4, 2, 3, 5]
  77.          *       ¦
  78.          *****************************
  79.          *  0, 1, 2, 3, 4
  80.          *  v
  81.          * [1, 2, 3, 4, 5]
  82.          *    ¦
  83.          *
  84.          * length: 5
  85.          */
  86.         for (int i = array.Length - 2; i >= 0; i--)
  87.         {
  88.             int shp = i;
  89.             //                                                      |
  90.             //make sure that we don't fall off the end of the array V
  91.             while(shp < array.Length - 1 && array[shp] > array[shp + 1])
  92.             {
  93.                 swap_places(ref array, shp, shp + 1);
  94.                 shp++;
  95.             }
  96.  
  97.             Console.Write("i: {0} ", i);
  98.             print_array(ref array);
  99.         }
  100.     }
  101.  
  102.     static void Main()
  103.     {
  104.         int[] array = generate_array(25, 0, 99);
  105.  
  106.         print_array(ref array);
  107.  
  108.         insertion_sort(ref array);
  109.     }
  110. }
RAW Paste Data