150 lines
4.0 KiB
C++
150 lines
4.0 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <chrono>
|
|
#include <algorithm>
|
|
#include <thread>
|
|
#include <fstream>
|
|
#define ARR_LEN 45'000
|
|
using namespace std;
|
|
|
|
void merge(int array[], int const left, int const mid,
|
|
int const right)
|
|
{
|
|
int const subArrayOne = mid - left + 1;
|
|
int const subArrayTwo = right - mid;
|
|
|
|
// Create temp arrays
|
|
auto *leftArray = new int[subArrayOne],
|
|
*rightArray = new int[subArrayTwo];
|
|
|
|
// Copy data to temp arrays leftArray[] and rightArray[]
|
|
for (auto i = 0; i < subArrayOne; i++)
|
|
leftArray[i] = array[left + i];
|
|
for (auto j = 0; j < subArrayTwo; j++)
|
|
rightArray[j] = array[mid + 1 + j];
|
|
|
|
auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
|
|
int indexOfMergedArray = left;
|
|
|
|
// Merge the temp arrays back into array[left..right]
|
|
while (indexOfSubArrayOne < subArrayOne
|
|
&& indexOfSubArrayTwo < subArrayTwo) {
|
|
if (leftArray[indexOfSubArrayOne]
|
|
<= rightArray[indexOfSubArrayTwo]) {
|
|
array[indexOfMergedArray]
|
|
= leftArray[indexOfSubArrayOne];
|
|
indexOfSubArrayOne++;
|
|
}
|
|
else {
|
|
array[indexOfMergedArray]
|
|
= rightArray[indexOfSubArrayTwo];
|
|
indexOfSubArrayTwo++;
|
|
}
|
|
indexOfMergedArray++;
|
|
}
|
|
|
|
// Copy the remaining elements of
|
|
// left[], if there are any
|
|
while (indexOfSubArrayOne < subArrayOne) {
|
|
array[indexOfMergedArray]
|
|
= leftArray[indexOfSubArrayOne];
|
|
indexOfSubArrayOne++;
|
|
indexOfMergedArray++;
|
|
}
|
|
|
|
// Copy the remaining elements of
|
|
// right[], if there are any
|
|
while (indexOfSubArrayTwo < subArrayTwo) {
|
|
array[indexOfMergedArray]
|
|
= rightArray[indexOfSubArrayTwo];
|
|
indexOfSubArrayTwo++;
|
|
indexOfMergedArray++;
|
|
}
|
|
delete[] leftArray;
|
|
delete[] rightArray;
|
|
}
|
|
|
|
// begin is for left index and end is right index
|
|
// of the sub-array of arr to be sorted
|
|
void mergeSort(int array[], int const begin, int const end)
|
|
{
|
|
if (begin >= end)
|
|
return;
|
|
|
|
int mid = begin + (end - begin) / 2;
|
|
mergeSort(array, begin, mid);
|
|
mergeSort(array, mid + 1, end);
|
|
merge(array, begin, mid, end);
|
|
}
|
|
|
|
void bubbleSort(int arr[], int n)
|
|
{
|
|
int i, j;
|
|
bool swapped;
|
|
for (i = 0; i < n - 1; i++) {
|
|
swapped = false;
|
|
for (j = 0; j < n - i - 1; j++) {
|
|
if (arr[j] > arr[j + 1]) {
|
|
swap(arr[j], arr[j + 1]);
|
|
swapped = true;
|
|
}
|
|
}
|
|
|
|
// If no two elements were swapped
|
|
// by inner loop, then break
|
|
if (!swapped)
|
|
break;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
using std::chrono::high_resolution_clock;
|
|
using std::chrono::duration_cast;
|
|
using std::chrono::duration;
|
|
using std::chrono::milliseconds;
|
|
srand(time(nullptr));
|
|
|
|
|
|
int nums1[ARR_LEN];
|
|
int (*p1)[ARR_LEN] = &nums1;
|
|
int nums2[ARR_LEN];
|
|
|
|
for(int & i : nums1) {
|
|
i = (int) rand() % 750 + 1;
|
|
}
|
|
|
|
copy(nums1, nums1+ARR_LEN, nums2);
|
|
|
|
auto total1 = high_resolution_clock ::now();
|
|
|
|
auto t1 = high_resolution_clock::now();
|
|
bubbleSort(nums1, ARR_LEN);
|
|
// mergeSort(nums1, 0, sizeof(nums1) / sizeof(nums1[0]));
|
|
// thread merge (mergeSort, nums1, 0, sizeof(nums1) / sizeof(nums1[0]));
|
|
auto t2 = high_resolution_clock::now();
|
|
|
|
|
|
auto t3 = high_resolution_clock ::now();
|
|
bubbleSort(nums2, ARR_LEN);
|
|
// thread bubble (bubbleSort, nums2, ARR_LEN);
|
|
auto t4 = high_resolution_clock ::now();
|
|
|
|
// thread bubble2(bubbleSort, nums1, 0);
|
|
|
|
|
|
// bubble2.join();
|
|
// bubble.join();
|
|
auto total2 = high_resolution_clock::now();
|
|
|
|
auto ms1 = duration<double, std::milli>(t2-t1);
|
|
auto ms2 = duration<double, std::milli>(t4-t3);
|
|
auto total_time = duration<double, std::milli>(total2-total1);
|
|
cout << "Merge sort took: "<< ms1.count() << "ms" << endl;
|
|
cout << "Bubble sort took: " << ms2.count() << "ms" << endl;
|
|
cout << "Total time: " << total_time.count() << "ms" << endl;
|
|
|
|
return 0;
|
|
}
|
|
|
|
|