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