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..

[Kalms]

Quick observation:

permute        
		cmp.w WghtOffs(a5,d3.w),d2 ;entry weight<pivot weight?
		ble.s lower
		move.w d6,NextOffs(a5,d3.w) ;Insert BEFORE Nentry  [1]
		addq.w #1,d4 ;increase size of list 1
		move.w d3,d6 ;Set new Nentry
		bra.s done ;Continue the loop...
lower		
		move.w NextOffs(a5,d0.w),NextOffs(a5,d3.w)  [2]
		move.w d3,NextOffs(a5,d0.w) ;insert AFTER first entry
		addq.w #1,d5 ;size of list 2
done		
		move.w NextOffs(a5,d3.w),d3 ;Get next entry   [3]
		dbf d1,permute

The above loop will iterate through one list, and build two new lists. However, locations marked [1] and [2] will stomp over the next-ptr which is subsequently read at [3]. Thus, fetch the old next-ptr at the beginning of the permute-loop, and keep it around in a register, so [1] and [2] don't affect you when you want to go to the next element in the original list.

Other than that, well, I've never seen qsort implemented using singly linked lists so I can't vouch for the validity of the rest of the code. Wish you luck.


[edit] By the way, if you really are sorting polygons then you probably don't need exact sorting results. Create 256 linked lists (heretofore referred to as "buckets"). Initialize them all to be empty. Go through your set of items, and depending on the sort key (say, the upper byte of the Z-value), throw the item into the corresponding bucket.

Once this is done, go through the buckets in order and render their contents.

This gives you sorting which is accurate on 8 of the 16 bits of your Z values. Works "good enough" for low-polygon 3D graphics (and this is pretty much how many PS1 games did their sorting, along with various tweaks). The algorithm is normally referred to as "bucket sort", by the way.

Other algorithms of interest are radix sort + insert counting (aka counting sort). Radix sort + insert counting, or radix sort + bucket sort, allows you to sort on the full key (be it 16 bits or 32 bits) in linear time.

[Photon]

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.

[Kalms]

An alternative name for bucket sort is "bin sort". It's probably older than the Grand Canyon.

[Samurai_Crow]

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.

Thanks a lot guy's, I'll greet you all when the demo is done .

[Photon]

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.