Last active
March 13, 2024 09:06
-
-
Save zachwhaley/533235d7be027b12c67ebff478678aa5 to your computer and use it in GitHub Desktop.
C++ quicksort with iterators
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <algorithm> | |
#include <iostream> | |
#include <list> | |
template<typename Iter> | |
void print(const Iter& beg, const Iter& end) | |
{ | |
std::for_each(beg, end, [](auto& i) { std::cout << i << " "; }); | |
std::cout << std::endl; | |
} | |
template<typename Iter> | |
Iter part(Iter beg, Iter end, const typename Iter::value_type& pivot) | |
{ | |
Iter head = beg; | |
Iter tail = std::prev(end); | |
while (head != tail) { | |
while (*head < pivot) { | |
if (++head == tail) { | |
return head; | |
} | |
} | |
while (*tail >= pivot) { | |
if (--tail == head) { | |
return head; | |
} | |
} | |
std::cout << "swap " << *head << " ↔ " << *tail << std::endl; | |
std::iter_swap(head, tail); | |
std::cout << " ⇒ "; print(beg, end); | |
if (++head == tail--) { | |
return head; | |
} | |
} | |
return head; | |
} | |
template<typename Iter> | |
void quick_sort(Iter beg, Iter end) | |
{ | |
std::cout << "sort "; print(beg, end); | |
if (beg == end) { | |
return; | |
} | |
auto pivot = *beg; | |
Iter split = part(beg, end, pivot); | |
// sort left | |
quick_sort(beg, split); | |
// sort right | |
Iter new_middle = beg; | |
quick_sort(++new_middle, end); | |
} | |
int main(int argc, const char* argv[]) | |
{ | |
std::list<int> l = { 3, 2, 1, 5, 2, 12, 4356, 1, 5, 12 }; | |
quick_sort(l.begin(), l.end()); | |
std::cout << "done "; print(l.begin(), l.end()); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi, I tried your impl with the following and it did not work:
(A) 1 12 5 26 7 14 3 7 2; it produced: 1 2 3 7 5 7 12 14 26
(B) 3 42 1 5 32 37 4356 41 135 92; it produced: 1 5 3 32 37 41 42 92 135 4356
(C) 3 2 1 5 2 12 4356 1 5 12, with mid point pivot
auto pivot = beg; std::advance(pivot, std::distance(beg, end)/2);
; it produced: 3 1 1 2 2 5 5 12 12 4356(D) 3 42 1 5 32 37 4356 41 135 92, with mid point pivot
auto pivot = beg; std::advance(pivot, std::distance(beg, end)/2);
; it produced: 3 1 5 32 37 41 42 92 135 4356(E) Also, due to the weak/strong asymmetry in the comparisons done in
part
, it can not handlestd::greater
ordering.(F) Finally, this is inefficient as it ends up making several redundant comparisons:
This is what I came up with and it seems to work: