jeff082chen · April 6, 2022 04:26 · Apr 6, 2022
diff --git a/sort.hpp b/sort.hpp
@@ -0,0 +1,118 @@
+#include <vector>
+
+void mergeSort(std::vector<int>& array);
+void mergeSortHelper(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t endIdx);
+void doMerge(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t middleIdx, size_t endIdx);
+
+void quickSort(std::vector<int>& array);
+void quickSortHelper(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx);
+std::vector<int>::iterator paritition(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx);
+
+void heapSort(std::vector<int>& array);
+void heapify(std::vector<int>& array);
+void siftDown(std::vector<int>& heap, int currentIdx, int endIdx);
+
+
+
+
+
+void mergeSort(std::vector<int>& array) {
+    if(array.size() <= 1) {
+        return;
+    }
+    std::vector<int> auxiliaryArray = array;
+    mergeSortHelper(array, auxiliaryArray, 0, array.size() - 1);
+}
+
+void mergeSortHelper(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t endIdx) {
+    if(startIdx == endIdx) {
+        return;
+    }
+    size_t middleIdx = (startIdx + endIdx) / 2;
+    mergeSortHelper(auxiliaryArray, mainArray, startIdx, middleIdx);
+    mergeSortHelper(auxiliaryArray, mainArray, middleIdx + 1, endIdx);
+    doMerge(mainArray, auxiliaryArray, startIdx, middleIdx, endIdx);
+}
+
+void doMerge(std::vector<int>& mainArray, std::vector<int>& auxiliaryArray, size_t startIdx, size_t middleIdx, size_t endIdx) {
+    size_t k = startIdx, i = startIdx, j = middleIdx + 1;
+
+    while(i <= middleIdx && j <= endIdx) 
+        if(auxiliaryArray[i] <= auxiliaryArray[j])
+            mainArray[k++] = auxiliaryArray[i++];
+        else
+            mainArray[k++] = auxiliaryArray[j++];
+
+    while(i <= middleIdx)
+        mainArray[k++] = auxiliaryArray[i++];
+
+    while(j <= endIdx)
+        mainArray[k++] = auxiliaryArray[j++];
+}
+
+void quickSort(std::vector<int>& array) {
+    quickSortHelper(array, array.begin(), array.end() - 1);
+}
+
+void quickSortHelper(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx) {
+    if(startIdx >= endIdx) {
+        return;
+    }
+    auto pivotIdx = paritition(array, startIdx, endIdx);
+    bool leftSubarrayIsSmaller = (pivotIdx - startIdx) < (endIdx - pivotIdx);
+    if(leftSubarrayIsSmaller) {
+        quickSortHelper(array, startIdx, pivotIdx - 1);
+        quickSortHelper(array, pivotIdx + 1, endIdx);
+    }
+    else {
+        quickSortHelper(array, pivotIdx + 1, endIdx);
+        quickSortHelper(array, startIdx, pivotIdx - 1);
+    }
+}
+
+std::vector<int>::iterator paritition(std::vector<int>& array, std::vector<int>::iterator startIdx, std::vector<int>::iterator endIdx) {
+    int pivot = *startIdx;
+    auto leftIdx = startIdx;
+    auto rightIdx = endIdx;
+    while(leftIdx < rightIdx) {
+        while(leftIdx < rightIdx && *rightIdx >= pivot) --rightIdx;
+        *leftIdx = *rightIdx;
+        while(leftIdx < rightIdx && *leftIdx <= pivot) ++leftIdx;
+        *rightIdx = *leftIdx;
+    }
+    *leftIdx = pivot;
+    return leftIdx;
+}
+
+void heapSort(std::vector<int>& array) {
+    int endIdx;
+    heapify(array);
+    for(endIdx = (int)array.size() - 1; endIdx > 0; --endIdx) {
+        std::swap(array[0], array[endIdx]);
+        siftDown(array, 0, endIdx - 1);
+    }
+}
+
+void heapify(std::vector<int>& array) {
+    int firstParentIdx = (int)(array.size() - 2) / 2, currentIdx;
+    for(currentIdx = firstParentIdx; currentIdx >= 0; --currentIdx) {
+        siftDown(array, currentIdx, (int)array.size() - 1);
+    }
+}
+
+void siftDown(std::vector<int>& heap, int currentIdx, int endIdx) {
+    int childOneIdx = currentIdx * 2 + 1, childTwoIdx, idxToSwap;
+    while(childOneIdx <= endIdx) {
+        childTwoIdx = (currentIdx * 2 + 2) <= endIdx ? (currentIdx * 2 + 2) : -1;
+        idxToSwap = childOneIdx;
+
+        if(childTwoIdx != -1 && heap[childTwoIdx] > heap[childOneIdx])
+            idxToSwap = childTwoIdx;
+
+        if(heap[idxToSwap] <= heap[currentIdx]) return;
+
+        std::swap(heap[idxToSwap], heap[currentIdx]);
+        currentIdx = idxToSwap;
+        childOneIdx = currentIdx * 2 + 1;
+    }
+}