Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #27062
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Newsgroups | pl.comp.programming |
| Subject | Re: Kiedy qsort zaczyna źle działać? |
| Date | 2015-07-15 23:18 +0200 |
| Organization | ATMAN - ATM S.A. |
| Message-ID | <mo6im9$cqj$1@node2.news.atman.pl> (permalink) |
| References | <mo6d72$n3b$1@node1.news.atman.pl> <mo6i8q$sld$1@node1.news.atman.pl> |
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.
Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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