[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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]