[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug in sort.c
From: |
Roland Orre |
Subject: |
bug in sort.c |
Date: |
Thu, 14 Oct 2004 14:07:36 +0200 |
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
- bug in sort.c,
Roland Orre <=