Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #27057
| From | Pit <nospam@sdf.lonestar.org> |
|---|---|
| Newsgroups | pl.comp.programming |
| Subject | Re: Kiedy qsort zaczyna źle działać? |
| Date | 2015-07-15 20:55 +0000 |
| Organization | ATMAN - ATM S.A. |
| Message-ID | <slrnmqdi53.3uo.nospam@nc10.lan> (permalink) |
| References | <mo6d72$n3b$1@node1.news.atman.pl> |
Dnia 15.07.2015 Borneq <borneq@antyspam.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).
Back to pl.comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread
Re: Kiedy qsort zaczyna źle działać? Pit <nospam@sdf.lonestar.org> - 2015-07-15 20:55 +0000
Re: Kiedy qsort zaczyna źle działać? Borneq <borneq@antyspam.hidden.pl> - 2015-07-15 23:06 +0200
Re: Kiedy qsort zaczyna źle działać? Borneq <borneq@antyspam.hidden.pl> - 2015-07-15 23:08 +0200
Re: Kiedy qsort zaczyna źle działać? bartekltg <bartekltg@gmail.com> - 2015-07-15 23:11 +0200
csiph-web