Article View: pl.comp.programming
Article #216537Re: Quciksort a najmniejsza liczba odpytywań
From: M.M.
Date: Mon, 25 Nov 2019 04:51
Date: Mon, 25 Nov 2019 04:51
16 lines
2207 bytes
2207 bytes
On Sunday, November 24, 2019 at 9:50:35 PM UTC+1, Tomasz Konstanty Maluszycki wrote: > On Sunday, November 24, 2019 at 8:49:55 AM UTC, Borneq wrote: > > Pytanie z Algorytmów i struktur danych > > Co się zdarzy, gdy funkcja oceniająca będzie dawała dziwne wyniki: > > typu A<B , B<C, ale C<A ? > > Czy w QuickSort zawsze pyta się minimalna ilość razy? > > Ale z drugiej strony, może być początkowe posortowanie takie że > > QuickSort będzie miał złożoność kwadratową, czyli na pewno nie pyta > > minimalna ilość razy. Co wtedy? QuickSort się wykrzaczy? Jak się to objawi? > > [...] > Mała ciekawostka: największym koszmarem quicksorta jest tablica częściowo > posortowana. Trzeba wybierać losowo element 'podziału'. Pozdrawiam
Technical Details
Message-ID:
<70a99d67-186f-4350-bc56-691900aa0f4d@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!wsisiz.edu.pl!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed9.news.xs4all.nl!82.197.223.106.MISMATCH!feeder1.cambriumusenet.nl!feed.tweak.nl!209.85.160.216.MISMATCH!g89no7848655qtd.0!news-out.google.com!p4ni1793qtu.1!nntp.google.com!g89no7848650qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mailReferences:
<5dda4431$0$31099$65785112@news.neostrada.pl> <ed09b514-3a95-4204-8d0b-51c5a8f54ca4@googlegroups.com>Show Full Headers
Complete Article Headers
X-Received: by 2002:a37:9b90:: with SMTP id d138mr25161407qke.450.1574657518196; Sun, 24 Nov 2019 20:51:58 -0800 (PST) X-Received: by 2002:ad4:4682:: with SMTP id bq2mr3368551qvb.215.1574657518014; Sun, 24 Nov 2019 20:51:58 -0800 (PST) Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!wsisiz.edu.pl!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed9.news.xs4all.nl!82.197.223.106.MISMATCH!feeder1.cambriumusenet.nl!feed.tweak.nl!209.85.160.216.MISMATCH!g89no7848655qtd.0!news-out.google.com!p4ni1793qtu.1!nntp.google.com!g89no7848650qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: pl.comp.programming Date: Sun, 24 Nov 2019 20:51:57 -0800 (PST) In-Reply-To: <ed09b514-3a95-4204-8d0b-51c5a8f54ca4@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=159.205.150.241; posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj NNTP-Posting-Host: 159.205.150.241 References: <5dda4431$0$31099$65785112@news.neostrada.pl> <ed09b514-3a95-4204-8d0b-51c5a8f54ca4@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <70a99d67-186f-4350-bc56-691900aa0f4d@googlegroups.com> Subject: Re: Quciksort a najmniejsza liczba odpytywań From: "M.M." <mmarszik@gmail.com> Injection-Date: Mon, 25 Nov 2019 04:51:58 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit