Re: Kiedy qsort zaczyna źle działać?

From	bartekltg <bartekltg@gmail.com>
Newsgroups	pl.comp.programming
Subject	Re: Kiedy qsort zaczyna źle działać?
Date	2015-07-15 23:10 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<mo6i8q$sld$1@node1.news.atman.pl> (permalink)
References	<mo6d72$n3b$1@node1.news.atman.pl>

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: Kiedy qsort zaczyna źle działać? bartekltg <bartekltg@gmail.com> - 2015-07-15 23:10 +0200
  Re: Kiedy qsort zaczyna źle działać? Borneq <borneq@antyspam.hidden.pl> - 2015-07-15 23:18 +0200
    Re: Kiedy qsort zaczyna źle działać? bartekltg <bartekltg@gmail.com> - 2015-07-15 23:37 +0200

csiph-web