Guest User

Untitled

a guest
Sep 17th, 2019
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class Sort<T>
  2. where T : IComparable<T>
  3. {
  4. public static void BubbleSort(T[] arr)
  5. {
  6. int arrCount = arr.Length;
  7. for (int i = 0; i < arrCount; i++)
  8. {
  9. int count = 0;
  10. for (int j = 0; j < arrCount - 1; j++)
  11. {
  12. if (arr[j].CompareTo(arr[j + 1]) == 1)
  13. {
  14. swap(arr, j, j + 1);
  15. count++;
  16. }
  17. }
  18. if (count == 0)
  19. break;
  20. }
  21. }
  22. public static void InsertionSort(T[] arr)
  23. {
  24. int arrCount = arr.Length;
  25. for (int i = 0; i < arrCount - 1; i++)
  26. {
  27. for (int j = i + 1; j > 0; j--)
  28. {
  29. if (arr[j - 1].CompareTo(arr[j]) == 1)
  30. swap(arr, j, j - 1);
  31. }
  32. }
  33. }
  34. public static void SelectionSort(T[] arr)
  35. {
  36. int smallestIndex;
  37. int count = arr.Length;
  38. for (int i = 0; i < count - 1; i++)
  39. {
  40. smallestIndex = i;
  41.  
  42. for (int index = i + 1; index < count; index++)
  43. {
  44. if (arr[index].CompareTo(arr[smallestIndex]) == -1)
  45. smallestIndex = index;
  46. }
  47. swap(arr, i, smallestIndex);
  48. }
  49. }
  50. public static void QuickSort(T[] arr)=> quickSort(arr, 0, arr.Length - 1);
  51. public static void MarginSort(T[] arr) => mergeSort(arr, 0, arr.Length-1);
  52. public static void BuckedSort(int[] arr)
  53. {
  54. int max = int.MinValue;
  55. for (int i = 0; i < arr.Length; i++)
  56. {
  57. if (arr[i].CompareTo(max) == 1)
  58. max = arr[i];
  59. }
  60. int[] ar = new int[max + 1];
  61. for (int i = 0; i < arr.Length; i++)
  62. {
  63. ar[arr[i]]++;
  64. }
  65. int index = 0;
  66. int counter = 0;
  67. for (int i = 0; i < ar.Length; i++)
  68. {
  69. int count = ar[index++];
  70. while (count > 0)
  71. {
  72. arr[counter++] = i;
  73. count--;
  74. }
  75. }
  76. }
  77.  
  78. #region private Functionality
  79. private static void swap(T[] arr, int firstIndex, int secondIndex)
  80. {
  81. T temp = arr[firstIndex];
  82. arr[firstIndex] = arr[secondIndex];
  83. arr[secondIndex] = temp;
  84. }
  85. private static void swap(int[] array, int firstIndex, int secondIndex)
  86. {
  87. int temp = array[firstIndex];
  88. array[firstIndex] = array[secondIndex];
  89. array[secondIndex] = temp;
  90. }
  91. private static int partition(T[] array, int left, int right, T pivot)
  92. {
  93. while (left <= right)
  94. {
  95. while (array[left].CompareTo(pivot) == - 1)
  96. {
  97. left++;
  98. }
  99. while (array[right].CompareTo(pivot) == 1)
  100. {
  101. right--;
  102. }
  103. if (left <= right)
  104. {
  105. swap(array, left, right);
  106. left++;
  107. right--;
  108. }
  109. }
  110. return left;
  111. }
  112. private static void quickSort(T[] array, int left, int right)
  113. {
  114. if (left >= right)
  115. return;
  116. T pivot = array[(left + right) / 2];
  117. int index = partition(array, left, right, pivot);
  118. quickSort(array, left, index - 1);
  119. quickSort(array, index, right);
  120. }
  121. private static void merge(T[] arr, int left, int middle, int right)
  122. {
  123. T[] leftArray = new T[middle - left + 1];
  124. T[] rightArray = new T[right - middle];
  125.  
  126. Array.Copy(arr, left, leftArray, 0, middle - left + 1);
  127. Array.Copy(arr, middle + 1, rightArray, 0, right - middle);
  128.  
  129. int i = 0;
  130. int j = 0;
  131. for (int k = left; k < right + 1; k++)
  132. {
  133. if (i == leftArray.Length)
  134. arr[k] = rightArray[j++];
  135. else if (j == rightArray.Length)
  136. arr[k] = leftArray[i++];
  137. else if (leftArray[i].CompareTo(rightArray[j]) < 1)
  138. arr[k] = leftArray[i++];
  139. else
  140. arr[k] = rightArray[j++];
  141. }
  142. }
  143. private static void mergeSort(T[] input, int left, int right)
  144. {
  145. if (left < right)
  146. {
  147. int middle = (left + right) / 2;
  148. mergeSort(input, left, middle);
  149. mergeSort(input, middle + 1, right);
  150. merge(input, left, middle, right);
  151. }
  152. }
  153. #endregion
  154. }
RAW Paste Data