eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingsortowanie › Re: sortowanie
  • Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
    atman.pl!.POSTED!not-for-mail
    From: bartekltg <b...@g...com>
    Newsgroups: pl.comp.programming
    Subject: Re: sortowanie
    Date: Sun, 14 Oct 2012 12:42:27 +0200
    Organization: ATMAN - ATM S.A.
    Lines: 95
    Message-ID: <k5e4ur$ls4$1@node2.news.atman.pl>
    References: <k59gbj$be7$1@node2.news.atman.pl>
    <6...@g...com>
    <k59jgh$mb7$1@mx1.internetia.pl> <k59jvr$360$1@node1.news.atman.pl>
    <k59q5n$np3$1@mx1.internetia.pl> <k5a1ih$slr$1@node2.news.atman.pl>
    <k5bd6c$a6c$1@mx1.internetia.pl> <k5blvn$3nk$1@node1.news.atman.pl>
    <k5chsn$f2b$1@mx1.internetia.pl>
    <6...@g...com>
    <5079e395$0$1305$65785112@news.neostrada.pl>
    <k5crfb$aso$1@node1.news.atman.pl>
    <5079f25c$0$26697$65785112@news.neostrada.pl>
    <k5crvb$h7t$2@node2.news.atman.pl>
    <f...@g...com>
    <2...@g...com>
    NNTP-Posting-Host: 144-mi3-6.acn.waw.pl
    Mime-Version: 1.0
    Content-Type: text/plain; charset=UTF-8; format=flowed
    Content-Transfer-Encoding: 8bit
    X-Trace: node2.news.atman.pl 1350211355 22404 85.222.69.144 (14 Oct 2012 10:42:35
    GMT)
    X-Complaints-To: u...@a...pl
    NNTP-Posting-Date: Sun, 14 Oct 2012 10:42:35 +0000 (UTC)
    User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:15.0) Gecko/20120907
    Thunderbird/15.0.1
    In-Reply-To: <2...@g...com>
    Xref: news-archive.icm.edu.pl pl.comp.programming:199888
    [ ukryj nagłówki ]

    W dniu 2012-10-14 09:39, M.M. pisze:
    > W dniu niedziela, 14 października 2012 08:15:43 UTC+2 użytkownik kenobi napisał:
    >> hehe, mi sie tez kojarzy jako if z 20ma poziomami zaglebbienia i 2^20 'klauzulami'
    na koniec ;-) No ale nie wiem jak wygladalaby
    >>
    >> (ile wierszy) optymalizowana wersja takiego ifu
    >
    > Moze inspiracji nalezy szukac w sekcji "Optymalne sortowanie"
    > http://pl.wikipedia.org/wiki/Sie%C4%87_sortuj%C4%85c
    a

    Nie do końca, ale...*)
    To trochę inne zagadnienia.
    Zauważ, że posortowanie 5 elementów
    wymaga 9 komparatorów. Czyli 9 porównań.
    Wiemy, że wystarczy 7.

    Sieć sortująca nie ma 'ifów' mogących
    diametralnie zmienić działanie w zależności
    od wyniku, może tylko porównywać pary
    w ustalonej kolejności.

    Po pierwszych 2 porównaniach możemy mieć wiedzę
    postaci a<-b<-c lub a<-b->c i zależnie od tego
    należy działć ciut inaczej.


    Za to mają inna przewagę. Cześć porównan moze być
    równoległa, więc głębokość wynosi (wg wiki) 5.
    Wynik będzie w czasie wykonania 5 kolejnych porównań.
    (tylko czasem wykona się dwa).

    O, znalazłem ciekawą stronę.
    http://pages.ripco.net/~jgamble/nw.html

    http://jgamble.ripco.net/cgi-bin/nw.cgi?inputs=5&alg
    orithm=batcher&output=svg

    Zgadza się.

    I teraz do naszego ale. Jest to ewidentnie gorsze rozwiązanie
    niż algorytm optymalny, czy nawet przywoływany przez PK
    Ford and Johnson Merge-Insertion Sort (który dla 10 elementów
    ma optymalne 22 porównania). Hmm, a nawet insertsorta
    z wyszukiwaniem binarnym.
    user.it.uu.se/~fm/Courses/AA/2000/h6.ps

    Za to jest znacznie prostszy.

    I wykorzystuje 29 porównań
    http://jgamble.ripco.net/cgi-bin/nw.cgi?inputs=10&al
    gorithm=best&output=svg

    Można więc pociągnąć Twój sposób z http://pastebin.com/RGhkx6u6

    Mógłbyś użyć takiego ciągu (uwaga, zrobione automatycznie
    z wyników podanych przez stronę). daj znać, czy przebija sort10;)

    static inline void sort10_N( typs d[] ) {
    sort( d[4] , d[9] );
    sort( d[3] , d[8] );
    sort( d[2] , d[7] );
    sort( d[1] , d[6] );
    sort( d[0] , d[5] );
    sort( d[1] , d[4] );
    sort( d[6] , d[9] );
    sort( d[0] , d[3] );
    sort( d[5] , d[8] );
    sort( d[0] , d[2] );
    sort( d[3] , d[6] );
    sort( d[7] , d[9] );
    sort( d[0] , d[1] );
    sort( d[2] , d[4] );
    sort( d[5] , d[7] );
    sort( d[8] , d[9] );
    sort( d[1] , d[2] );
    sort( d[4] , d[6] );
    sort( d[7] , d[8] );
    sort( d[3] , d[5] );
    sort( d[2] , d[5] );
    sort( d[6] , d[8] );
    sort( d[1] , d[3] );
    sort( d[4] , d[7] );
    sort( d[2] , d[3] );
    sort( d[6] , d[7] );
    sort( d[3] , d[4] );
    sort( d[5] , d[6] );
    sort( d[4] , d[5] );
    }


    A, stronka sama generuje takie 'swap macros'.

    pzdr
    bartekltg




Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: