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
|
#include <chrono>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <numeric>
#include <random>
#include <vector>
unsigned long long getRndULL( unsigned long long, unsigned long long );
void quicksort_element_left( std::vector<unsigned long long int>::iterator left,
std::vector<unsigned long long int>::iterator right );
void printFromIte( const std::vector<unsigned long long>::iterator&,
const std::vector<unsigned long long>::iterator& );
int main()
{
int constexpr How_Many { 20 };
std::vector<unsigned long long> v( How_Many );
std::generate( v.begin(), v.end(), []() { return getRndULL( 1, 50 ); } );
std::cout << "Original ";
printFromIte( v.begin(), v.end() );
quicksort_element_left( v.begin(), v.end() );
std::cout << "After quicksort_element_left() --> ";
printFromIte( v.begin(), v.end() );
}
unsigned long long getRndULL( unsigned long long min, unsigned long long max )
{
static std::mt19937 eng {
static_cast<unsigned>(
std::chrono::high_resolution_clock::now().time_since_epoch().count()
)
};
std::uniform_int_distribution<unsigned long long> dst( min, max );
return dst( eng );
}
void quicksort_element_left( std::vector<unsigned long long int>::iterator left,
std::vector<unsigned long long int>::iterator right )
{
if (left >= right) { return; }
std::vector<unsigned long long int>::iterator it {
std::partition(left, right + 1, [left](unsigned long long int e) {
std::cout << "*left: " << *left << "; e: " << e << '\n';
return e < (*left);
} )
};
std::cout << "After partition --> ";
printFromIte( left, right );
iter_swap(right, it);
quicksort_element_left( left, it - 1 );
quicksort_element_left( it + 1, right );
return;
}
void printFromIte( const std::vector<unsigned long long>::iterator& begin,
const std::vector<unsigned long long>::iterator& end )
{
std::vector<int> v2( end - begin );
std::iota( v2.begin(), v2.end(), 0 );
std::cout << "vector content:\npos: ";
for (const auto& e : v2) {
std::cout << std::setw( 3 ) << e;
}
std::cout << "\nelem: ";
for (auto ite { begin }; ite != end; ++ite) {
std::cout << std::setw( 3 ) << *ite;
}
std::cout << "\n\n";
}
|