Last active
November 12, 2021 13:22
-
-
Save vivek781113/652057f9c9a4a6ff72f7bface2246cb4 to your computer and use it in GitHub Desktop.
CSharpGist
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class SortAlgorithm | |
| { | |
| /* | |
| * Below for loop is alog for build heap | |
| * FOR (N/2-1) TO 0 <= Range of internal nodes | |
| * HEAPIFIY(arr, i) | |
| */ | |
| public void BuildMaxHeap(int[] arr) | |
| { | |
| int len = arr.Length; | |
| for (int i = (len / 2 - 1); i >= 0; i--) | |
| MaxHeapify(arr, i, len - 1); | |
| } | |
| public int[] HeapSort(int[] nums) | |
| { | |
| //nums = BuildMaxHeap(nums); | |
| int heapsize = nums.Length - 1; | |
| for (int i = heapsize; i > 0; i--) | |
| { | |
| //Extract Max OR min by swapping the root element with leaf element | |
| (nums[0], nums[i]) = (nums[i], nums[0]); | |
| heapsize--; | |
| MaxHeapify(nums, 0, heapsize); | |
| } | |
| return nums; | |
| } | |
| private void MaxHeapify(int[] array, int parentIndex, int indexLimit) | |
| { | |
| int leftChildIndex = 2 * parentIndex + 1; | |
| int rightChildIndex = 2 * parentIndex + 2; | |
| int maxIndex = parentIndex; | |
| if (leftChildIndex <= indexLimit && array[leftChildIndex] > array[parentIndex]) | |
| { | |
| maxIndex = leftChildIndex; | |
| } | |
| if (rightChildIndex <= indexLimit && array[rightChildIndex] > array[maxIndex]) | |
| { | |
| maxIndex = rightChildIndex; | |
| } | |
| if (maxIndex != parentIndex) | |
| { | |
| (array[parentIndex], array[maxIndex]) = (array[maxIndex], array[parentIndex]); | |
| MaxHeapify(array, maxIndex, indexLimit); | |
| } | |
| } | |
| public int[] MergeSort(int[] nums) | |
| { | |
| int size = nums.Length; | |
| if (size < 2) | |
| return nums; | |
| int mid = size / 2; | |
| int[] leftHalf = new int[mid]; | |
| int[] rightHalf = new int[size - mid]; | |
| for (int i = 0; i < mid; i++) | |
| { | |
| leftHalf[i] = nums[i]; | |
| } | |
| for (int i = mid; i < size; i++) | |
| { | |
| rightHalf[i-mid] = nums[i]; | |
| } | |
| MergeSort(leftHalf); | |
| MergeSort(rightHalf); | |
| Merge(nums, leftHalf, rightHalf, mid, size - mid); | |
| return nums; | |
| } | |
| private void Merge(int[] arr, int[] leftHalf, int[] rightHalf, int leftBoundary, int rightBoundary) | |
| { | |
| int leftIndex = 0; | |
| int rightIndex = 0; | |
| int arrayIndex = 0; | |
| while (leftIndex < leftBoundary && rightIndex < rightBoundary) | |
| { | |
| if (leftHalf[leftIndex] < rightHalf[rightIndex]) | |
| { | |
| arr[arrayIndex] = leftHalf[leftIndex]; | |
| leftIndex++; | |
| } | |
| else | |
| { | |
| arr[arrayIndex] = rightHalf[rightIndex]; | |
| rightIndex++; | |
| } | |
| arrayIndex++; | |
| } | |
| while (leftIndex < leftBoundary) | |
| { | |
| arr[arrayIndex] = leftHalf[leftIndex]; | |
| arrayIndex++; | |
| leftIndex++; | |
| } | |
| while (rightIndex < rightBoundary) | |
| { | |
| arr[arrayIndex] = rightHalf[rightIndex]; | |
| arrayIndex++; | |
| rightIndex++; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment