Advertisement
Guest User

GWArraySort

a guest
Jul 17th, 2013
26
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 5.90 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace GameWork.util {
  5.  
  6.     /**
  7.      * @Author Alex
  8.      */
  9.  
  10.     public class GWArraySort {
  11.         //vars
  12.  
  13.         //constructor
  14.         public GWArraySort() {
  15.  
  16.         }
  17.  
  18.         //public
  19.  
  20.         //use for nearly sorted arrays. Should not be used for reversed arrays
  21.         public List<T> insertionSort<T>(List<T> list) where T : IComparable {
  22.             T[] arr = list.ToArray();
  23.             insertionSort<T>(arr);
  24.  
  25.             return new List<T>(arr);
  26.         }
  27.         public void insertionSort<T>(T[] arr) where T : IComparable {
  28.             for (int i = 0; i < arr.Length; i++) {
  29.                 T temp = arr[i];
  30.                 int j = i - 1;
  31.  
  32.                 while (j >= 0 && temp.CompareTo(arr[j]) < 0) {
  33.                     arr[j + 1] = arr[j];
  34.                     j--;
  35.                 }
  36.  
  37.                 arr[j + 1] = temp;
  38.             }
  39.         }
  40.  
  41.         //should not be used for reversed arrays
  42.         public List<T> selectionSort<T>(List<T> list) where T : IComparable {
  43.             T[] arr = list.ToArray();
  44.             selectionSort<T>(arr);
  45.  
  46.             return new List<T>(arr);
  47.         }
  48.         public void selectionSort<T>(T[] arr) where T : IComparable {
  49.             int k;
  50.             T temp;
  51.  
  52.             for (int i = 0; i < arr.Length; i++) {
  53.                 k = i;
  54.  
  55.                 for (int j = i + 1; j < arr.Length; j++) {
  56.                     if (arr[j].CompareTo(arr[k]) < 0) {
  57.                         k = j;
  58.                     }
  59.                 }
  60.  
  61.                 temp = arr[i];
  62.                 arr[i] = arr[k];
  63.                 arr[k] = temp;
  64.             }
  65.         }
  66.  
  67.         public List<T> selectionSort<T>(List<T> list) where T : IComparable {
  68.             T[] arr = list.ToArray();
  69.             bubbleSort<T>(arr);
  70.  
  71.             return new List<T>(arr);
  72.         }
  73.         public void bubbleSort<T>(T[] arr) where T : IComparable {
  74.             bool changed;
  75.             int length = arr.Length;
  76.  
  77.             do {
  78.                 changed = false;
  79.                 length--;
  80.  
  81.                 for (int i = 0; i < length; i++) {
  82.                     if (arr[i].CompareTo(arr[i + 1]) > 0) {
  83.                         T temp = arr[i + 1];
  84.  
  85.                         arr[i + 1] = arr[i];
  86.                         arr[i] = temp;
  87.  
  88.                         changed = true;
  89.                     }
  90.                 }
  91.             } while (changed);
  92.         }
  93.  
  94.         //use for reversed arrays. should not be used for completely random/unsorted arrays with many unique values
  95.         public List<T> shellSort<T>(List<T> list) where T : IComparable {
  96.             T[] arr = list.ToArray();
  97.             shellSort<T>(arr);
  98.  
  99.             return new List<T>(arr);
  100.         }
  101.         public void shellSort<T>(T[] arr) where T : IComparable {
  102.             int n = arr.Length;
  103.             int[] incs = {1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376, 3402672, 8382192, 21479367, 49095696, 114556624, 343669872, 52913488, 2085837936};
  104.  
  105.             for (int l = incs.Length / incs[0]; l > 0;) {
  106.                 int m = incs[l--];
  107.  
  108.                 for (int i = m; i < n; i++) {
  109.                     int j = i - m;
  110.  
  111.                     if (arr[i].CompareTo(arr[j]) < 0) {
  112.                         T temp = arr[i];
  113.  
  114.                         do {
  115.                             arr[j + m] = arr[j];
  116.                             j -= m;
  117.                         } while ((j >= 0) && (temp.CompareTo(arr[j]) < 0));
  118.  
  119.                         arr[j + m] = temp;
  120.                     }
  121.                 }
  122.             }
  123.         }
  124.  
  125.         //experimental
  126.         public List<T> mergeSort<T>(List<T> list) where T : IComparable {
  127.             T[] arr = list.ToArray();
  128.             mergeSort<T>(arr);
  129.  
  130.             return new List<T>(arr);
  131.         }
  132.         public void mergeSort<T>(T[] arr) where T : IComparable {
  133.             T[] left;
  134.             T[] right;
  135.  
  136.             if (arr.Length <= 1) {
  137.                 return;
  138.             }
  139.  
  140.             left = new List<T>(arr).GetRange(0, arr.Length / 2).ToArray();
  141.             right = new List<T>(arr).GetRange(left.Length, arr.Length - left.Length).ToArray();
  142.  
  143.             mergeSort(left);
  144.             mergeSort(right);
  145.             merge<T>(new List<T>(left), new List<T>(right)).CopyTo(arr);
  146.         }
  147.  
  148.         //use for completely random/unsorted arrays with many unique values. Should not be used with nearly sorted arrays
  149.         public List<T> heapSort<T>(List<T> list) where T : IComparable {
  150.             T[] arr = list.ToArray();
  151.             heapSort<T>(arr);
  152.  
  153.             return new List<T>(arr);
  154.         }
  155.         public void heapSort<T>(T[] arr) where T : IComparable {
  156.             int heapSize = arr.Length;
  157.  
  158.             for (int p = (heapSize - 1) / 2; p >= 0; p--) {
  159.                 heapify<T>(arr, heapSize, p);
  160.             }
  161.  
  162.             for (int i = arr.Length - 1; i > 0; i--) {
  163.                 T temp = arr[i];
  164.                 arr[i] = arr[0];
  165.                 arr[0] = temp;
  166.  
  167.                 heapSize--;
  168.                 heapify<T>(arr, heapSize, 0);
  169.             }
  170.         }
  171.  
  172.         //use for arrays with very few unique values. Should not be used with completely random/unsorted arrays with many unique values
  173.         public List<T> quick3Sort<T>(List<T> list) where T : IComparable {
  174.             T[] arr = list.ToArray();
  175.             quick3Sort<T>(arr);
  176.  
  177.             return new List<T>(arr);
  178.         }
  179.         public void quick3Sort<T>(T[] arr) where T : IComparable {
  180.             internalQuick3Sort<T>(arr, 0, arr.Length);
  181.         }
  182.  
  183.         //private
  184.         private List<T> merge<T>(List<T> left, List<T> right) where T : IComparable {
  185.             List<T> arr = new List<T>();
  186.  
  187.             while (left.Count > 0 && right.Count > 0) {
  188.                 if (left[0].CompareTo(right[0]) <= 0) {
  189.                     arr.Add(left[0]);
  190.                     left.RemoveAt(0);
  191.                 } else {
  192.                     arr.Add(arr[0]);
  193.                     right.RemoveAt(0);
  194.                 }
  195.             }
  196.  
  197.             arr.AddRange(left);
  198.             arr.AddRange(right);
  199.  
  200.             return arr;
  201.         }
  202.  
  203.         private void heapify<T>(T[] arr, int heapSize, int index) where T : IComparable {
  204.             int left = (index + 1) * 2 - 1;
  205.             int right = (index + 1) * 2;
  206.             int largest = 0;
  207.  
  208.             if (left < heapSize && arr[left].CompareTo(arr[index]) > 0) {
  209.                 largest = left;
  210.             } else {
  211.                 largest = index;
  212.             }
  213.  
  214.             if (right < heapSize && arr[right].CompareTo(arr[largest]) > 0) {
  215.                 largest = right;
  216.             }
  217.  
  218.             if (largest != index) {
  219.                 T temp = arr[index];
  220.  
  221.                 arr[index] = arr[largest];
  222.                 arr[largest] = temp;
  223.  
  224.                 heapify<T>(arr, heapSize, largest);
  225.             }
  226.         }
  227.  
  228.         private void internalQuick3Sort<T>(T[] arr, int hi, int lo) where T : IComparable {
  229.             int lt = lo;
  230.             int gt = hi;
  231.             int i = lo;
  232.             T v;
  233.  
  234.             if (hi <= lo) {
  235.                 return;
  236.             }
  237.  
  238.             v = arr[lo];
  239.  
  240.             while (i <= gt) {
  241.                 int cmp = arr[i].CompareTo(v);
  242.  
  243.                 if (cmp < 0) {
  244.                     exch<T>(arr, lt++, i++);
  245.                 } else if (cmp > 0) {
  246.                     exch<T>(arr, i, gt--);
  247.                 } else {
  248.                     i++;
  249.                 }
  250.             }
  251.  
  252.             internalQuick3Sort<T>(arr, lo, lt - 1);
  253.             internalQuick3Sort<T>(arr, gt + 1, hi);
  254.         }
  255.         private void exch<T>(T[] arr, int i, int j) {
  256.             T temp = arr[i];
  257.  
  258.             arr[i] = arr[j];
  259.             arr[j] = temp;
  260.         }
  261.     }
  262. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement