#35945 - Celeryface - Sun Feb 13, 2005 1:44 pm
Hi there,
I'm trying to decide on an algorithm to use for the sorting portion my A* implementation (Sorting the nodes to have the highest F value at the top of the heap). I will be using C, for reference.
I have implemented A* using C++ and the priority queue (heap sort) from STL on the PC, but I want to use C for the GBA implementation.
Can anyone recommend which sorting algorithm I should use in C that will be fast on the GBA to sort the nodes?
Thanks in advance. :)
#35946 - sasq - Sun Feb 13, 2005 2:02 pm
qsort()
part of the standard c-library and pretty fast for general cases.
#35948 - Celeryface - Sun Feb 13, 2005 2:34 pm
| sasq wrote: |
qsort()
part of the standard c-library and pretty fast for general cases. |
For qsort(), can you specify a comparison function so that it can compare a certain value within a structure?
#35952 - ymalik - Sun Feb 13, 2005 3:48 pm
Yes.
#35953 - Celeryface - Sun Feb 13, 2005 3:50 pm
#35990 - DiscoStew - Sun Feb 13, 2005 10:15 pm
To use qsort() on the GBA, what is needed (like what files and such need to be included)? Also, how much memory would such a function take up, and could it be implemented into IWRAM? I'm currently using my own sorting algorithm that I think runs pretty well, but I'm open to anything faster.
_________________
DS - It's all about DiscoStew
#35992 - Miked0801 - Sun Feb 13, 2005 10:18 pm
Howe many nodes are you sorting?
#36003 - Celeryface - Mon Feb 14, 2005 12:23 am
| Miked0801 wrote: |
| Howe many nodes are you sorting? |
The node grid array would be 32x32 max.
#36029 - sasq - Mon Feb 14, 2005 11:09 am
qsort sorts "in place" and does not take any extra memory. That's also it's weekness since it uses memcpy to move things around which is a overhead you may not want when you can just sort pointers and read/write them without the function-call overhead.
A good way is to use the source of qsort() directly, make it work as it is and then maybe eliminate the memcpy() if necessary.
#36051 - tepples - Mon Feb 14, 2005 5:58 pm
| sasq wrote: |
| qsort sorts "in place" and does not take any extra memory. |
Not necessarily, for two reasons: - qsort() implemented as Quicksort uses a data-size-dependent amount of stack space. On the other hand, Metrowerks CodeWarrior for Mac implemented qsort as Heapsort, a true in-place sort that takes constant extra memory.
Learn more about sorting algorithms - Your comparison function could be written such that qsort() does in fact sort pointers as you suggest. This would involve dereferencing each pointer inside the comparison function.
| Quote: |
| That's also it's weekness since it uses memcpy to move things around which is a overhead you may not want when you can just sort pointers and read/write them without the function-call overhead. |
If you can fit your comparison function into five registers, the function-call overhead on ARM isn't nearly as bad as it is on x86.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#36054 - sasq - Mon Feb 14, 2005 6:19 pm
This is what I use in pogoshell; it's only slightly modified from something I found on the net. It does need enough stack for recursive calls to partition() so you're right about it needing more memory.
| Code: |
static char *tmp_item;
static int item_size;
static int (*cmp_func)(void *a, void *b);
static int partition(char *a, int low, int high)
{
int left, right, pivot;
char *pivot_item;
pivot_item = &a[low * item_size];
pivot = left = low;
right = high;
while(left < right)
{
// Move left while item < pivot
while(cmp_func(&a[left * item_size], pivot_item) <= 0) left++;
// Move right while item > pivot
while(cmp_func(&a[right * item_size], pivot_item) > 0) right--;
if(left < right)
{
// Swap elements
memcpy(tmp_item, &a[left * item_size], item_size);
memcpy(&a[left * item_size], &a[right * item_size], item_size);
memcpy(&a[right * item_size], tmp_item, item_size);
}
}
// right is final position for the pivot
memcpy(tmp_item, pivot_item, item_size);
memcpy(&a[low * item_size], &a[right * item_size], item_size);
memcpy(&a[right * item_size], tmp_item, item_size);
// low -> right-1 AND right+1 -> high
if((right-1) > low)
partition(a, low, right-1);
if(high > (right+1))
partition(a, right+1, high);
return right;
}
void qsort(void *array, int count, int size, int cf(void *a, void *b))
{
cmp_func = cf;
item_size = size;
tmp_item = malloc(size);
partition((char *)array, 0, count-1);
free(tmp_item);
}
|
#36077 - Celeryface - Mon Feb 14, 2005 9:46 pm
Would a heapsort work well on the GBA?
http://en.wikipedia.org/wiki/Heapsort
#36080 - tepples - Mon Feb 14, 2005 10:06 pm
Yes. In theory, best-first search algorithms such as A* just need a selection, not a sort, so you could use heapsort to sort the elements at first and then later, as an optimization, use the binary heap code you already have as a priority queue.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#36081 - Celeryface - Mon Feb 14, 2005 10:10 pm
| tepples wrote: |
| Yes. In theory, best-first search algorithms such as A* just need a selection, not a sort, so you could use heapsort to sort the elements at first and then later, as an optimization, use the binary heap code you already have as a priority queue. |
Have you seen any implementations in C for the binary heap?
#36106 - Miked0801 - Tue Feb 15, 2005 2:09 am
Shell sort is my current favorite - but only because I wrote a fast ARM friendly version :)