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:37 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<mo6jq3$u9f$1@node1.news.atman.pl> (permalink)
References	<mo6d72$n3b$1@node1.news.atman.pl> <mo6i8q$sld$1@node1.news.atman.pl> <mo6im9$cqj$1@node2.news.atman.pl>

Show all headers | View raw

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

Back to pl.comp.programming | Previous | Next — Previous 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