-
X-Received: by 2002:a05:620a:13d1:: with SMTP id g17mr22424734qkl.313.1574610154135;
Sun, 24 Nov 2019 07:42:34 -0800 (PST)
X-Received: by 2002:a05:620a:13d1:: with SMTP id g17mr22424734qkl.313.1574610154135;
Sun, 24 Nov 2019 07:42:34 -0800 (PST)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!wsisiz.edu.pl!goblin2!goblin1!goblin.st
u.neva.ru!g89no5972682qtd.0!news-out.google.com!g53ni1038qtg.0!nntp.google.com!
g89no5972670qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-fo
r-mail
Newsgroups: pl.comp.programming
Date: Sun, 24 Nov 2019 07:42:33 -0800 (PST)
In-Reply-To: <5dda4431$0$31099$65785112@news.neostrada.pl>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=83.25.207.226;
posting-account=f7iIKQoAAAAkDKpUafc-4IXhmRAzdB5r
NNTP-Posting-Host: 83.25.207.226
References: <5dda4431$0$31099$65785112@news.neostrada.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <5...@g...com>
Subject: Quciksort a najmniejsza liczba odpytywań
From: g...@g...com
Injection-Date: Sun, 24 Nov 2019 15:42:34 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:214480
[ ukryj nagłówki ]Dla prostoty weźmy Haskellową implementację (pseudo) quicksorta:
qsort [] = []
qsort (h:t) = (qsort [x|x<-t, x<h]) \
++[h]++(qsort [x|x<-t, x>=h])
Jeżeli tylko
x >= y <=> ~(x < y)
i jeżeli każde wywołanie x < y daje tę samą wartość, to lewa i prawa strona listy
będzie każdorazowo malała przy kolejnych wywołaniach rekurencyjnych (bo są rozłączne,
i wyciągamy z listy jeden element, h).
Dlatego brak przechodniości operatora < nie powinna mieć wpływu na to, czy algorytm
się zakończy.
W prawdziwym quicksorcie jest lepiej, bo tam wywołujesz funkcję porównującą tylko raz
na iterację dla każdego elementu, i przerzucasz elementy na lewo i prawo od pivota.
Ale schemat rekursji jest dokładnie taki sam.
Rezultat będzie oczywiście niezdefiniowany, ale algorytm się zakończy.
Następne wpisy z tego wątku
- 24.11.19 21:50 Tomasz Konstanty Maluszycki
- 25.11.19 05:51 M.M.
- 25.11.19 16:23 Borneq
Najnowsze wątki z tej grupy
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-04-22 Re: Głośniki
- 2024-04-22 Velobank -- KK Mastercard
- 2024-04-22 dwie nastolatki w radiowozie
- 2024-04-22 Detektor
- 2024-04-22 Warszawa => Senior IT Recruiter <=
- 2024-04-22 Wrocław => Mid PHP Developer (Laravel) <=
- 2024-04-22 Berlin => IT Systems Administrator and Customer Support Engineer <=
- 2024-04-22 Warszawa => Senior Software Engineer PHP (BillPro) Contractor <=
- 2024-04-22 Warszawa => Technical Lead ( (Java Background)) <=
- 2024-04-22 Re: Może tutaj się uda: [NTG] Elewacja / dziurawa Churka
- 2024-04-22 Wrocław => Head of Sales (IT services/products field) <=
- 2024-04-22 Warszawa => Senior IT Recruiter <=
- 2024-04-22 Warszawa => Expert Recruiter 360 stopni <=
- 2024-04-22 Gdańsk => Kierownik Działu Spedycji Międzynarodowej <=
- 2024-04-22 Warszawa => Key Account Manager (HR Services) <=