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

[Agregat]

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

PHP Code:

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


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

[gaglik]

Originally Posted by Agregat

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

PHP Code:

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 и далее пока не дойдете до STL docs это содержат. Специально для вас еще один крутой алгоритм:

PHP Code:

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!), но так как алгоритм случайный - можеы быть как хуже так и лучше