Quicksort using the STL partition function

I wrote the following quicksort function:

1
2
3
4
5
6
7
8
9
10
11
12
13
void _sort(vector<unsigned short int>::iterator left,
            vector<unsigned short int>::iterator right)
{
    if(left < right)
    {
        vector<unsigned short int>::iterator it = partition(left, right + 1, [right](unsigned short int essential)
                                                                                    {return essential < (*right);});
        iter_swap(right, it);
        _sort(left, it - 1);
        _sort(it + 1, right);
    }
    return;
}


Clearly, the pivots it uses are always the last elements of intervals.

Sometime later, I wrote this:

1
2
3
4
5
6
7
8
9
10
11
12
13
void quicksort_element_left(vector<unsigned long long int>::iterator left,
                        vector<unsigned long long int>::iterator right)
{
    if(left < right)
    {
        vector<unsigned long long int>::iterator it = partition(left, right + 1, [left](unsigned long long int e)
                                                                                            {return e < (*left);});
        iter_swap(right, it);
        quicksort_element_left(left, it - 1);
        quicksort_element_left(it + 1, right);
    }
    return;
}


It's supposed to be a quicksort function, one that always takes the first elements of intervals as pivots, yet it refuses to work. Why is that the case?
The main problem is you asked the question the wrong way.
Don’t you think compiler warnings are important to programmers? And do you presume people will take time to write a driver program just to test your code and get compiler directions?
Do post compilable (or nearly compilable) snippets which reproduce your error, or you could get no answers. It implies there must be a main() and a copy of your data.

You can find a good example of quicksort made by std::partition here:
https://en.cppreference.com/w/cpp/algorithm/partition
As you can see, it’s quite different from yours.
You should consider an iterator can ‘move’ from an element to another and the value pointed by a not-const iterator may vary too.

Look what your function does:
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";
}


Example output:
Original vector content:
pos:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
elem:  49 34 47 33 13 34 42 43  9 47 36 37 32 22 45 49 25 22 42 49

*left: 49; e: 49
*left: 49; e: 0
*left: 0; e: 34
*left: 0; e: 49
*left: 0; e: 42
*left: 0; e: 22
*left: 0; e: 25
*left: 0; e: 49
*left: 0; e: 45
*left: 0; e: 22
*left: 0; e: 32
*left: 0; e: 37
*left: 0; e: 36
*left: 0; e: 47
*left: 0; e: 9
*left: 0; e: 43
*left: 0; e: 42
*left: 0; e: 34
*left: 0; e: 13
*left: 0; e: 33
*left: 0; e: 47
After partition --> vector content:
pos:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
elem:   0 34 47 33 13 34 42 43  9 47 36 37 32 22 45 49 25 22 42 49

*left: 47; e: 47
*left: 47; e: 34
*left: 34; e: 33
*left: 34; e: 13
*left: 34; e: 34
*left: 34; e: 49
*left: 34; e: 42
*left: 34; e: 22
*left: 34; e: 42
*left: 34; e: 25
*left: 34; e: 43
*left: 34; e: 49
*left: 34; e: 45
*left: 34; e: 22
*left: 34; e: 9
*left: 34; e: 47
*left: 34; e: 32
*left: 34; e: 36
*left: 34; e: 37
After partition --> vector content:
pos:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
elem:  34 33 13 22 25 22  9 32 36 37 47 43 45 49 42 34 42 49

*left: 34; e: 34
*left: 34; e: 32
*left: 32; e: 33
*left: 32; e: 9
*left: 32; e: 13
*left: 32; e: 22
*left: 32; e: 25
*left: 32; e: 22
After partition --> vector content:
pos:    0  1  2  3  4  5  6
elem:  32  9 13 22 25 22 33

*left: 32; e: 32
*left: 32; e: 22
*left: 22; e: 9
*left: 22; e: 13
*left: 22; e: 22
*left: 22; e: 25
After partition --> vector content:
pos:    0  1  2  3  4
elem:  22  9 13 22 25

*left: 22; e: 22
*left: 22; e: 13
*left: 13; e: 9
After partition --> vector content:
pos:    0  1
elem:  13  9

*left: 13; e: 13
*left: 13; e: 9
After partition --> vector content:
pos:    0
elem:   9

*left: 25; e: 25
*left: 25; e: 22
After partition --> vector content:
pos:    0
elem:  22

*left: 37; e: 37
*left: 37; e: 36
*left: 36; e: 47
*left: 36; e: 49
*left: 36; e: 42
*left: 36; e: 34
*left: 36; e: 43
*left: 36; e: 42
*left: 36; e: 49
*left: 36; e: 45
After partition --> vector content:
pos:    0  1  2  3  4  5  6  7  8
elem:  36 34 43 45 49 42 47 42 49

*left: 36; e: 36
*left: 36; e: 34
After partition --> vector content:
pos:    0
elem:  34

*left: 45; e: 45
*left: 45; e: 43
*left: 43; e: 49
*left: 43; e: 49
*left: 43; e: 42
*left: 43; e: 42
*left: 43; e: 47
After partition --> vector content:
pos:    0  1  2  3  4  5
elem:  43 42 42 47 49 49

*left: 43; e: 43
*left: 43; e: 42
*left: 42; e: 42
After partition --> vector content:
pos:    0  1
elem:  42 42

*left: 49; e: 49
*left: 49; e: 47
*left: 47; e: 49
After partition --> vector content:
pos:    0  1
elem:  47 49

After quicksort_element_left() --> vector content:
pos:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
elem:   0 49  9 13 22 32 22 25 34 33 47 34 36 37 42 43 42 45 47 49

Topic archived. No new replies allowed.