eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingKiedy qsort zaczyna źle działać?Re: Kiedy qsort zaczyna źle działać?
  • Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.P
    OSTED!not-for-mail
    From: bartekltg <b...@g...com>
    Newsgroups: pl.comp.programming
    Subject: Re: Kiedy qsort zaczyna źle działać?
    Date: Wed, 15 Jul 2015 23:10:50 +0200
    Organization: ATMAN - ATM S.A.
    Lines: 42
    Message-ID: <mo6i8q$sld$1@node1.news.atman.pl>
    References: <mo6d72$n3b$1@node1.news.atman.pl>
    NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
    Mime-Version: 1.0
    Content-Type: text/plain; charset=utf-8; format=flowed
    Content-Transfer-Encoding: 8bit
    X-Trace: node1.news.atman.pl 1436994650 29357 89.73.81.145 (15 Jul 2015 21:10:50 GMT)
    X-Complaints-To: u...@a...pl
    NNTP-Posting-Date: Wed, 15 Jul 2015 21:10:50 +0000 (UTC)
    User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101
    Thunderbird/31.7.0
    In-Reply-To: <mo6d72$n3b$1@node1.news.atman.pl>
    Xref: news-archive.icm.edu.pl pl.comp.programming:207850
    [ ukryj nagłówki ]

    On 15.07.2015 21:44, Borneq wrote:
    > QSort w najgorszym przypadku jak słyszałem, ma złożoność kwadratową.
    > Kiedy występuje ten najgorszy przypadek? Kiedy dane są już posortowane?
    > czy też jest to jeden specyficzny porządek, na którego natrafienie jest
    > trudniejsze niż wygranie w toto lotka?


    Zależy od tego, jako to qsort. Ten szkolny nie działą dla danych
    monotonicznych (posortowanych lub odwrotnie posortowanych).
    Dlaczego? Dlatego, że jeśli za element dzielący weźmiemy pierwszy
    element podtablicy, to wyląduje on albo na początku, albo na końcu.
    Rekurencja podzieliła nam podtablicę długośći na tablice dlugosci 1
    i n-2.
    Sposobów raczenia sobie z tym jest masa, pierwszym, jest losowy
    wybór elementu dzialącego. Wtedy musisz mieć ogromengo pecha ;-)

    Częściej stosowanym jest wzięcie za element dzielący mediany
    z trzech elementów, pierwszego, ostatniego i środkowego.
    Posortowane dane dzialą się idealnie (rekurencja dzlei na pół),
    dodatkową zaletą jest to, że element dzielący na pewno nie jest
    najmniejszym ani największym elementem tablicy, dzięki czemu
    można obyć się bez pewnych sprawdzeń w pętli.

    Niestety, nadal można tak spreparować dane, aby podział był
    bardzo zły (wymaga już to trochę wysiłku ;-) Weź kartkę i sobie
    rozrysuj. pewnie jakiś grzebień wyjdzie.
    Dlatego sporo implementacji (w tym chyba wszystkie standardowe w c++)
    używają algorytmu introsort, który jest to quicksorttem,
    który w wywołaniach rekurencyjnych sprawdza głębokość rekurencji.
    Jeśli jest ona zbyt duża (tzn z jakiś powodów, jak bardzo złośliwe
    dane, ciagle źle trafiamy) podtablica traktowana jest heapsortem.

    I ostatecznie biblioteczny "qsort" nie wpada w tryb kwadratowy nigdy.

    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: