Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #27060 > unrolled thread

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

Back to article view | Back to pl.comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

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

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

[toc] | [next] | [standalone]

#27062

W dniu 2015-07-15 o 23:10, bartekltg pisze:
> 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.

Spotkałem się z przypadkiem zamiany quicksorta na metodę iteracyjną, 
zamiast stosu używając lokalnej tablicy. Działał szybciej.
Jeśli chodzi o sprawdzanie tej tablicy, to występuje to tak rzadko, że 
zamiast sprawdzać za pomocą if, lepiej, zwłaszcza w Javie czekać na wyjątek.

[toc] | [prev] | [next] | [standalone]

#27063

On 15.07.2015 23:18, Borneq wrote:
> W dniu 2015-07-15 o 23:10, bartekltg pisze:
>> 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.
>
> Spotkałem się z przypadkiem zamiany quicksorta na metodę iteracyjną,
> zamiast stosu używając lokalnej tablicy. Działał szybciej.

W pewnym przypadkach i mnimalnie. Potrzebujesz dodatkowej pamięci.
Chyba nawet w Cormenia było;-) Tworzy sie stos z wrzucanymi na niego
elementami podziału.

W ząden sposób nie zapobiega to przypadkowi złego działąnia qsorta.
Wiec tablica musi mieć w praktyce długość rzędu długości danych.


> Jeśli chodzi o sprawdzanie tej tablicy, to występuje to tak rzadko, że
> zamiast sprawdzać za pomocą if, lepiej, zwłaszcza w Javie czekać na
> wyjątek.


Pomojając, że nie mam pojęćia, jak odnieść to co mówisz do
quicksota bez stosu:

Raczej tylko w javie. W niektórych jezykach 'skryptowych'
sterowanie programem za pomocą wyjątków jest pobłogosławioną
metodą, i twory nazwane tam wyjatkami są do tego przestosowane.
Czy java jest jednym z nich, nie wiem, bardzo prawdopodobne.
W innych językach jest to idiotyzm od strony logicnzej
i wydajnościowej.

A od siebie dodam:
I czekać na cotygodniowe wywalanie się bazy danych;-)

pzdr
bartekltg

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web