Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- namespace GameWork.util {
- /**
- * @Author Alex
- */
- public class GWArraySort {
- //vars
- //constructor
- public GWArraySort() {
- }
- //public
- //use for nearly sorted arrays. Should not be used for reversed arrays
- public List<T> insertionSort<T>(List<T> list) where T : IComparable {
- T[] arr = list.ToArray();
- insertionSort<T>(arr);
- return new List<T>(arr);
- }
- public void insertionSort<T>(T[] arr) where T : IComparable {
- for (int i = 0; i < arr.Length; i++) {
- T temp = arr[i];
- int j = i - 1;
- while (j >= 0 && temp.CompareTo(arr[j]) < 0) {
- arr[j + 1] = arr[j];
- j--;
- }
- arr[j + 1] = temp;
- }
- }
- //should not be used for reversed arrays
- public List<T> selectionSort<T>(List<T> list) where T : IComparable {
- T[] arr = list.ToArray();
- selectionSort<T>(arr);
- return new List<T>(arr);
- }
- public void selectionSort<T>(T[] arr) where T : IComparable {
- int k;
- T temp;
- for (int i = 0; i < arr.Length; i++) {
- k = i;
- for (int j = i + 1; j < arr.Length; j++) {
- if (arr[j].CompareTo(arr[k]) < 0) {
- k = j;
- }
- }
- temp = arr[i];
- arr[i] = arr[k];
- arr[k] = temp;
- }
- }
- public List<T> selectionSort<T>(List<T> list) where T : IComparable {
- T[] arr = list.ToArray();
- bubbleSort<T>(arr);
- return new List<T>(arr);
- }
- public void bubbleSort<T>(T[] arr) where T : IComparable {
- bool changed;
- int length = arr.Length;
- do {
- changed = false;
- length--;
- for (int i = 0; i < length; i++) {
- if (arr[i].CompareTo(arr[i + 1]) > 0) {
- T temp = arr[i + 1];
- arr[i + 1] = arr[i];
- arr[i] = temp;
- changed = true;
- }
- }
- } while (changed);
- }
- //use for reversed arrays. should not be used for completely random/unsorted arrays with many unique values
- public List<T> shellSort<T>(List<T> list) where T : IComparable {
- T[] arr = list.ToArray();
- shellSort<T>(arr);
- return new List<T>(arr);
- }
- public void shellSort<T>(T[] arr) where T : IComparable {
- int n = arr.Length;
- 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};
- for (int l = incs.Length / incs[0]; l > 0;) {
- int m = incs[l--];
- for (int i = m; i < n; i++) {
- int j = i - m;
- if (arr[i].CompareTo(arr[j]) < 0) {
- T temp = arr[i];
- do {
- arr[j + m] = arr[j];
- j -= m;
- } while ((j >= 0) && (temp.CompareTo(arr[j]) < 0));
- arr[j + m] = temp;
- }
- }
- }
- }
- //experimental
- public List<T> mergeSort<T>(List<T> list) where T : IComparable {
- T[] arr = list.ToArray();
- mergeSort<T>(arr);
- return new List<T>(arr);
- }
- public void mergeSort<T>(T[] arr) where T : IComparable {
- T[] left;
- T[] right;
- if (arr.Length <= 1) {
- return;
- }
- left = new List<T>(arr).GetRange(0, arr.Length / 2).ToArray();
- right = new List<T>(arr).GetRange(left.Length, arr.Length - left.Length).ToArray();
- mergeSort(left);
- mergeSort(right);
- merge<T>(new List<T>(left), new List<T>(right)).CopyTo(arr);
- }
- //use for completely random/unsorted arrays with many unique values. Should not be used with nearly sorted arrays
- public List<T> heapSort<T>(List<T> list) where T : IComparable {
- T[] arr = list.ToArray();
- heapSort<T>(arr);
- return new List<T>(arr);
- }
- public void heapSort<T>(T[] arr) where T : IComparable {
- int heapSize = arr.Length;
- for (int p = (heapSize - 1) / 2; p >= 0; p--) {
- heapify<T>(arr, heapSize, p);
- }
- for (int i = arr.Length - 1; i > 0; i--) {
- T temp = arr[i];
- arr[i] = arr[0];
- arr[0] = temp;
- heapSize--;
- heapify<T>(arr, heapSize, 0);
- }
- }
- //use for arrays with very few unique values. Should not be used with completely random/unsorted arrays with many unique values
- public List<T> quick3Sort<T>(List<T> list) where T : IComparable {
- T[] arr = list.ToArray();
- quick3Sort<T>(arr);
- return new List<T>(arr);
- }
- public void quick3Sort<T>(T[] arr) where T : IComparable {
- internalQuick3Sort<T>(arr, 0, arr.Length);
- }
- //private
- private List<T> merge<T>(List<T> left, List<T> right) where T : IComparable {
- List<T> arr = new List<T>();
- while (left.Count > 0 && right.Count > 0) {
- if (left[0].CompareTo(right[0]) <= 0) {
- arr.Add(left[0]);
- left.RemoveAt(0);
- } else {
- arr.Add(arr[0]);
- right.RemoveAt(0);
- }
- }
- arr.AddRange(left);
- arr.AddRange(right);
- return arr;
- }
- private void heapify<T>(T[] arr, int heapSize, int index) where T : IComparable {
- int left = (index + 1) * 2 - 1;
- int right = (index + 1) * 2;
- int largest = 0;
- if (left < heapSize && arr[left].CompareTo(arr[index]) > 0) {
- largest = left;
- } else {
- largest = index;
- }
- if (right < heapSize && arr[right].CompareTo(arr[largest]) > 0) {
- largest = right;
- }
- if (largest != index) {
- T temp = arr[index];
- arr[index] = arr[largest];
- arr[largest] = temp;
- heapify<T>(arr, heapSize, largest);
- }
- }
- private void internalQuick3Sort<T>(T[] arr, int hi, int lo) where T : IComparable {
- int lt = lo;
- int gt = hi;
- int i = lo;
- T v;
- if (hi <= lo) {
- return;
- }
- v = arr[lo];
- while (i <= gt) {
- int cmp = arr[i].CompareTo(v);
- if (cmp < 0) {
- exch<T>(arr, lt++, i++);
- } else if (cmp > 0) {
- exch<T>(arr, i, gt--);
- } else {
- i++;
- }
- }
- internalQuick3Sort<T>(arr, lo, lt - 1);
- internalQuick3Sort<T>(arr, gt + 1, hi);
- }
- private void exch<T>(T[] arr, int i, int j) {
- T temp = arr[i];
- arr[i] = arr[j];
- arr[j] = temp;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement