Aujourd’hui, j’ai recodé un code à moi vieux de quatre ans. C’était une version un peu modifiée de l’exercice zTri, où j’avais implémenté les tris à bulle, par insertion et rapide.
C’est amusant de voir que j’ai progressé et comment j’ai pu raccourcir le code et le rendre plus agréable à lire. Bien entendu, il y a de quoi améliorer. Mais c’est un exemple pour tout ceux qui débutent et peut-être se sentent découragés parce qu’ils ont l’impression de ne pas progresser.
Je mets mon nouveau code en spolier en-dessous. Voici le lien de la V1. Comparez et voyez. Si vous voulez me faire des remarques sur la V2, je les attends avec impatience. 
#include <algorithm>
#include <functional>
#include <iostream>
#include <random>
#include <vector>
class ComparePolicyLess
{
protected:
template <typename T>
bool comparing(T const & left, T const & right)
{
return std::less<T>{} (left, right);
}
};
class ComparePolicyGreat
{
protected:
template <typename T>
bool comparing(T const & left, T const & right)
{
return std::greater<T>{} (left, right);
}
};
template <typename Container, typename SortPolicy>
class Sort : SortPolicy
{
using SortPolicy::algorithm;
public:
void sort(Container & container)
{
algorithm<Container>(container);
}
};
template <typename ComparePolicy>
class SortPolicyBubble : private ComparePolicy
{
using ComparePolicy::comparing;
protected:
template <typename Container>
void algorithm(Container & container)
{
auto it_begin = std::end(container); --it_begin;
for (auto it = it_begin; it != std::begin(container); --it)
{
bool no_swap { true };
for (auto jt = std::begin(container); jt != it; ++jt)
{
auto kt = jt; ++kt;
if (comparing(*jt, *kt))
{
using std::swap;
swap(*kt, *jt);
no_swap = false;
}
}
if (no_swap)
{
break;
}
}
}
};
template <typename ComparePolicy>
class SortPolicyInsertion : private ComparePolicy
{
using ComparePolicy::comparing;
protected:
template <typename Container>
void algorithm(Container & container)
{
for (auto it = std::begin(container); it != std::end(container); ++it)
{
// https://stackoverflow.com/a/18454367/6060256
std::rotate(std::upper_bound(std::begin(container), it, *it), it, std::next(it));
}
}
};
template <typename ComparePolicy>
class SortPolicyQuick : private ComparePolicy
{
using ComparePolicy::comparing;
protected:
template <typename Container>
void algorithm(Container & container)
{
auto end = std::end(container); --end;
quick_sort(container, std::begin(container), end);
}
private:
template <typename Iterator>
Iterator pivot(Iterator first, Iterator last)
{
std::random_device rd {};
std::default_random_engine engine { rd() };
int const max { static_cast<int>(std::distance(first, last)) };
std::uniform_int_distribution uniform_dist(0, max);
Iterator temp { first };
std::advance(temp, uniform_dist(engine));
return temp;
}
template <typename Iterator>
Iterator part(Iterator first, Iterator last)
{
auto pivot = this->pivot(first, last);
auto const pivot_original_value { *pivot };
using std::swap;
swap(*pivot, *last);
auto jt = first;
for (auto it = first; it != last; ++it)
{
if (comparing(pivot_original_value, *it))
{
swap(*it, *jt);
++jt;
}
}
std::swap(*last, *jt);
return jt;
}
template <typename Container, typename Iterator>
void quick_sort(Container & container, Iterator first, Iterator last)
{
if (std::distance(first, last) > 0)
{
Iterator pivot { part(first, last) };
Iterator previous { pivot };
Iterator next { pivot };
// Protection because the pivot is random and can be the beginning or end of the container.
if (pivot != std::begin(container)) { --previous; }
quick_sort(container, first, previous);
if (pivot != std::end(container)) { ++next; }
quick_sort(container, next, last);
}
}
};
template <typename Container>
using BubbleSort = Sort<Container, SortPolicyBubble<ComparePolicyGreat>>;
template <typename Container>
using InsertionSort = Sort<Container, SortPolicyInsertion<ComparePolicyGreat>>;
template <typename Container>
using QuickSort = Sort<Container, SortPolicyQuick<ComparePolicyGreat>>;
int main()
{
std::vector<int> v1 { 1, -8, 4, 48, -10, 700, 5, -7, 54545, -777 };
QuickSort<decltype(v1)> qs;
qs.sort(v1);
for (auto i : v1)
{
std::cout << i << std::endl;
}
return 0;
}
