English Amiga Board - View Single Post

Kalms · 11 November 2008, 22:34

Quick observation:

Code:

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.

11 November 2008, 22:34	#2
Kalms Registered User Join Date: Nov 2006 Location: Stockholm, Sweden Posts: 237	Quick observation: Code: 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. Last edited by Kalms; 11 November 2008 at 22:45.