[ruby-talk:5173] Re: methods w/ ! giving nil

> Actually Ruby does have its own qsort routine in C (in util.c), which
> is compatible with original qsort(3).  Only problem left is re-design
> and hack the routine.   I'm afraid it's a tough task, for me at least.

Changing swap does not work since swap can be invoked also for equal
values and it one has to be careful in defining if the list is changed or
not. The only other solution (I can think of) is checking if the array is
already sorted. The check is already present in the ruby_sort code so this
small change does not affect performances.

In any case, the *average* cost of checking if an array is sorted is a
*small* constant number of comparisons.

The following patch should do the job:


for util.h:
--------------------------------
39c39
< void ruby_qsort _((void*, int, int, int (*)()));
---
> int ruby_qsort _((void*, int, int, int (*)()));
--------------------------------

for util.c:
--------------------------------
617c617,618
< void ruby_qsort (base, nel, size, cmp) void* base; int nel; int size; int (*cmp)();
---
> int ruby_qsort (base, nel, size, cmp)
> void* base; int nel; int size; int (*cmp)();
619,620c620,621
<  register char *l, *r, *m;          	/* l,r:left,right group   m:median point */
<  register int  t, eq_l, eq_r;       	/* eq_l: all items in left group are equal to S */
---
>  register char *l, *r, *m;          	/* l,r,m: left,right,median point */
>  register int  t, eq_l, eq_r;    /* eq_l: items in left group are equal to S */
623c624
<  int  chklim = 63;                      /* threshold of ordering element check */
---
>  int  chkord = 1;                       /* check ordering of elements */
626c627
<  if (nel <= 1) return;        /* need not to sort */
---
>  if (nel <= 1) return 1;                /* need not to sort */
627a629,631
>  if (nel == 2) {
>    if ((*cmp)(L,R) > 0) {mmswap(L,R); return 0;} else return 1;
>  }
631c635
<  if (stack == top) return;    /* return if stack is empty */
---
>  if (stack == top) return 0;            /* return if stack is empty */
636c640,641
<    if (L + size == R) {if ((*cmp)(L,R) > 0) mmswap(L,R); goto nxt;}/* 2 elements */
---
>    if (L + size == R)                   /* 2 elements */
>      {if ((*cmp)(L,R) > 0) mmswap(L,R); goto nxt;}
665,682c670
<    if ((t = (*cmp)(l,m)) < 0) {                             /*3-5-?*/
<      if ((t = (*cmp)(m,r)) < 0) {                           /*3-5-7*/
<        if (chklim && nel >= chklim) {   /* check if already ascending order */
<          char *p;
<          chklim = 0;
<          for (p=l; p<r; p+=size) if ((*cmp)(p,p+size) > 0) goto fail;
<          goto nxt;
<        }
<        fail: goto loopA;                                    /*3-5-7*/
<      }
<      if (t > 0) {
<        if ((*cmp)(l,r) <= 0) {mmswap(m,r); goto loopA;}     /*3-5-4*/
<        mmrot3(r,m,l); goto loopA;                           /*3-5-2*/
<      }
<      goto loopB;                                            /*3-5-5*/
<    }
<    
<    if (t > 0) {                                             /*7-5-?*/
---
>    if ((t = (*cmp)(l,m)) > 0) {                             /*7-5-?*/
684c672
<        if (chklim && nel >= chklim) {   /* check if already ascending order */
---
>        if (chkord) {   /* check if already descending order */
686,687c674,675
<          chklim = 0;
<          for (p=l; p<r; p+=size) if ((*cmp)(p,p+size) < 0) goto fail2;
---
>          chkord = 0;
>          for (p=l; p<r; p+=size) if ((*cmp)(p,p+size) < 0) goto fail;
691c679
<        fail2: mmswap(l,r); goto loopA;                      /*7-5-3*/
---
>        fail: mmswap(l,r); goto loopA;                       /*7-5-3*/
698a687,704
> 
>    if (t < 0) {                                             /*3-5-?*/
>      if ((t = (*cmp)(m,r)) > 0) {
>        if ((*cmp)(l,r) <= 0) {mmswap(m,r); goto loopA;}     /*3-5-4*/
>        mmrot3(r,m,l); goto loopA;                           /*3-5-2*/
>      }
>      if (chkord) {   /* check if already ascending order */
>        char *p;
>        chkord = 0;
>        for (p=l; p<r; p+=size) if ((*cmp)(p,p+size) > 0) goto fail2;
>        if ((l == base) && (r == (char *)base + size*(nel - 1)))
> 	 return 1;
>        goto nxt;
>      }
>    fail2:
>      if (t < 0) goto loopA;                                 /*3-5-7*/
>      goto loopB;                                            /*3-5-5*/
>    }   
700,701c706,716
<    if ((t = (*cmp)(m,r)) < 0)  {goto loopA;}                /*5-5-7*/
<    if (t > 0) {mmswap(l,r); goto loopB;}                    /*5-5-3*/
---
>    if ((t = (*cmp)(m,r)) > 0) {mmswap(l,r); goto loopB;}    /*5-5-3*/
>    if (chkord) {   /* check if already ascending order */
>      char *p;
>      chkord = 0;
>      for (p=l; p<r; p+=size) if ((*cmp)(p,p+size) > 0) goto fail3;
>      if ((l == base) && (r == (char *)base + size*(nel - 1)))
>        return 1;
>      goto nxt;
>    }
>  fail3:
>    if (t < 0)  {goto loopA;}                                /*5-5-7*/
711c726
<    loopA: eq_l = 1; eq_r = 1;  /* splitting type A */ /* left <= median < right */
---
>    loopA: eq_l = 1; eq_r = 1;  /* splitting type A: left <= median < right */
730c745
<    loopB: eq_l = 1; eq_r = 1;  /* splitting type B */ /* left < median <= right */
---
>    loopB: eq_l = 1; eq_r = 1;  /* splitting type B: left < median <= right */
----------------------------------------

Best Regards,

						Davide