1. Forum
  2. Usenet
  3. COMP.LANG.C

  • quicksort traume

    From fir@21:1/5 to All on Tue Mar 26 13:06:06 2024
    quicksort trauma


    i remmeber back then i was revriting quicksort form
    wikipedia or some other poage and tested multiple
    versions of it
    at some moment i changed something (as i remember i
    repleced do while on while this way it seemd to me
    it should work but i made some mistake and some
    versions were wrong and i not noticed that
    - later i afair repaired that but in my
    older codes i got verions which im not sure is for
    sure right or not

    for example this one



    void QuicksortInts7(int* table, int lo, int hi)
    {

    int i=lo; int j=hi;

    while (i<hi)
    {
    int pivot =table[(lo+hi)/2];
    while (i<=j) // Partition
    {
    while (table[i]<pivot) i++;
    while (table[j]>pivot) j--;
    if (i<=j)
    {
    int t=table[i];table[i]=table[j];table[j]=t;
    i++; j--;
    }
    }

    if (lo < j){ QuicksortInts7(table, lo, j);} //recursion
    lo=i; j=hi;
    }
    }


    how can i be sure this is right?? do generation of random array
    and comoper results with say qsort from c-lib is enough?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From fir@21:1/5 to fir on Wed Mar 27 11:07:14 2024
    fir wrote:
    quicksort trauma


    i remmeber back then i was revriting quicksort form
    wikipedia or some other poage and tested multiple
    versions of it
    at some moment i changed something (as i remember i
    repleced do while on while this way it seemd to me
    it should work but i made some mistake and some
    versions were wrong and i not noticed that
    - later i afair repaired that but in my
    older codes i got verions which im not sure is for
    sure right or not

    for example this one



    void QuicksortInts7(int* table, int lo, int hi)
    {

    int i=lo; int j=hi;

    while (i<hi)
    {
    int pivot =table[(lo+hi)/2];
    while (i<=j) // Partition
    {
    while (table[i]<pivot) i++;
    while (table[j]>pivot) j--;
    if (i<=j)
    {
    int t=table[i];table[i]=table[j];table[j]=t;
    i++; j--;
    }
    }

    if (lo < j){ QuicksortInts7(table, lo, j);} //recursion
    lo=i; j=hi;
    }
    }


    how can i be sure this is right?? do generation of random array
    and comoper results with say qsort from c-lib is enough?

    this version above seem to work but i only compare to correctnes by
    compare to qsort results and if tryin to revrite quicksort it opens
    small hell to me so hard is to debiug this, and why something is errorous


    this above i sucpect (though not know, maybe not) probably could be
    simplified but revriting is hard

    mainy i dislike those conditions like in while headers imo conditions
    in the middle that calls break should be better, but tryin to revrite id
    i spend 3-4 hours and failed

    though its rare exampel of code i do not fully understand in a form of
    usueal micrologic - and i at least closed to understand it so next time
    i can revrite it probably and fully understand it

    quicksort btw is somewhat strughtforward reccurency metgod - as it goes
    divide on tqwo parts and call itself on the parts (where divide on two
    parts i swipe lower on the left and upper on the right so in fact
    its quite simple

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)