English Amiga Board Weird quicksort routine
 Register Amiga FAQ Rules & Help Members List  /  Moderators List Today's Posts Mark Forums Read

 11 November 2008, 22:19 #1 rbw   Posts: n/a Weird quicksort routine (Or perhaps just me being stupid.) I've been trying to understand why I can't get this quicksort routine to work, it was originally a part of the "howtocode" series of articles (that you can find for instance here: http://www.mways.co.uk/amiga/howtocode/text/vectors.php In that version, the quicksort routine is incomplete, i've got my example here: http://www.itsahit.com/ola/qsort/qsort.s What I'm trying to do - is to sort my coordinates (Rotcoords) with respect to Z. The coords are arranged in a linked-list, formed as per description in the qsort rout (at least the way I interpreted them). dc.w nextpointer2, x1, y1, z1 dc.w nextpointer3, x2, y2, z2 . . After the sorting is done; I should have the pointer to the element with the largest Z-factor in d0 and just follow the next pointer to go down the list... but... no.. It seems like the re-ordering of the list makes it stuck in an infinite loop, so that the next pointer is points to the same element again. And that really puzzles me, since the routine is wide spread (and old) and I can't really imagine it being incorrect, or? "dumplist" just moves the z-factor of element1 into d1, second into d2.. to d7. An easier way of debugging is to hex-view the result (in asmone: h (a0) ) I'd appreciate if someone could shed some light on this..
 11 November 2008, 23:34 #2 Kalms Registered User   Join Date: Nov 2006 Location: Stockholm, Sweden Posts: 173 Quick observation: Code: ```permute cmp.w WghtOffs(a5,d3.w),d2 ;entry weight
 12 November 2008, 13:15 #3 Photon Moderator   Join Date: Nov 2004 Location: Hult / Sweden Posts: 4,474 I have a source of a vectorbobs part I made in 1991 that uses 6 top bits of Z-coord+tweaks to not have to clear the "buckets". Bucket sort, hm. Never knew the name existed When was it invented? Ola, Quicksort is great when the number of items is large. If it's like 50-80 polygons you might just use a scan for most distant poly, draw it and mark it as drawn, then scan again for the next poly. Last edited by Photon; 12 November 2008 at 13:21.
 12 November 2008, 15:29 #4 Kalms Registered User   Join Date: Nov 2006 Location: Stockholm, Sweden Posts: 173 An alternative name for bucket sort is "bin sort". It's probably older than the Grand Canyon.
 12 November 2008, 17:33 #5 Samurai_Crow Total Chaos forever!   Join Date: Aug 2007 Location: Ft. Collins, CO USA Age: 43 Posts: 975 If I have to use a comparison sort, I use a natural merge sort. Unlike a quicksort, which degenerates to n^2 passes if you have an already sorted list, it sorts stuff that's in order already using only a single pass. Here's how it works: You go through the list adding every item to a region list and any time you find something out of order, you start a new region. You may have some regions that are one item long and some that are very long. Then on to the merge phase: You check if there are two or more regions on the first region list. If not then you're already sorted. If so, then take the top two regions and compare the top two entries adding the lower one to another region on a second region list. When one of the regions is empty just copy the rest of the other region to the destination region. Once those two regions are empty, remove them from the source region list and take the next two. If you have one region left at the end, just copy it to the destination list. Switch lists and repeat until you have only one sorted region. For a Z-buffer, I wouldn't use a comparison sort though. I'd use a base-16 radix sort.
 12 November 2008, 19:46 #6 rbw   Posts: n/a Thanks a lot guy's, I'll greet you all when the demo is done .
12 November 2008, 21:46   #7
Photon
Moderator

Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,474
Quote:
 Originally Posted by Kalms An alternative name for bucket sort is "bin sort". It's probably older than the Grand Canyon.
Had a look at Wikipedia. Earliest mention is from 1992, but then again it's Wikipedia. Not that ordinary encyclopedias usually care about these things.

Mine bypasses the histogram/scatter phase, improves coord bit precision by one, and needs no clearing of buckets.

But basically, I was just curious who implemented the first working BucketSort() Since I'm into algorithm history.

 Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

 Similar Threads Thread Thread Starter Forum Replies Last Post BlueAchenar Coders. General 4 14 January 2009 17:38 BippyM Coders. General 2 15 July 2007 13:15 MidJasper request.Other 2 03 February 2007 21:10 redblade Coders. General 6 02 June 2006 09:51 Akira Coders. General 4 18 December 2003 00:51

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home News Main     Amiga scene     Retrogaming General Discussion     Nostalgia & memories Support     New to Emulation or Amiga scene         Member Introductions     support.WinUAE     support.WinFellow     support.OtherUAE     support.FS-UAE     support.Hardware         Hardware mods         Hardware pics     support.Games     support.Demos     support.Apps     support.Amiga Forever     support.Amix     support.Other Requests     request.UAE Wishlist     request.Old Rare Games     request.Demos     request.Apps     request.Modules     request.Music     request.Other     Looking for a game name ?     Games images which need to be WHDified abime.net - Hall Of Light     HOL news     HOL suggestions and feedback     HOL data problems     HOL contributions abime.net - Amiga Magazine Rack     AMR news     AMR suggestions and feedback     AMR data problems     AMR contributions abime.net - Home Projects     project.Amiga Lore     project.EAB     project.IRC     project.Mods Jukebox     project.Wiki abime.net - Hosted Projects     project.aGTW     project.APoV     project.ClassicWB     project.Jambo!     project.Green Amiga Alien GUIDES     project.Maptapper     project.Sprites     project.WinUAE - Kaillera Other Projects     project.Amiga Demo DVD     project.Amiga Game Factory     project.CARE     project.EAB File Server     project.CD32 Conversion     project.Game Cover Art         GCA.Feedback and Suggestions         GCA.Work in Progress         GCA.Cover Requests         GCA.Usefull Programs         GCA.Helpdesk     project.KGLoad     project.MAGE     project.Missing Full Shareware Games     project.SPS (was CAPS)     project.TOSEC (amiga only)     project.WHDLoad         project.Killergorilla's WHD packs Misc     Amiga websites reviews     MarketPlace         Swapshop     EAB's competition Coders     Coders. General         Coders. Releases         Coders. Tutorials     Coders. Asm / Hardware     Coders. System         Coders. Scripting         Coders. Nextgen     Coders. Language         Coders. C/C++         Coders. AMOS         Coders. Blitz Basic Off Topic     OT - General     OT - Technical     OT - Entertainment     OT - Sports     OT - Gaming

All times are GMT +2. The time now is 23:06.

 -- EAB3 skin ---- EAB2 skin ---- Mobile skin Archive - Top