starbeamrainbowlabs

Reverse Selection Sort

Jan 7th, 2015
259
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2.  
  3. /*
  4.  * Reverse Selection Sort
  5.  ***************************************
  6.  * By Starbeamrainbowlabs <https://starbeamrinbowlabs.com>
  7.  *
  8.  * Posted at https://starbeamrainbowlabs.com/blog/article.php?posts%2F039-Selection-Sort.html
  9.  * A binary can be found at https://starbeamrainbowlabs.com/binaries/reverseselection.exe
  10.  */
  11. public class SelectionSort
  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.             newarray[i] = generator.Next(min, max);
  43.         }
  44.  
  45.         return newarray;
  46.     }
  47.  
  48.     /// <summary>
  49.     /// Performs a selection sort on an array of ints.
  50.     /// </summary>
  51.     /// <param name="array">The array to sort.</param>
  52.     static void selection_sort(ref int[] array)
  53.     {
  54.         /*
  55.          * pass #0
  56.          *  0 1 2 3 4
  57.          * [3,1,5,3,2]
  58.          *  |---*-|
  59.          *          ^ limit
  60.          *
  61.          * pass #1
  62.          *  0 1 2 3 4
  63.          * [3,1,2,3,5]
  64.          *  *---^
  65.          *        ^ limit
  66.          *
  67.          * pass #2
  68.          *  0 1 2 3 4
  69.          * [3,1,2,3,5]
  70.          *  *-^
  71.          *      ^ limit
  72.          *  
  73.          * pass #3
  74.          *  0 1 2 3 4
  75.          * [2,1,3,3,5]
  76.          *  *
  77.          *    ^ limit
  78.          *
  79.          * * done *
  80.          * [1,2,3,3,5]
  81.          */
  82.         int limit = array.Length - 1;
  83.         while(limit > 0)
  84.         {
  85.             //find the index with the maximum value
  86.             int max_index = 0; //set the max to the first element in the array
  87.             //don't search the first element in the array, we have already done that on the line above
  88.             for(int i = limit - 1; i > 0; i--)
  89.             {
  90.                 if(array[i] > array[max_index])
  91.                     max_index = i;
  92.             }
  93.             if(array[max_index] > array[limit])
  94.             {
  95.                 //we have found an index with a high value than the current limit
  96.                 swap_places(ref array, max_index, limit);
  97.             }
  98.  
  99.             Console.Write("limit: {0} ", limit);
  100.             print_array(ref array);
  101.  
  102.             limit--;
  103.         }
  104.     }
  105.  
  106.     /// <summary>
  107.     /// Prints an array of ints to the console.
  108.     /// </summary>
  109.     /// <param name="array">The array to print.</param>
  110.     static void print_array(ref int[] array, bool new_line = true)
  111.     {
  112.         Console.Write("[ {0} ]", String.Join(", ", array));
  113.         if(new_line)
  114.             Console.WriteLine();
  115.     }
  116.  
  117.  
  118.     static void Main()
  119.     {
  120.         int[] array = generate_array(25);
  121.  
  122.         print_array(ref array);
  123.  
  124.         selection_sort(ref array);
  125.     }
  126. }
RAW Paste Data