Quick Sort using iterators

Lately I have been experimenting various algorithms using std iterators and tried to implement quick sort algorithm using just iterators instead of passing on the vector by reference. Following is the implementation of the algorithm.

#include <vector>
#include <iostream>
#include <algorithm>

auto partition(std::vector<int>::iterator start, std::vector<int>::iterator end_it){
   auto partition_idx = start;
   for(auto i = start; i != end_it; i++){
     if(*i <= *end_it){
       std::iter_swap(i, partition_idx);
       partition_idx++;
     }
   }
   std::iter_swap(partition_idx, end_it);
   return partition_idx;
}

void quick_sort(std::vector<int>::iterator start, std::vector<int>::iterator end_it){
  int size = std::distance(start, end_it);
  if (size <= 1) return;
  auto partition_idx = partition(start, end_it);
  quick_sort(start, partition_idx-1);
  quick_sort(partition_idx, end_it);
}

int main(){
  std::vector<int> v{72, 23, 65, 53, 36, 90, 76, 50, 1, 20, 64, 18, 26, 39, 34, 91, 86, 21, 81, 7, 58, 27, 9, 61, 77, 2, 88, 70, 79, 3, 100, 44, 94, 51, 83, 48, 68, 13, 96, 30, 98, 24, 95, 67, 55, 8, 56, 19, 52, 85, 6, 69, 43, 16, 93, 74, 60, 41, 37, 84, 66, 99, 78, 57, 33, 14, 62, 35, 31, 46, 59, 38, 12, 92, 73, 25, 32, 22, 28, 63, 54, 97, 29, 47, 15, 40, 87, 80, 17, 71, 11, 4, 75, 89, 49, 10, 5, 45, 42, 82};
  quick_sort(v.begin(), v.end()-1); // one element before end
  for(const auto & i:v){
    std::cout << i << ' ';
  }
 return 0;
}

Author: Saurabh Purnaye

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s