fork(1) download 
  1. #include <iostream>
  2. #include <type_traits>
  3. #include <iterator>
  4. #include <cstdlib>
  5. using namespace std;
  6.  
  7. // assumes T::operator <(const T&) exists for the iterated type.
  8. template<
  9.    typename Iterator,
  10.    typename Compare=std::less<typename std::iterator_traits<Iterator>::value_type>
  11. >
  12. void quicksort(Iterator first, Iterator last, Compare cmp = Compare())
  13. {
  14.     // early exit on trivial list (zero or one element)
  15.     std::size_t len = std::distance(first, last);
  16.     if (len <= 1)
  17.         return;
  18.  
  19.     // establish pivot, move it to end of sequence
  20.     Iterator tail = last - 1, pvt = first + (std::rand() % (len-1));
  21.     std::iter_swap(pvt, tail);
  22.  
  23.     // run through scan
  24.     pvt = first;
  25.     for (Iterator head = first; head != tail; ++head)
  26.     {
  27.         if (cmp(*head,*tail))
  28.             std::iter_swap(head, pvt++);
  29.     }
  30.     std::iter_swap(pvt, tail);
  31.  
  32.     // run through sublists. note: pvt is NOT included.
  33.     quicksort(first, pvt);
  34.     quicksort(pvt+1, last);
  35. }
  36. //////////////////////////////////////////////////////////////////////
  37.  
  38.  
  39. int main()
  40. {
  41.     int ar[] = { 7, 3, 5, 8, 9, 2, 1, 6, 4};
  42.     std::copy(std::begin(ar), std::end(ar), std::ostream_iterator<int>(cout, " "));
  43.     std::cout << std::endl;
  44.  
  45.     quicksort(std::begin(ar), std::end(ar));
  46.     std::copy(std::begin(ar), std::end(ar), std::ostream_iterator<int>(cout, " "));
  47.     std::cout << std::endl;
  48.     return 0;
  49. }
Success #stdin #stdout 0s 3296KB
comments (?)
stdin 
Standard input is empty
stdout 
7 3 5 8 9 2 1 6 4 
1 2 3 4 5 6 7 8 9
https://ideone.com/yE4J7f
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!