Új hozzászólás Aktív témák

• Chipi333 csendes tag

  #3144

  #3143 uraga

  2012-04-25 11:28:52

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  Chipi333

  csendes tag

  #3143 uraga

  #3143 uraga

  Igen, eddig én is eljutottam, abból ha az intervallumokat rendezed, nem lesz rendezett listád. Akkor sem ha a végén n elemszámú listában n darab intervallumod lesz. Max akkor lenne a végén rendezett ha még a rendezett intervallumokat összefésülnénk, ami igen hatékony de egy TimSort nevű rendezés sokkal jobban csinálja, szóval itt nem ez a lényeg. A lényeg ott lenne, hogy a min és max elemek közé úgy pakoljuk be az elemeket, hogy valamilyen csoportosításba kerüljenek mint a BucketSortnál pl 10-20, 20-30, 40-50- ig stb. Ezután az intervallumok rendezésével akár rekurzivan egy rendezett sorozatot kapnánk a végén. De mivel a leirásban az is szerepel hogy egyenlő elem számú intervallumokra osztja, tényleg nem értem hogy csinálja, hogy a végén rendezve is legyen az egész lista, ne csak az intervallumok.

  A leírás elég egyértelmű. Gyakorlatilag egy quicksort, csak nem egy hanem több pivotot használ -> 2 helyett több partíciót csinál az elemekből aztán rekurzívan azokat is rendezi, és így tovább. Ha nem ismered a quicksortot akkor először azt nézd meg, és utána érteni fogod.

  Aműgy ebbe a topicba szerintem jobban illene a téma: http://itcafe.hu/tema/programozas_forum/hsz_1-50.html

Új hozzászólás Aktív témák