qsort algoritm and ARM library 
Author Message
 qsort algoritm and ARM library

Hi there!
Does anybody know if the qsort algorithm in the ARM library is implemented
as recursive algorithm or not. I'm not very keen on using a recursive
algorithm in an embedded environment with limited memory resources.

(The compiler I'm using is:    Norcroft  ARM C vsn 4.91 (ARM Ltd SDT2.51)
[Build number 128])

Kind regards,
H.G.Gestsson.



Mon, 15 Dec 2003 19:47:05 GMT  
 qsort algoritm and ARM library

Quote:
>Hi there!
>Does anybody know if the qsort algorithm in the ARM library is implemented
>as recursive algorithm or not. I'm not very keen on using a recursive
>algorithm in an embedded environment with limited memory resources.

>(The compiler I'm using is:    Norcroft  ARM C vsn 4.91 (ARM Ltd SDT2.51)
>[Build number 128])

>Kind regards,
>H.G.Gestsson.

This isn't really topical in comp.lang.c... as long as qsort does what it's
meant it doesn't matter how it's done.

To get this info, try posting to an ARM specific group, or (if you're
lucky) one specific for the compiler. Alternatively, contact the company
directly (email should suffice).

A possibly better idea is to just ditch using qsort and write your own
sorting routine that meet the requirements - as far as the C standard goes
the only requirement is the function performed by qsort rather than any
limitations on how it performs.

Good luck on your search.

Ian Woods.



Tue, 16 Dec 2003 03:14:33 GMT  
 qsort algoritm and ARM library
Hi

I think qsort() is usually recursive; here are two other methods you may use
instead of qsort:

void shell(int arr[], int amount)
{
 int k, dist, change = 1;
 dist = amount / 2;
 do
 do
 {
  change = 0;
  for (k = 0; k < (amount - dist); k++)
   if (arr[k] > arr[k + dist])
   {
      swap(&(arr[k]), &(arr[k + dist]));
    change = 1;
  }
 }
   while (change);
 while ( (dist /= 2) > 0);

Quote:
}

void bubble(int arr[], int amount)
{
 int ok, i, temp;
 do
 {
  ok = 1;
  for (i=0; i < amount-1; i++)
  {
    if (arr[i] > arr[i+1])
    {
      swap(&(arr[i]), &(arr[i+1]));
  ok = 0;
  }
  }
 }
  while (!ok);

Quote:
}

/* swap
void swap(int* a, int* b)
{
 int temp;
 temp = *a;
 *a = *b;
 *b = temp;
Quote:
}

*/


Tue, 16 Dec 2003 12:23:21 GMT  
 qsort algoritm and ARM library

Quote:
> I think qsort() is usually recursive; here are two other methods you may use
> instead of qsort:

well, i dont know about that. depends on what you mean by 'usually' :)
while i dont want to post the source code from VxWorks (i doubt
that would be too legal) let me just say that it is not recursive.
Of course, it proves nothing, except the fact that you cant really
figure out how arm people did it from the 'usually' statement.

denis



Wed, 17 Dec 2003 01:29:30 GMT  
 qsort algoritm and ARM library

Quote:

> > I think qsort() is usually recursive; here are two other methods you may
use
> > instead of qsort:

> well, i dont know about that. depends on what you mean by 'usually' :)

qsort() suggests that the "quicksort" algorithm is used, which is naturally
recursive (it divides the array along a pivot point, and then sub-divides).

qsort() can however be implemented with some other algorithm and remain ANSI
compliant, and of course any recursive function in C can be rewritten so
that it doesn't use recursion.

However it is perfectly true to say that qsort() is usually recursive.



Wed, 17 Dec 2003 17:56:57 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. WANTED: Safety Polygon Algoritm or a Algoritm Resource Page on the Net

2. qsort bug in Microsoft library?

3. Bug in qsort (Plauger Standard C Library)

4. Bug in qsort (Plauger Standard C Library)

5. Example of bug in qsort from Plauger's library

6. What is algoritm of hashing?

7. otsu threshold algoritm

8. patricia algoritm

9. Best algoritm homepage

10. Dijstra Algoritm

11. Algoritm newsgroups ?

12. CRC Algoritm wanted

 

 
Powered by phpBB® Forum Software