Discussion about Quick sort

[jovany-wang]

The current quick sort algorithm is too concrete. It's better to make it more generic. The points that I listed here:

1. Make partition can be rewrite and we provide an implementation for it. This means we should make partition as an interface and provide a default implementation.

2. Make quick_sort API can be passed any iterable type. In another word, The API should looks like:

void quick_sort(std::random_iterator<?> begin, std::random_iterator<?> end);

3. Provide another overloading API for quick_sort which can be passed a comparer:

using Comparable = std::function<bool (const random_iterator<?> &prev, const random_iterator<?> &next)>;
void quick_sort(std::random_iterator<?> begin, std::random_iterator<?> end, Comparable comparer);

TODOs:

• implementation
• benchmark
• ut
• docs

[ivanallen]

I have 2 points.

1. Iterator in sort api should be Random Iterator.
2. I prefer the predicate Compare to be std::function<bool (const T& a, const T& b)>

[jovany-wang]

After we discussed offline, here are the usages we expected:

// default api
dsa::quick_sort(vec.begin(), vec.end());

// with default partition implemention
dsa::quick_sort(vec, 0, 100, dsa::DEFAULT_PARTITION_1);
dsa::quick_sort(vec, 0, 100, dsa::DEFAULT_PARTITION_2);

// with custom partition implementation
auto my_partition = [](random_iter left, random_iter right) -> size_t {
    // my custom partition algorithm.
};
dsa::quick_sort(vec.begin(), vec.end(), my_partition);