Assignment one:merge sort
Sanskriti Debnath:06301032023
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
using namespace std;
void merge(vector<int>& arr, int si, int mid, int ei, vector<int>& temp) {
int i = si, j = mid + 1, k = si;
while (i <= mid && j <= ei) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= ei) {
temp[k++] = arr[j++];
}
for (i = si; i <= ei; i++) {
arr[i] = temp[i];
}
}
void mergeSort(vector<int>& arr, int si, int ei, vector<int>& temp) {
if (si >= ei) return;
int mid = si + (ei - si) / 2;
mergeSort(arr, si, mid, temp);
mergeSort(arr, mid + 1, ei, temp);
merge(arr, si, mid, ei, temp);
}
int main() {
vector<int> sizes = {1000, 4000, 8000, 16000, 32000, 64000};
for (int size : sizes) {
vector<int> arr(size), temp(size);
for (int i = 0; i < size; i++) arr[i] = i;
auto startTime = chrono::high_resolution_clock::now();
mergeSort(arr, 0, arr.size() - 1, temp);
auto endTime = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
cout << "Sorted Array - Size: " << size << ", Time: " << duration << " ms" << endl;
for (int i = 0; i < size; i++) arr[i] = size - i;
startTime = chrono::high_resolution_clock::now();
mergeSort(arr, 0, arr.size() - 1, temp);
endTime = chrono::high_resolution_clock::now();
duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
cout << "Reverse Sorted Array - Size: " << size << ", Time: " << duration << " ms" << endl;
for (int i = 0; i < size; i++) arr[i] = rand() % size;
startTime = chrono::high_resolution_clock::now();
mergeSort(arr, 0, arr.size() - 1, temp);
endTime = chrono::high_resolution_clock::now();
duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
cout << "Random Array - Size: " << size << ", Time: " << duration << " ms" << endl;
cout << "--------------------------------------------" << endl;
}
return ;
output:
Sorted Array - Size: 1000, Time: 0 ms
Reverse Sorted Array - Size: 1000, Time: 0 ms
Random Array - Size: 1000, Time: 0 ms
--------------------------------------------
Sorted Array - Size: 4000, Time: 1 ms
Reverse Sorted Array - Size: 4000, Time: 1 ms
Random Array - Size: 4000, Time: 2 ms
--------------------------------------------
Sorted Array - Size: 8000, Time: 3 ms
Reverse Sorted Array - Size: 8000, Time: 3 ms
Random Array - Size: 8000, Time: 5 ms
--------------------------------------------
Sorted Array - Size: 16000, Time: 2 ms
Reverse Sorted Array - Size: 16000, Time: 2 ms
Random Array - Size: 16000, Time: 4 ms
--------------------------------------------
Sorted Array - Size: 32000, Time: 8 ms
Reverse Sorted Array - Size: 32000, Time: 7 ms
Random Array - Size: 32000, Time: 12 ms
--------------------------------------------
Sorted Array - Size: 64000, Time: 14 ms
Reverse Sorted Array - Size: 64000, Time: 11 ms
Random Array - Size: 64000, Time: 18 ms
Graph table
Number of elements Sorted array Reverse sorted array Random array
1000 0 0 0
4000 0 0 1
8000 1 1 2
16000 3 3 5
32000 7 8 12
64000 14 11 18
