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?

do góry

Dnia 15.07.2015 Borneq <b...@a...hidden.pl> napisał/a:
> 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 nie tyle od samego posortowania, co od wyboru elementu wg którego
"dzielisz" zbiór. Jeśli "pechowo" zawsze trafisz w element największy
(lub najmniejszy) to dostajesz podział na zbiór jednoelementowy i "resztę"
(czyli nie dość że takie "pechowe typowania" sortują tak na prawdę tylko
jeden element a reszta pozostaje jak było, to jeszcze rośnie
zapotrzebowanie na pamięć stosu, bo rekurencja idzie bardzo głęboko).

do góry

W dniu 2015-07-15 o 22:55, Pit pisze:
> Zależy nie tyle od samego posortowania, co od wyboru elementu wg którego
> "dzielisz" zbiór. Jeśli "pechowo" zawsze trafisz w element największy
> (lub najmniejszy) to dostajesz podział na zbiór jednoelementowy i "resztę"
> (czyli nie dość że takie "pechowe typowania" sortują tak na prawdę tylko
> jeden element a reszta pozostaje jak było, to jeszcze rośnie
> zapotrzebowanie na pamięć stosu, bo rekurencja idzie bardzo głęboko).

Czy procedury się przed tym zabezpieczają? czy to jest naprawdę rzadki
przypadek, że łatwiej trafić w totolotka?

do góry

W dniu 2015-07-15 o 23:06, Borneq pisze:
> Czy procedury się przed tym zabezpieczają? czy to jest naprawdę rzadki
> przypadek, że łatwiej trafić w totolotka?

Ale nawet rzadki, to może trafić się gdy sortujemy indeks bazy danych
wiele razy na sekundę a system wykrzacza się raz na parę miesięcy z
powodu przepełnienia stosu przez qsort.

do góry

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

do góry

On 15.07.2015 23:08, Borneq wrote:
> W dniu 2015-07-15 o 23:06, Borneq pisze:
>> Czy procedury się przed tym zabezpieczają? czy to jest naprawdę rzadki
>> przypadek, że łatwiej trafić w totolotka?
>
> Ale nawet rzadki, to może trafić się gdy sortujemy indeks bazy danych
> wiele razy na sekundę a system wykrzacza się raz na parę miesięcy z
> powodu przepełnienia stosu przez qsort.

Ktoś go chujowo napisał;-)

pzdr
bartekltg

do góry

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.

do góry

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

do góry

Dnia 15.07.2015 Borneq <b...@a...hidden.pl> napisał/a:
> 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.

W Javie żadna kolekcja (ze standardowej biblioteki) nie zwraca dla 'sort'
wyjątków postaci "nietypowy przypadek, zabrakło stosu" tylko radzi sobie z
takimi problemami wewnętrznie. Jedyne wyjątki jakie można dostać, to
nieprawidłowy zakres czy nieprawidłowy komparator (ewentualnie
NullPointerException jeśli masz tablicę referencji do obiektów i któraś
referencja jest pusta). Zresztą nie można mieć żadnej gwarancji co do tego
jaki konkretnie algorytm kryje się pod metodą 'sort' (może być inny dla
listy, inny dla wektora a jeszcze inny dla na przykład SortedSet czy
kolejki priorytetowej), bo po pierwsze implementacja może się różnić w
zależności od wersji Javy a po drugie implementacja może się różnić od
ilości danych (czy od tego co się będzie działo w trakcie sortowania).

Zresztą wyjątki w Javie służą raczej do sytuacji w których twórca
klasy/metody musi coś zasygnalizować użytkownikowi klasy/metody z czym
klasa/metoda sama w sobie nie jest w stanie sobie poradzić w rozsądny
sposób (na przykład użytkownik klasy zgłasza chęć utworzenia pliku, którego
nazwa w danym systemie operacyjnym zawiera niedopuszczalne znaki). Problemy
typu "niebezpiecznie duże użycie stosu" należy rozwiązywać wewnętrznie a
nie poprzez zgłaszanie wyjątków typu "pomieszaj trochę dane, bo się
trafił nieoptymalny/brzegowy przypadek" D

do góry

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

Widziałem implementacje w Pascalu zwykłego Qsorta i iteracyjnego.
Iteracyjny był znacząco szybszy. Nie bez powodu stosuje się w programach
funkcje inline aby nie mieć narzutu na wołanie procedury. W
rekurencyjnej metodzie nie można zrobić inline natomiast mamy tam masę
wywołań. Poza tym łatwiej jest zaimplementować pasek postępu dla
długiego sortowania.

> 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.

W procedurze pascalowej była tablica rzędu 40-tu par i nigdy się do tej
granicy nie zbliżało, był pewien zapas. Dla kilu milionów 20 w
zupełności wystarczało, trzeba było mniej tablicy niż log2(N).
Zostaje przypadek złośliwy, ale wtedy lepiej przełączyć się na heapsort
zamiast zwiększać tablicę.

do góry