bug in sort.c

bug in sort.c

[Roland Orre]

The following two lines in scm_restricted_vector_sort_x
are wrong:

  SCM_VALIDATE_INUM_RANGE (4, endpos,0, vlen+1);
  len = SCM_INUM (endpos) - spos;

they should be:

  SCM_VALIDATE_INUM_RANGE (4, endpos,0, vlen);
  len = SCM_INUM (endpos) - spos + 1;

at least to be consistent with the documentation. Apart from that
I've found that quicksort is extremely slow for vectors and am now
using a merge sort also for vectors. (It's me having put that code
ther earlier and I'll look into why it is slow, but quicksort worst
case complexity is O(N^2), in average O(N log N) but merge sort
is always O(N log N) as I understand so it may be correct, but I'll
post the suggested restricted_vector_msort_x on the guile-user.

	Best regards
	Roland Orre





_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel

Re: bug in sort.c

[Marius Vollmer]

Roland Orre <roland.orre@neurologic.se> writes:

> The following two lines in scm_restricted_vector_sort_x
> are wrong:
>
>   SCM_VALIDATE_INUM_RANGE (4, endpos,0, vlen+1);
>   len = SCM_INUM (endpos) - spos;
>
> they should be:
>
>   SCM_VALIDATE_INUM_RANGE (4, endpos,0, vlen);
>   len = SCM_INUM (endpos) - spos + 1;

I think the code is correct: we need to have

    0 <= startpos <= endpos <= vlen

The element with index endpos is not included in the sort, thus we
will sort

    len = endpos - spos

elements.

The docstring needs to be clearer about this, tho.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-devel