Re: attempt at qsort implementation

From: pete (pfiland_at_mindspring.com)
Date: 09/29/04 

Date: Wed, 29 Sep 2004 00:59:57 GMT

buda wrote:
>
> I had some spare time and decided to try to implement the standard library
> qsort. This is a pretty simpleminded attempt, but it seems to be working. I
> have to point out that efficiency is not at all an issue for me, and this is
> purely a toy, so to speak. I'm quite aware that this is not the quickest way
> to implement the quicksort algorithm, but I basically just wanted to try to
> make a "generic function". I tested it with a few arrays of structures
> containing all sorts of types (this, ofcourse, doesn't mean that it's
> correct, even by a long shot :).
> I would appreciate any and all constructive
> comments. The code below is a snippet. All the necessary headers are
> included and uchar is a typedef for unsigned char.
> Thank you.

This implementation will probably run out of memory
on large already ordered arrays.
If the array is in order prior to sorting,
then (x-t)/sz will be equal to count - 1
and you'll wind up with about count - 1, levels of recursion.
If count is large, the function could crash the program.

> void do_swap_(void *a, void *b, size_t sz)
> {
> uchar t;
> uchar *i = a;
> uchar *j = b;
>
> while (sz) {
> t = *i;
> *i++ = *j;
> *j++ = t;
> --sz;
> }
> }
> void quick_sort(void *v, size_t count,
> size_t sz, int (*cmp)(const void *,
> const void *))
> {
> uchar *t = v;
> uchar *x, *y;
> uchar *r;
>
> if (count) {
> x = y = t;
> r = t+(count-1)*sz;
> for(; y<r; y += sz)
> if (cmp(y, r)<0) {
> do_swap_(x, y, sz);
> x += sz;
> }
> do_swap_(x, r, sz);
> quick_sort(t, (x-t)/sz, sz, cmp);
> quick_sort(x+sz, count-(x-t)/sz - 1, sz, cmp);
> }
> } 

-- 
pete