Hi,
Below is my implementation of quicksort using Hoare partition in c++
and using iterators. The algorithm is slightly different from the one
provided in Introduction to Algorithms (by CLRS, second edition). The
return value as suggested in the book should have been "end" but it
didn't work . It seems to work if the return is "end + 1". I am not
sure if this is an error in the book or corrected later. So could
someone let me know if my code is correct?
HOARE-PARTITION(A, p, r)
1 x ← A[p]
2 i ← p − 1
3 j ←r + 1
4 while TRUE
5 do repeat j ← j − 1
6 until A[ j ] ≤ x
7 repeat i ←i + 1
8 until A[i ] ≥ x
9 if i < j
10 then exchange A[i ] ↔ A[ j ]
11 else return j
template <class T>
T hoare_partition(T first, T end)
{
size_t size = end - first;
typename std::iterator_traits<T>::value_type v = *(first + rand()
%size);
first--;
while (true)
{
do{
end--;
}while (*end > v);
do {
first++;
}while (*first < v);
if (first < end)
std::iter_swap(first,end);
else
return end + 1;
}
}
template <class T>
void quick_sort(T first, T end)
{
size_t size = end - first;
if (size > 1){
T pivot = hoare_partition (first, end);
quick_sort(first, pivot);
quick_sort(pivot, end);
}
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
