Для любителей оптимальных алгоритмов

[Agregat]

В голову пришел чудо - алгоритм сортировки, выглядит следующим образом. Несмотря на страшный вид пользоваться им можно элементарно.

template<class BidirectionalIterator, class StrictWeakOrdering>
void best_sort (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp) {
while (next_permutation(first, last, comp));
}


Для пытливых умов, предлагаю оценить временные затраты в терминах большого О. :)

[gaglik]

В голову пришел чудо - алгоритм сортировки, выглядит следующим образом. Несмотря на страшный вид пользоваться им можно элементарно.

template<class BidirectionalIterator, class StrictWeakOrdering>
void best_sort (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp) {
while (next_permutation(first, last, comp));
}


Для пытливых умов, предлагаю оценить временные затраты в терминах большого О. :)

Vo pervyx algoritm suschestvoval i do etogo.
Vo vtoryx chudom ego nazvat' nikak nel'zya t.k. optimal'nye algoritmy (based on comparisons) sortiruyut O(NlogN), i dokazano chto bystree ne vozmojno, a etot algoritm sortiruet O(N!), esli pomelochit'sya O(N*N!), chto namnogo medlennee chem daje exponencial'noe vremya.

Take care.

[gaglik]

And the algorithm is "surprisingly" called snail sort. :)

[Agregat]

1. На первый пост: во - первых я не сказал, что я его выдумал, я сказал, что он мне пришел в голову. Во - вторых, я не знаю, что ты подразумеваете под based on comparisons, но Bucketsort основанный на сравнение (comparison) на равенство однозначно 2*N без больших О. В - третьих посмотрите в толковом словаре слово сарказм.

2. Вы не первый, кто отметил, что я не первый кто это (алгоритм) заметил. www.sgi.com (http://www.sgi.com) и далее пока не дойдете до STL docs это содержат. Специально для вас еще один крутой алгоритм:

template <typename RanIt>
void bogosort (RanIt first, RanIt last)
{
while (std::adjacent_find(first, last, std::greater<typename std::iterator_traits<RanIt>::value_type>()) != last)
std::random_shuffle(first, last);
}

Идея не моя, реализация моя, хотя если копнуть в гугле найдете подобное, я не сомневаюсь, но это уже домашнее задание. Докажите его линейность (!) и приведите условия для доказательства линейности в худшем случае, при этих условиях, в худшем случае без подобных условий, как понятно тот же O(N!), но так как алгоритм случайный - можеы быть как хуже так и лучше :)