Programování - diskusní klub na Lopuchu

Registrace nového uživatele

Návod

Kluby

Archív Lopuchu

Lopuch.cz

Náš Lopuch Vám
vytře zrak

Lopuch.cz

	Klub Programování [ŽP: neomezená] (kategorie Programování) moderuje tvx.
	Archiv

Nastavení klubu

Nastavení práv

Homepage

Anketa

[ 857 ]

<Novější <<<Nejnovější Nejstarší>>> Starší>


	King Born to be king - ... 31.10.2006 21:12	589
	http://en.wikipedia.org/wiki/Bucket_sort http://en.wikipedia.org/wiki/Radix_sort a doma stokrat opsat: naucim se hledat na webu nez budu publikovat do fora...


	Norfin 31.10.2006 20:34	588
	Bucketsort je to, co popsal Bredy, ne?


	King Born to be king - ... 31.10.2006 19:49	587
	decide: to byl jen odhad - mozna zkus ten nejvetsi... jde o to, aby pivot byl dostatecne velky, aby si nevybral prilis male cislo, to by ti bylo nanic... tim ze ho vyberes z vice cisel zmensis pravdepodobnost ze se tohle stane... kdokoliv: BucketSort zni povedome?


	31.10.2006 18:26	586
	pivot?Kingu, ještě ke quicksortu. Říkals, že mám vybrat náhodně 5 pivotů a pak zvolit druhý. Chápu to správně takto?: 1)vyberu pět náhodných prvků aktuálně tříděné části pole 2)z nich vezmu druhý (nejlepš)největší Vysvětli, prosím, proč to mám dělat zrovna takhle, dík.


	Kdokoliv Nevidím důvod dělat cokoliv bezdůvodně. - http://kkl2401.wz.cz 31.10.2006 17:19	585
	Aha, tak to pardon, popletly se mi pojmy. Ale urcite jsme tomu rikali jeste jinak nez counting sort, kdybych si ale vybavil jak.


	31.10.2006 17:03	584
	Kdokoliv 671To co jsi popsal je Counting Sort. Radix sort se u integeru dela tak, ze cisla seradim nejprve podle prvni cifry (nejnizsi vpravo), potrebuju tedy 10 hromadek a podle cifry plnim hromadky. Pak to sesbiram a seradim to podle dalsi cifry a nakonec to seradim podle posledni cifry. Pokud jsem hromadky vzdy sbiral ve stejnem poradi, dostanu serazenou posloupnost. (Uz jste nekdy radili 500 faktur podle cisla? myslim rucne)


	31.10.2006 15:14	582
	Máš pravdu. Existují sice extrémní příklady, kdy to budu muset projít pětkrát celé, ale nebudou asi v reálu nastávat. Až uvidím rozložení hodnot, ještě o tom pouvažuju, ale řekl bych, že ten radix nakonec alespoň teoreticky prohraje. Jestli se dokopu k jeho implementaci a praktickému srovnání, dám vědět, jak to dopadlo. Ještě jednou dík.


	King Born to be king - ... 31.10.2006 13:33	581
	ten radix ale nemusi delat cely! staci ti jen setridit to podle PRVNICH x cifer, respektive napred podle poctu mist, pak staci setridit jen ten pocet kde je k-ty prvek, a ten musis tridit jen do te doby, kdy nebudou vsechna cisla stejna... ale uznavam, ze quicksortFirstK se asi bude psat lepe... ;)


	31.10.2006 13:27	580
	jasně konstanty tam nepatří... Bohužel ty velké hodnoty tam nebudou vždy, takže se na to spoléhat nedá. Když už to tak blbě píšu s těma konstantama, tak to použiju ještě jednou pro N=400 a M=20 je 1) náročnost radix O(7N)~2800 je trošku větší než 2) moje původní metoda O(lg2MN]~O(5N)~2000 a ta je horší než 3) upravený quick sort O(N+Mlg2M)~O(N+100)~500 Hlasuju pro quicksortFirstK


	King Born to be king - ... 31.10.2006 13:26	579
	bavime se o poli 400 pointeru, myslim ze z toho plyne ze tuhle otazku jiz mame vyresenou, jinak souhlas - kdyby je dostaval postupne tak halda je nejlepsi volba ;)


	31.10.2006 13:17	578
	Možná bych se úplně nejdřív zamyslel nad otázkou, jestli budeš vybírat z dat už existujících v paměti, nebo jestli je budeš teprve dostávat odněkud. Pak by totiž stálo za úvahu to dělat průběžně při příjmu dalšího prvku.


	King Born to be king - ... 31.10.2006 12:04	577
	O(7*N) je kapku raritka, konstanty se vetsinou nepocitaji.. ;) jinak ty to nepotrebujes tridit cele, pokud si muzes vsadit na to, ze vsech 20 nejvyssich hodnot bude mezi 100100 a 101000, tak si klidne udelej pole 900 prvku a nahazej to tam, a mas to linearne, primo... pak jedine musis osetrit nejhorsi pripad kdy se ti to tam netrefi a jeste budes muset dohledavat zbyle prvky...


	31.10.2006 11:49	576
	mluvím o verzi radixu, který se dělá postupně pro jednotlivé cifry


	31.10.2006 11:47	575
	oprava1 000 000 .. 1 000 100


	31.10.2006 11:46	574
	Ohledně radixu, hodnoty budou zhruba 0..10000 poměrně hustě a pak něco jako 100000..100100 všechny: Takže pokud řekneme, že to mudou max sedmimístná čísla, radix by to měl za O(7*N) setříděno celé?

[ 857 ]

<Novější <<<Nejnovější Nejstarší>>> Starší>


(c) 2001-2011 Lopuch.cz Kontakt