algorithm - C++ Quick Sort Implementation, not having the right output -

i implementing quick sort algorithm cormen's algorithm book(clrs).

 vector<int> numbers = {5, 6, 3, 4, 1, 2, 7, 13, -6, 0, 3, 1, -2};   my_quick_sort(numbers.begin(), numbers.end()); 

it has no error, can not sort numbers.

the pseudo code in book following.

1. quicksort(a, p, r)
2. if p < r
3. q = partition(a, p, r)
4. quicksort(a, p, q-1)

5. quicksort(a, q+1, r)

6. partition(a, p, r)

7. x = a[r]
8. i = p - 1
9. for j = p r - 1
10. ___i= i+1;
11. ___exchange a[i] a[j]
12. exchange a[i+1] a[r]
13. return + 1;

my implementation following.

 template<typename t>  void swap(t a, t b)  {      typedef typename std::iterator_traits<t>::value_type value_type;      value_type temp;      temp = *a;      *a = *b;      *b = temp;  }   template<typename t>  int partition(t begin, t end)  {      typedef typename std::iterator_traits<t>::value_type value_type;      value_type x;          x = *end;      t = begin - 1;      t j;      for(j = begin; j != end+1; ++j)      {          if ( x >= *j )          {               i++;               swap(i, j);          }          swap(i+1, end);      }      return static_cast<int>(distance(begin, i) + 1);  }   template<typename t>  void q_sort(t begin, t end)  {      auto length = end - begin;      if (length < 2) return;       if ( begin != end )      {          auto pivot = partition(begin, end);          q_sort(begin, begin + pivot - 1);          q_sort(begin + pivot + 1, end);      }  } 

anybody has idea code? works, not sorting. example, if input shuffle: 13, 0, -6, 6, -2, 5, 4, 3, 1, 1, 3, 2, 7,

output following my_quick_sort: -6, -2, 0, 6, 13, 0, 5, 1, 1, 4, 2, 3, 7,

a few notes implementation:

firstly, simplify q_sort method , logic, return iterator partition method rather int. simplify q_sort below:

template<typename t> void q_sort(t begin, t end) {     if ( begin < end )     {         t pivot = partition(begin, end);         q_sort(begin, pivot - 1);         q_sort( pivot + 1, end);     } } 

please note not need check "if (length < 2) return;"

secondly, in partition method in loop terminating condition "j != end+1" not match pseudocode. should end - 1. here new code partition method. please note assuming second parameter (end) points actual last value rather pointing value beyond last.

template<typename t> t partition(t begin, t end) {     typedef typename std::iterator_traits<t>::value_type value_type;     value_type x;      x = *end;     t = begin - 1;      for(t j = begin; j < end; ++j)     {         if ( x >= *j )         {             i++;             swap(i, j);         }     }      swap(i+1, end);     //return static_cast<int>(distance(begin, i) + 1);     return i+1; } 

lastly, believe pseudocode assumes second parameter last element iterator numbers.end() points position beyond last element. need change call quick sort below:

vector<int>::iterator iterend = numbers.end(); --iterend; q_sort(numbers.begin(), iterend); 

after considering above points should able sort correctly.