#85917 - knight0fdragon - Sat Jun 03, 2006 3:23 am
what algorithm would be best with the DS
right now im using selection sort, I would like to use quick sort, but im worried about the recursion
so what methods do others prefer
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#85918 - sajiimori - Sat Jun 03, 2006 3:53 am
Quicksort can be done iteratively. There are tons of implementations out there.
#85919 - tepples - Sat Jun 03, 2006 4:28 am
Quicksort can degrade to O(n^2) for pathological cases. By the time you've selected pivots to avoid the obvious pathological cases, you've already added enough overhead to switch to Heapsort. Heapsort and Shell sort give good guarantees of maximum runtime, which is important in a real-time environment.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#85930 - sajiimori - Sat Jun 03, 2006 6:48 am
The expected rarity of pathological cases, combined with the non-fatal (though undesirable) effect of dropping a frame during gameplay might make average-case performance the deciding factor, tipping the balance in favor of quicksort.
If speed becomes a problem, try some different methods. For now, do whatever's easiest. For DS games, I've never had the need to replace a sorting algorithm for efficiency reasons. It just never came up.
#85995 - spencer723 - Sat Jun 03, 2006 7:09 pm
I find Merge sorts are extremely fast, but I don't really know how much CPU speed you will need for that
#86007 - sniper - Sat Jun 03, 2006 8:03 pm
radixsort is also good even for less than 1000 entries.
#86023 - tepples - Sat Jun 03, 2006 11:24 pm
| spencer723 wrote: |
| I find Merge sorts are extremely fast, but I don't really know how much CPU speed you will need for that |
Merge sort is as fast as the good case of Quicksort, and it's likely to be more cache friendly (because of the linear access), but it uses enough space for a second copy of the data set.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#86058 - knight0fdragon - Sun Jun 04, 2006 3:31 am
i was always under the assumption that radix sort was just not efficient from a computational stand point, where as for people and machines it is really fast
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#86120 - tepples - Sun Jun 04, 2006 3:25 pm
The original PlayStation uses bucket sort, a special case of radix sort, for z-sorting 3D triangles.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#86465 - yackom - Wed Jun 07, 2006 11:45 am
quicksort is the best sorting algorithm on adverage.. the problem is that if your using large datasets (why in the hell would use sort something large on the ds? i dont know) you might blow the stack it has adverage case O(logn) stack space, and worse case O(n).
if you do have problems with that i suggest using in-situ merging algorithms with take constant O(1) space complexity. Though the challenge in getting one working is much higer.
edit:
also bucketsort does have linear time, it requires a block of memory the size of the domain of the data. which is unlikely to be the case since the ds has very limited amounts of memory
#86505 - knight0fdragon - Wed Jun 07, 2006 4:47 pm
it involves some compression routines im writing, so depending on what the data is it may vary. I am going with the iterative quick sort, I will try to implement the radix sort if memory is allowed
| yackom wrote: |
quicksort is the best sorting algorithm on adverage.. the problem is that if your using large datasets (why in the hell would use sort something large on the ds? i dont know) you might blow the stack it has adverage case O(logn) stack space, and worse case O(n).
if you do have problems with that i suggest using in-situ merging algorithms with take constant O(1) space complexity. Though the challenge in getting one working is much higer.
edit:
also bucketsort does have linear time, it requires a block of memory the size of the domain of the data. which is unlikely to be the case since the ds has very limited amounts of memory |
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#86926 - silent_code - Sat Jun 10, 2006 5:29 pm
normally merge sort is cool, becuase once the data is presorted (like after the first sort) it doen't have to do much comparsions on the data set. the downside is the memory requirements...
iterative quicksort sounds interesting for the nds... i wonder how it performs? does someone have any implementations on the nds to compare the best / worst / average / presorted cases of each algo?
#86930 - Dwedit - Sat Jun 10, 2006 6:00 pm
You don't really need to duplicate the data for mergesort. Maybe a really bad implementation would do that. But in an implemetation I used which sorted a bunch of strings, I used two tables of ints, each representing the array index of a string. The table of ints needed to be duplicated, but not the strings themselves.
I specifically chose iterative mergesort because of its near zero stack usage.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."
#86943 - Mighty Max - Sat Jun 10, 2006 9:29 pm
This implementation DUPLICATES the data it sorts. You just shifted what the data is. In your case it is not needed that the strings are really sorted, only the indexes, which you doubled.
There might be other cases you actually need strings to be in the correct order (i.e. to speed up things in sequential accessed medias, alltho you'd do something else here too)
To the question itself, i'm in the opinion that the sorting algorithm should be selected by problem, not on what device it runs (on RAMs, which the DS is)
_________________
GBAMP Multiboot
#86950 - knight0fdragon - Sat Jun 10, 2006 10:27 pm
well the one thing i noticed is that large arrays in functions end up crashing my code, so perhaps theres a limit to the stack space that can cause problems with quicksort. data i am sorting is prob on avg 6k
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#86987 - silent_code - Sun Jun 11, 2006 5:43 am
please feel free to correct me, but the standard implementation of quicksort is quite bad with presorted data in terms of comparsons. it's truely quick with unsorted datasets... so check for alternatives, no matter what sorting algo "sounds" the best (and quick doesn't mean it's ALLWAYS quick).
you might need to introduce other data structures.
some keyword would be a "red black tree". don't ask me, i just heard/read it being mentioned somewhere. some guy said/wrote he used it for sorting onscreen object for drawing order. it was a 2d-isometric-ish game if i remember right. don't know what hardware/platform it was designed for. maybe it was some article on the net, i really don't remember. might be interesting looking into it, though.
#86991 - knight0fdragon - Sun Jun 11, 2006 6:18 am
man i want to stay away from red black trees, not becuase of the algorithm, but because of the teacher that taught me it and the horrors and nightmares that I went though for 4 years
_________________
http://www.myspace.com/knight0fdragonds
MK DS FC: Dragon 330772 075464
AC WW FC: Anthony SamsClub 1933-3433-9458
MPFH: Dragon 0215 4231 1206
#87015 - tepples - Sun Jun 11, 2006 1:17 pm
AA trees are simpler than red-black trees and with about the same performance, and there is public domain source code for them.
But if you're doing sorting where you'll read out the values in order, you don't want a tree but a priority queue, that is, a heap.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.