Jag behöver ett kod exempel (i java) på ”bucket sort”. Har letat runt men hittar inget bra. Någon bra sida där man kan hitta färdig kod exempel?
Söker en kod exempel för ”bucket sort”
10 svar · 415 visningar · startad av Rocket
Godtycklig lärobok i java eller algoritmer.
Men idén är enkel: (Varefter vänstertecknad(!) beskriver radix sort med glatt hjärta! :r Just då i alla fall... :( )
Sortera in alla tal på samma sista siffra i en "bucket". Slå ihop "bucketarna i ordning.
Sortera in alla tal på samma näst sista siffra i en "bucket". osv...
19 24 3 7 98 92 21 117 15
blir
21 | 92 | 3 | 24 | 15 | 7 117 | 98 | 19
sammanslaget
21 92 3 24 15 7 117 98 19
nästa vända:
3 7 | 15 117 19 | 21 24 | 92 98
sammanslaget
3 7 15 117 19 21 24 92 98
sista vändan:
3 7 15 19 21 24 92 98 | 117
sammanslaget
3 7 15 19 21 24 92 98 117
Klart!
Så långt är jag med :) Jag skulle behöva kod så att jag kan testa att sortera data med bucketsort och se hur effektiv den är.
Provat att bara söka på "BucketSort.java" på Google? Du är ju garanterat inte den förste som skriver en sån ..
Här tex: http://www.geocities.com/er-chan/BucketSort.java (applet iofs men det kan du ju pilla bort.)
Rocket skrev:
Så långt är jag med :) Jag skulle behöva kod så att jag kan testa att sortera data med bucketsort och se hur effektiv den är.
Humm, snabbheten beror ju på HUR du väljer att implementera dina buckets. Det är ju ett designval du måste göra. Särskilt om du jämför effektivitet mellan olika sökmetoder är det ju inte oväsentligt. Då är det nog ingen bra idé att använda första bästa implementation man hittar.
aasah skrev:
Då är det nog ingen bra idé att använda första bästa implementation man hittar.
Så vart kan man hitta några bra exempel på bucket sort så att man har lite att välja bland. Jag sök på "bucketsort.java" i google men det är svårt att hitta något bra, mykcet känns mindre seriöst. Det måste ju finnas bra arkiv/sammlingar där man kan hitta fördiga kod exempel.
Läroböcker i effektiva algoritmer, kanske? Jag vet inte...
inte svar på frågan men kan inte låta bli att tipsa om denna sidan om någon har missat den:
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
Rocket skrev:
... aasah: Är det inte radix sort du har beskrivit ovan?
:r :r Jooo! :( Ledsen! Jag brukar alltid blanda ihop bucket sort och radix sort. (Skälet är en superfånig lärobok där de båda presenteras under rubriken "bucket sorts", borde ha kollat innan jag svarade.)
Dock är min kommentar fortfarande giltig. Men dessutom kan resultatet bero på hur du sorterar dina buckets, dvs vilken sorteringsalgoritm du använder inom bucketarna. I alla fall om du vet något om hur de data du sorterar brukar vara fördelade så kan du ju kanske slippa "värsta fallet" - annat än undantagsvis - om du väljer inre sorteringsalgoritm klokt. Sedan beror ju snabbheten också på hur många buckets du väljer, dvs hur många tal som förväntas hamna i varje bucket.... Det är många faktorer att ta ställning till. (Alternativet är väl möjligen en teoretisk jämförelse.)
beiker:
Tack för länken, helt ok.
aasah:
Jag läste någonstans (mins inte riktigt vart) att man ofta använder insertion sort för att sortera sina buckets. Det känns som att det är en onödigt tidskrävande lösning då en bucket alltid är sorterad när ett nytt element ska sättas in. Det bästa vore att hitta rätt plats med en binary search och trycka in det nya elementet där.
Jag har i alla fall hittat en kod som var ok och efter lite tips från den så har det ordnat sig. Min bucket sort är snabbare än quick sort och insertion sort på stora datamängder och det stämmer bra överens med teorin.