Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 07.05.2004, 10:18   #1
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default Для любителей оптимальных алгоритмов

В голову пришел чудо - алгоритм сортировки, выглядит следующим образом. Несмотря на страшный вид пользоваться им можно элементарно.
PHP Code:
template<class BidirectionalIterator, class StrictWeakOrdering
void best_sort (BidirectionalIterator firstBidirectionalIterator lastStrictWeakOrdering comp) {
 while (
next_permutation(firstlastcomp)); 

Для пытливых умов, предлагаю оценить временные затраты в терминах большого О.
Reply With Quote
Old 07.05.2004, 19:41   #2
Painfully Outlandish
 
gaglik's Avatar
 
Join Date: 05 2003
Location: Albainn
Age: 37
Posts: 113
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
Originally Posted by Agregat
В голову пришел чудо - алгоритм сортировки, выглядит следующим образом. Несмотря на страшный вид пользоваться им можно элементарно.
PHP Code:
template<class BidirectionalIterator, class StrictWeakOrdering
void best_sort (BidirectionalIterator firstBidirectionalIterator lastStrictWeakOrdering comp) {
 while (
next_permutation(firstlastcomp)); 

Для пытливых умов, предлагаю оценить временные затраты в терминах большого О.
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.
Reply With Quote
Old 07.05.2004, 19:46   #3
Painfully Outlandish
 
gaglik's Avatar
 
Join Date: 05 2003
Location: Albainn
Age: 37
Posts: 113
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

And the algorithm is "surprisingly" called snail sort.
Reply With Quote
Old 07.05.2004, 23:50   #4
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

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

2. Вы не первый, кто отметил, что я не первый кто это (алгоритм) заметил. www.sgi.com и далее пока не дойдете до STL docs это содержат. Специально для вас еще один крутой алгоритм:
PHP Code:
template <typename RanIt
void bogosort (RanIt firstRanIt last

while (
std::adjacent_find(firstlaststd::greater<typename std::iterator_traits<RanIt>::value_type>()) != last
std::random_shuffle(firstlast); 

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

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 20:46.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.