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.

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

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

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

> 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

 Page 1 of 1 [ 5 post ]

Relevant Pages