2.29.2012

Bucket Sort

I took the time to implement a few list macros that become useful for sorting the sprites in IGE with more performance. Previously I've used some sort of custom, admittedly bad n^2 sorting I'm not really proud of - even Insertion Sort was faster in the best case complexity. However, I thought about how to split the whole stuff into smaller sortings and noticed that all I'd need is a bucket sort algorithms with insertion sort for each bucket. I must admit that I like insertion sort because it doesn't require recursion and is trivial to implement with linked lists. Combined with an array of bucket lists, it works quite well on static memory and I'm wondering what sort of performance boost I might get when choosing a lot of buckets for a lot of z coordinates. The idea is to distribute the distribute so that they cover the area between the min max of all z values in the display list. Thus, one only needs to create a lot of buckets and the mapping is done. I like the idea. Especially because one bucket set is enough to feed to recursive render algorithm. Gonna implement this and do some Realease 0b or so. If I can implement this that quick, I definitely want to do it before writing my internship application to put insert even more sprites for the atom demo.

No comments: