Skip to content

Instantly share code, notes, and snippets.

@coderodde coderodde/main.cpp
Last active Jul 10, 2017

Embed
What would you like to do?
CR: sorting int vector
#include <vector>
#include <chrono>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
template<typename RandomAccessIterator1, typename RandomAccessIterator2>
void merge_sort_impl(RandomAccessIterator1 source_begin,
RandomAccessIterator1 source_end,
RandomAccessIterator2 target_begin,
RandomAccessIterator2 target_end)
{
auto range_length = std::distance(source_begin, source_end);
if (range_length < 2)
{
return;
}
auto left_chunk_length = range_length >> 1;
auto source_left_chunk_end = source_begin;
auto target_left_chunk_end = target_begin;
std::advance(source_left_chunk_end, left_chunk_length);
std::advance(target_left_chunk_end, left_chunk_length);
merge_sort_impl(target_begin,
target_left_chunk_end,
source_begin,
source_left_chunk_end);
merge_sort_impl(target_left_chunk_end,
target_end,
source_left_chunk_end,
source_end);
std::merge(source_begin,
source_left_chunk_end,
source_left_chunk_end,
source_end,
target_begin);
}
template<typename RandomAccessIterator>
void merge_sort(RandomAccessIterator begin, RandomAccessIterator end)
{
auto range_length = std::distance(begin, end);
if (range_length < 2)
{
return;
}
using value_type = typename std::iterator_traits<RandomAccessIterator>::value_type;
std::vector<value_type> aux(begin, end);
merge_sort_impl(aux.begin(), aux.end(), begin, end);
}
void sort(vector<int> & bar);
void mergeSort(vector<int>&left,vector<int>& right,vector<int>& bars);
#include <chrono>
#include <cstdint>
class CurrentTime {
std::chrono::high_resolution_clock m_clock;
public:
uint64_t milliseconds() {
return std::chrono::duration_cast<std::chrono::milliseconds>(m_clock.now().time_since_epoch()).count();
}
};
int main() {
vector<int> nums;
vector<int> nums2;
vector<int> nums3;
for (size_t i = 0; i < 1000 * 1000; i++)
{
int r = rand();
nums.push_back(r);
nums2.push_back(r);
nums3.push_back(r);
}
CurrentTime ct;
auto start_time = ct.milliseconds();
sort(nums);
auto end_time = ct.milliseconds();
cout << "OP mergesort in " << (end_time - start_time) << " milliseconds.\n";
start_time = ct.milliseconds();
merge_sort(nums2.begin(), nums2.end());
end_time = ct.milliseconds();
cout << "coderodde mergesort in " << (end_time - start_time)
<< " milliseconds.\n";
start_time = ct.milliseconds();
std::sort(nums3.begin(), nums3.end());
end_time = ct.milliseconds();
cout << "std::sort in " << (end_time - start_time) << " milliseconds.\n";
cout << boolalpha;
bool agreed = true;
for (int i = 0; i < nums.size(); ++i)
{
if (nums[i] != nums2[i] || nums[i] != nums3[i]) {
agreed = false;
break;
}
}
cout << "Algorithms agree: " << agreed << endl;
return 0;
}
void sort(vector<int> & bar) {
if (bar.size() <= 1) return;
int mid = bar.size() / 2;
vector<int> left;
vector<int> right;
for (size_t j = 0; j < mid;j++)
left.push_back(bar[j]);
for (size_t j = 0; j < (bar.size()) - mid; j++)
right.push_back(bar[mid + j]);
sort(left);
sort(right);
mergeSort(left, right, bar);
}
void mergeSort(vector<int>&left, vector<int>& right, vector<int>& bars)
{
int nL = left.size();
int nR = right.size();
int i = 0, j = 0, k = 0;
while (j < nL && k < nR)
{
if (left[j] < right[k]) {
bars[i] = left[j];
j++;
}
else {
bars[i] = right[k];
k++;
}
i++;
}
while (j < nL) {
bars[i] = left[j];
j++; i++;
}
while (k < nR) {
bars[i] = right[k];
k++; i++;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.