Created
May 26, 2023 18:39
-
-
Save aamahi/a10c329a55e996445535e219988e97c6 to your computer and use it in GitHub Desktop.
Rubayat Assignment
This file contains 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
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <ctime> | |
void bubbleSort(std::vector<int>& arr) { | |
int n = arr.size(); | |
for (int i = 0; i < n - 1; ++i) { | |
for (int j = 0; j < n - i - 1; ++j) { | |
if (arr[j] > arr[j + 1]) { | |
std::swap(arr[j], arr[j + 1]); | |
} | |
} | |
} | |
} | |
void merge(std::vector<int>& arr, int left, int mid, int right) { | |
int n1 = mid - left + 1; | |
int n2 = right - mid; | |
std::vector<int> L(n1), R(n2); | |
for (int i = 0; i < n1; ++i) { | |
L[i] = arr[left + i]; | |
} | |
for (int j = 0; j < n2; ++j) { | |
R[j] = arr[mid + 1 + j]; | |
} | |
int i = 0, j = 0, k = left; | |
while (i < n1 && j < n2) { | |
if (L[i] <= R[j]) { | |
arr[k] = L[i]; | |
++i; | |
} | |
else { | |
arr[k] = R[j]; | |
++j; | |
} | |
++k; | |
} | |
while (i < n1) { | |
arr[k] = L[i]; | |
++i; | |
++k; | |
} | |
while (j < n2) { | |
arr[k] = R[j]; | |
++j; | |
++k; | |
} | |
} | |
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); | |
} | |
} | |
void heapify(std::vector<int>& arr, int n, int i) { | |
int largest = i; | |
int left = 2 * i + 1; | |
int right = 2 * i + 2; | |
if (left < n && arr[left] > arr[largest]) { | |
largest = left; | |
} | |
if (right < n && arr[right] > arr[largest]) { | |
largest = right; | |
} | |
if (largest != i) { | |
std::swap(arr[i], arr[largest]); | |
heapify(arr, n, largest); | |
} | |
} | |
void heapSort(std::vector<int>& arr) { | |
int n = arr.size(); | |
for (int i = n / 2 - 1; i >= 0; --i) { | |
heapify(arr, n, i); | |
} | |
for (int i = n - 1; i >= 0; --i) { | |
std::swap(arr[0], arr[i]); | |
heapify(arr, i, 0); | |
} | |
} | |
void selectionSort(std::vector<int>& arr) { | |
int n = arr.size(); | |
for (int i = 0; i < n - 1; ++i) { | |
int minIndex = i; | |
for (int j = i + 1; j < n; ++j) { | |
if (arr[j] < arr[minIndex]) { | |
minIndex = j; | |
} | |
} | |
std::swap(arr[i], arr[minIndex]); | |
} | |
} | |
int partition(std::vector<int>& arr, int low, int high) { | |
int pivot = arr[high]; | |
int i = low - 1; | |
for (int j = low; j <= high - 1; ++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); | |
} | |
} | |
void printExecutionTime(const std::string& algorithm, clock_t start, clock_t end) { | |
double duration = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0; | |
std::cout << algorithm << ": " << duration << " ms" << std::endl; | |
} | |
int main() { | |
// Create an array | |
std::vector<int> arr = { 5, 2, 9, 1, 3 }; | |
// Quick Sort | |
clock_t start = clock(); | |
quickSort(arr, 0, arr.size() - 1); | |
clock_t end = clock(); | |
printExecutionTime("Quick Sort", start, end); | |
// Selection Sort | |
start = clock(); | |
selectionSort(arr); | |
end = clock(); | |
printExecutionTime("Selection Sort", start, end); | |
// Heap Sort | |
start = clock(); | |
heapSort(arr); | |
end = clock(); | |
printExecutionTime("Heap Sort", start, end); | |
// Bubble Sort | |
start = clock(); | |
bubbleSort(arr); | |
end = clock(); | |
printExecutionTime("Bubble Sort", start, end); | |
// Merge Sort | |
start = clock(); | |
mergeSort(arr, 0, arr.size() - 1); | |
end = clock(); | |
printExecutionTime("Merge Sort", start, end); | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment