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

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!