|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 |
#include <iostream> #include <vector> // Bubble Sort void bubbleSort(std::vector<int>& arr) { size_t n = arr.size(); for (size_t i = 0; i < n - 1; ++i) { for (size_t j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } } // Selection Sort void selectionSort(std::vector<int>& arr) { size_t n = arr.size(); for (size_t i = 0; i < n - 1; ++i) { size_t minIdx = i; for (size_t j = i + 1; j < n; ++j) { if (arr[j] < arr[minIdx]) { minIdx = j; } } std::swap(arr[i], arr[minIdx]); } } // Insertion Sort void insertionSort(std::vector<int>& arr) { size_t n = arr.size(); for (size_t i = 1; i < n; ++i) { int key = arr[i]; size_t j = i; while (j > 0 && arr[j - 1] > key) { arr[j] = arr[j - 1]; --j; } arr[j] = key; } } // Merge Sort Helper Function void merge(std::vector<int>& arr, int left, int mid, int right) { std::vector<int> temp(right - left + 1); int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (i = left; i <= right; ++i) { arr[i] = temp[i - left]; } } void mergeSort(std::vector<int>& arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } // Quick Sort Helper Function int partition(std::vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; ++j) { if (arr[j] < pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(std::vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } // Function to print an array void printArray(const std::vector<int>& arr) { for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; } int main() { std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90}; std::vector<int> arrCopy = arr; std::cout << "Original array: "; printArray(arr); std::cout << "Bubble Sort: "; bubbleSort(arr); printArray(arr); arr = arrCopy; std::cout << "Selection Sort: "; selectionSort(arr); printArray(arr); arr = arrCopy; std::cout << "Insertion Sort: "; insertionSort(arr); printArray(arr); arr = arrCopy; std::cout << "Merge Sort: "; mergeSort(arr, 0, arr.size() - 1); printArray(arr); arr = arrCopy; std::cout << "Quick Sort: "; quickSort(arr, 0, arr.size() - 1); printArray(arr); return 0; } |
Explanation
- Bubble Sort:
- Repeatedly compares adjacent elements and swaps them if they are in the wrong order.
- Continues until no more swaps are needed.
- Selection Sort:
- Finds the minimum element from the unsorted portion and swaps it with the first unsorted element.
- Repeats this process for all elements.
- Insertion Sort:
- Builds the final sorted array one item at a time.
- Takes each element and inserts it into its correct position among the previously sorted elements.
- Merge Sort:
- Divides the array into two halves, recursively sorts them, and then merges the sorted halves.
- Uses a helper function to merge two sorted subarrays.
- Quick Sort:
- Selects a pivot element and partitions the array into elements less than the pivot and elements greater than the pivot.
- Recursively applies the same process to the subarrays.
- Utility Functions:
printArray(): Prints the elements of the array.main(): Tests each sorting algorithm on a copy of the same array to show their results.