Article View: pl.comp.bazy-danych
Article #47Re: Algorytm sortowania -???
From: l... Jarek Lis
Date: Mon, 12 Feb 1996 00:00
Date: Mon, 12 Feb 1996 00:00
35 lines
2233 bytes
2233 bytes
Lukasz Sznuk (lsz...@laser.mimuw.edu.pl) wrote: : Jerzy Tarasiuk wrote: : > O gorszych wynikach decyduje nie najgorszy przypadek, ktorego : > prawdopodobienstwo jest 1/n!, ale wystapienie znaczacej ilosci : > nieoptymalnych podzialow, co jakos calkiem czesto mi wychodzilo. : Tu sie zgadzam... ale jezeli za kazdym razem wezmiemy mediane jako : element wzgledem ktorwgo bedziemy dzielic, to ciag podzialow bedzie : optymalny. He, he -tylko znajdziesz te mediane? Najszybszy znany algorytm stosuje technike bardzo podobna do quicksorta. ... : [...] : > A nie, nie tak prosto: nie wystarczy jednokrotne znalezienie : > mediany (tak sie nazywa w ksiazce Wirtha element n/2), trzeba : > potem dzielic dalej, wynik jest O(n^2)... :-( : Troche chory jestem, wiec moze zle licze, ale mi n^2 nie wychodzi... A ile zalozyles na znalezienie mediany? I czy ten algorytm nie podlega podebnemu problemowi co quicksort - przy zlisliwych danych dziala n^2.. Jeszcze jeden problem - ile by nie wydluzyl, heapsort jest bardzo blisko. Jak pisalem - w praktycznych wynikach heapsort jest okolo dwa razy gorszy niz quicksort. policz mediane - qs bedzie wolniejszy. A czas hs jest bardzo stabilny... Jaroslaw Lis +------------------------------------------------------------------------+ | l...@ict.pwr.wroc.pl | Institute of Engineering Cybernetics | | tel 48-71-202636 | Technical University of Wroclaw, Poland | | fax 48-71-203408 or 517398 | | +------------------------------------------------------------------------+
Technical Details
Message-ID:
<4foghr$6n6@okapi.ict.pwr.wroc.pl>Path:
mbox-mo1.pugleaf.net!unknown!not-for-mailReferences:
<4et6u0$kg5@bnet.fuw.edu.pl> <JT.88.31127DC2@zfja-gate.fuw.edu.pl> <4f19rs$4j2@okapi.ict.pwr.wroc.pl> <JT.121.31161111@zfja-gate.fuw.edu.pl> <3119949E.477A@laser.mimuw.edu.pl> <JT.122.311F6498@zfja-gate.fuw.edu.pl> <31201215.2339@laser.mimuw.edu.pl>Show Full Headers
Complete Article Headers
From: l...@okapi.ict.pwr.wroc.pl (Jarek Lis) Subject: Re: Algorytm sortowania -??? Date: 1996/02/12 Message-ID: <4foghr$6n6@okapi.ict.pwr.wroc.pl> X-Deja-AN: 139246083 references: <4et6u0$kg5@bnet.fuw.edu.pl> <JT.88.31127DC2@zfja-gate.fuw.edu.pl> <4f19rs$4j2@okapi.ict.pwr.wroc.pl> <JT.121.31161111@zfja-gate.fuw.edu.pl> <3119949E.477A@laser.mimuw.edu.pl> <JT.122.311F6498@zfja-gate.fuw.edu.pl> <31201215.2339@laser.mimuw.edu.pl> organization: Technical University of Wroclaw, Poland newsgroups: pl.comp.bazy-danych MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit