Re: Quicksort

On Jan 8, 2:56 pm, "cr88192" <cr88...@xxxxxxxxxxx> wrote:
"user923005" <dcor...@xxxxxxxxx> wrote in message

news:5888dd6d-f82f-47a9-8f32-ca1cc08cff9d@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jan 8, 4:29am, "cr88192" <cr88...@xxxxxxxxxxx> wrote:> <robertwess...@xxxxxxxxx> wrote in message

[snip]

<
Note: I am not sure about proper quoting here, since the post I am
replying to appeared to be missing a level of quote indicators.



Outlook Express is giving me crap...
me being too lazy to switch to a different newsreader, quote things as
above.
I did not innovate this style of quotes though, but have seen similar
before.

Besides, a heapsort is hardly complex to implement. Frankly, it would
probably be better if heapsort was most people's first choice - it's
only a bit more complex than quicksort in its basic form, and unlike
quicksort, it's perfectly usable in its basic form, all while only
being a factor of two, or so, slower. Once you add all the required
frou-frou to make quicksort usable, it's just as complex, if not more
so.

not really...

<
#include <cstdlib>
/* Adapted from Pete Filander's C version: */
/*http://www.mindspring.com/~pfilandr/C/e_driver/e_sort.c*/

template < class e_type >
void            hsortm(e_type * array, size_t nmemb)
{
    size_t          p,
                    child,
                    parent;
    e_type          temp;

    if (nmemb > 1) {
        p = --nmemb / 2;
        do {
            parent = (p);
            child = parent * 2;
            temp = (array)[parent];
            while ((nmemb) - parent > parent) {
                if ((*((array) + child + 1) > *((array) + child))) {
                    ++child;
                }
                if ((*((array) + child) > *(&temp))) {
                    (array)[parent] = (array)[child];
                    parent = child;
                    child *= 2;
                } else {
                    break;
                }
            }
            if ((nmemb) == child && (*((array) + child) > *(&temp))) {
                (array)[parent] = (array)[child];
                parent = child;
            }
            (array)[parent] = temp;
        } while (p-- != 0);
        ((void) (*(&temp) = *(array), *(array) = *(array + nmemb),
*(array + nmemb) = *(&temp)));
        while (--nmemb != 0) {
            parent = (0);
            child = parent * 2;
            temp = (array)[parent];
            while ((nmemb) - parent > parent) {
                if ((*((array) + child + 1) > *((array) + child))) {
                    ++child;
                }
                if ((*((array) + child) > *(&temp))) {
                    (array)[parent] = (array)[child];
                    parent = child;
                    child *= 2;
                } else {
                    break;
                }
            }
            if ((nmemb) == child && (*((array) + child) > *(&temp))) {
                (array)[parent] = (array)[child];
                parent = child;
            }
            (array)[parent] = temp;
            ((void) (*(&temp) = *(array), *(array) = *(array + nmemb),
*(array + nmemb) = *(&temp)));
        }
    }

}

you are claiming this is, simpler?...

and, in this example, you even have templates on your side...

even as such, note the number of compound expressions and pointer
operations.

actually, many of these could be changed to array indices, and many of these
pointer operations are useless, I have no idea why this is written this
way...

for fairness, I will take the example given, and clean it up:

template<class e_type> void hsortm(e_type *array, size_t nmemb)
{
    size_t          p, child, parent;
    e_type          temp;

    if (nmemb>1)
    {
        p=(--nmemb)/2;
        do {
            parent=p;
            child=parent * 2;
            temp=array[parent];
            while ((nmemb-parent)>parent)
            {
                if (array[child+1]>array[child]) child++;
                if (array[child]>temp)
                {
                    array[parent]=array[child];
                    parent=child;
                    child*=2;
                }else break;
            }
            if ((nmemb==child) && (array[child]>temp))
            {
                array[parent]=array[child];
                parent=child;
            }
            array[parent]=temp;
        } while (p--);

        temp=array[0];
        array[0]=array[nmemb];
        array[nmemb]=temp;

        while (--nmemb)
        {
            parent=0;
            child=parent*2;
            temp=array[parent];
            while ((nmemb-parent)>parent)
            {
                if (array[child+1]>array[child]) child++;

                if (array[child]>temp)
                {
                    array[parent]=array[child];
                    parent=child;
                    child*=2;
                } else break;
            }
            if ((nmemb==child) && (array[child]>temp))
            {
                array[parent]=array[child];
                parent=child;
            }
            array[parent]=temp;

            temp=array[0];
            array[0]=array[nmemb];
            array[nmemb]=temp;
        }
    }

}

still slightly more complicated than quicksort IMO, but IMO now somewhat
less horrid...

here is the algo of mine from before, adapted for an array of integers:

void Swap(int *arr, int i, int j)
{
    int k;
    if(i==j)return;
    k=arr[i]; arr[i]=arr[j]; arr[j]=k;

}

void Sort(int *arr, int base, int lim)
{
    static int depth=0;
    int mp;
    int low, mid, high;
    int i, j;

    if((lim-base)<2)return;

    depth++;
    if(depth>=32) //bad case, use selection sort
        { for(i=base; i<lim; i++)for(j=i+1; j<lim; j++)
            if(arr[j]<arr[i])Swap(arr, i, j);
            return; }

    low=base; high=lim; mid=(low+high)/2;
    mp=arr[mid];

    i=low;
    while(i<high)
    {
        if(arr[i]<mp) { Swap(arr, low++, i++); continue; }
        if(arr[i]>mp) { Swap(--high, i); continue; }
        i++;
    }

    Sort(base, low);
    Sort(high, lim);
    depth--;

}

and here is how it would look incorporating cocktail sort as a fallback:

void Sort(int *arr, int base, int lim)
{
    static int depth=0;
    int mp;
    int low, mid, high;
    int i, j;

    if((lim-base)<2)return;

   depth++;
   if(depth>=32) //bad case, use selection sort
    {
        j=1; while(j)
        {
            j=0; lim--;
            for(i=base; i<lim; i++)
                if(arr[i+1]<arr[i]) { Swap(i, i+1); j++; }
            for(i=lim; i>base; i--)
                if(arr[i]<arr[i-1]) { Swap(i, i-1); j++; }
            base++;
        }
        return;
    }

    low=base; high=lim; mid=(low+high)/2;
    mp=arr[mid];

    i=low;
    while(i<high)
    {
        if(arr[i]<mp) { Swap(arr, low++, i++); continue; }
        if(arr[i]>mp) { Swap(--high, i); continue; }
        i++;
    }

    Sort(base, low);
    Sort(high, lim);
    depth--;



}- Hide quoted text -

- Show quoted text -

Given the following definition for SWAP, I tried to implement your
sort:

#include <stdlib.h>

#define SWAP(A, B, T) ((void)(*(T) = *(A), *(A) = *(B), *(B) = *(T)))

typedef int e_type;

static void cr88192Sort(e_type * arr, int base, int lim, int
depth)
{
e_type mp;
int low,
mid,
high;
int i,
j;


if ((lim - base) < 2)
return;


depth++;
if (depth >= 32) { // bad case, use selection sort
j = 1;
while (j) {
e_type tmp;
j = 0;
lim--;
for (i = base; i < lim; i++)
if (arr[i + 1] < arr[i]) {
SWAP(&arr[i], &arr[i + 1], &tmp);
j++;
}
for (i = lim; i > base; i--)
if (arr[i] < arr[i - 1]) {
SWAP(&arr[i], &arr[i - 1], &tmp);
j++;
}
base++;
}
return;
}
low = base;
high = lim;
mid = (low + high) / 2;
mp = arr[mid];


i = low;
while (i < high) {
e_type tmp;
if (arr[i] < mp) {
SWAP(&arr[low], &arr[i], &tmp);
low++, i++;
continue;
}
if (arr[i] < mp) {
SWAP(&arr[high], &arr[i], &tmp);
high++;
continue;
}
i++;
}

cr88192Sort(arr, base, low, depth);
cr88192Sort(arr, high, lim, depth);
depth--;
}
void cr88192(e_type * array, size_t nmemb)
{
cr88192Sort(array, 0, nmemb - 1, 0);
}

/*
However, it does not produce properly sorted output.
Can you tell me where I went off?
*/
.

Relevant Pages

  • Re: linux-next: Tree for December 3 (cifs)
    ... looks like this new Kconfig option depends on some code that's ... I think the patch below is a better way to deal with this. ... -static int ...
    (Linux-Kernel)
  • Re: Plz explain me the following code
    ... int main ...   int x; ... says that when the behavior is undefined, "this International Standard ... it and executing it - "imposes no requirements" means that one of the ...
    (comp.lang.c)
  • Re: starting into H&S
    ...   int n; ...   const char *path; ... argc in that case. ... int main(int argc, char **argv) { ...
    (comp.lang.c)
  • Re: Error freeing memory....
    ...   size_t ilev; ...   int ncid; ... void USAGE; ... void GetMean(struct AR *A, struct V *ret, int timestep, double *array) ...
    (comp.lang.c)
  • Re: address calculation or M.S.D radix sort ?
    ...   struct node *next; ... int hash_fn; ... and "radix sort" are all very similar sorting algorithms. ... The keys are very short ...
    (comp.programming)