Sorting implemented in Guile standard library

Sorting implemented in Guile standard library

[Zelphir Kaltstahl]

Hello Guile Users!

I was checking out
https://www.gnu.org/software/guile/manual/html_node/Sorting.html and
noticed, that the definition of `sort` does not mention, which algorithm
is used for sorting:

> Sort the sequence items, which may be a list or a vector. less is used
for comparing the sequence elements. This is not a stable sort.

So my question is: Which algorithm is used for Guile's `sort` function?

Regards,
Zelphir

-- 
repositories: https://notabug.org/ZelphirKaltstahl

Re: Sorting implemented in Guile standard library

[Bill Markmann]

I'm not a guile hacker, but looking at the source for "libguile/sort.c", it
looks like quicksort:

#include "sort.h"

/* We have two quicksort variants: one for SCM (#t) arrays and one for
   typed arrays.
*/

#define NAME        quicksort
#define INC_PARAM   ssize_t inc,
#define VEC_PARAM   SCM * ra,
#define GET(i)      ra[(i)*inc]
#define SET(i, val) ra[(i)*inc] = val
#include "quicksort.i.c"

The sort functions look like they call "s_scm_restricted_vector_sort_x",
and then in there:

  if (handle.element_type == SCM_ARRAY_ELEMENT_TYPE_SCM)
    quicksort (scm_array_handle_writable_elements (&handle) - dims[0].lbnd
* dims[0].inc,
               spos, epos, dims[0].inc, less);
  else
    quicksorta (&handle, spos, epos, less);


I'd assume that's what is underneath (sort items less) and friends.  Just a
guess, though... :-)


On Sun, Aug 16, 2020 at 4:56 PM Zelphir Kaltstahl <
zelphirkaltstahl@posteo.de> wrote:

> Hello Guile Users!
>
> I was checking out
> https://www.gnu.org/software/guile/manual/html_node/Sorting.html and
> noticed, that the definition of `sort` does not mention, which algorithm
> is used for sorting:
>
> > Sort the sequence items, which may be a list or a vector. less is used
> for comparing the sequence elements. This is not a stable sort.
>
> So my question is: Which algorithm is used for Guile's `sort` function?
>
> Regards,
> Zelphir
>
> --
> repositories: https://notabug.org/ZelphirKaltstahl
>
>
>

Re: Sorting implemented in Guile standard library

[Zelphir Kaltstahl]

Hello Bill!

Thanks for looking into it!

Regards,
Zelphir

On 16.08.20 23:11, Bill Markmann wrote:
> I'm not a guile hacker, but looking at the source for
> "libguile/sort.c", it looks like quicksort:
>
> #include "sort.h"
>
> /* We have two quicksort variants: one for SCM (#t) arrays and one for
>    typed arrays.
> */
>
> #define NAME        quicksort
> #define INC_PARAM   ssize_t inc,
> #define VEC_PARAM   SCM * ra,
> #define GET(i)      ra[(i)*inc]
> #define SET(i, val) ra[(i)*inc] = val
> #include "quicksort.i.c"
>
> The sort functions look like they
> call "s_scm_restricted_vector_sort_x", and then in there:
>
>   if (handle.element_type == SCM_ARRAY_ELEMENT_TYPE_SCM)
>     quicksort (scm_array_handle_writable_elements (&handle) -
> dims[0].lbnd * dims[0].inc,
>                spos, epos, dims[0].inc, less);
>   else
>     quicksorta (&handle, spos, epos, less);
>
>
> I'd assume that's what is underneath (sort items less) and friends. 
> Just a guess, though... :-)
>
>
> On Sun, Aug 16, 2020 at 4:56 PM Zelphir Kaltstahl
> <zelphirkaltstahl@posteo.de <mailto:zelphirkaltstahl@posteo.de>> wrote:
>
>     Hello Guile Users!
>
>     I was checking out
>     https://www.gnu.org/software/guile/manual/html_node/Sorting.html and
>     noticed, that the definition of `sort` does not mention, which
>     algorithm
>     is used for sorting:
>
>     > Sort the sequence items, which may be a list or a vector. less
>     is used
>     for comparing the sequence elements. This is not a stable sort.
>
>     So my question is: Which algorithm is used for Guile's `sort`
>     function?
>
>     Regards,
>     Zelphir
>
>     -- 
>     repositories: https://notabug.org/ZelphirKaltstahl
>
>
-- 
repositories: https://notabug.org/ZelphirKaltstahl

Re: Sorting implemented in Guile standard library

[Stefan Israelsson Tampe]

Can we get some benchmarking, calling out to scheme for each comparison
seam expensive. I could think of an algorithm that dispatch on the <,>,else
and use fast C for '<','>' and a scheme implementation for 'else'.

On Tue, Aug 18, 2020 at 9:33 PM Zelphir Kaltstahl <
zelphirkaltstahl@posteo.de> wrote:

> Hello Bill!
>
> Thanks for looking into it!
>
> Regards,
> Zelphir
>
> On 16.08.20 23:11, Bill Markmann wrote:
> > I'm not a guile hacker, but looking at the source for
> > "libguile/sort.c", it looks like quicksort:
> >
> > #include "sort.h"
> >
> > /* We have two quicksort variants: one for SCM (#t) arrays and one for
> >    typed arrays.
> > */
> >
> > #define NAME        quicksort
> > #define INC_PARAM   ssize_t inc,
> > #define VEC_PARAM   SCM * ra,
> > #define GET(i)      ra[(i)*inc]
> > #define SET(i, val) ra[(i)*inc] = val
> > #include "quicksort.i.c"
> >
> > The sort functions look like they
> > call "s_scm_restricted_vector_sort_x", and then in there:
> >
> >   if (handle.element_type == SCM_ARRAY_ELEMENT_TYPE_SCM)
> >     quicksort (scm_array_handle_writable_elements (&handle) -
> > dims[0].lbnd * dims[0].inc,
> >                spos, epos, dims[0].inc, less);
> >   else
> >     quicksorta (&handle, spos, epos, less);
> >
> >
> > I'd assume that's what is underneath (sort items less) and friends.
> > Just a guess, though... :-)
> >
> >
> > On Sun, Aug 16, 2020 at 4:56 PM Zelphir Kaltstahl
> > <zelphirkaltstahl@posteo.de <mailto:zelphirkaltstahl@posteo.de>> wrote:
> >
> >     Hello Guile Users!
> >
> >     I was checking out
> >     https://www.gnu.org/software/guile/manual/html_node/Sorting.html and
> >     noticed, that the definition of `sort` does not mention, which
> >     algorithm
> >     is used for sorting:
> >
> >     > Sort the sequence items, which may be a list or a vector. less
> >     is used
> >     for comparing the sequence elements. This is not a stable sort.
> >
> >     So my question is: Which algorithm is used for Guile's `sort`
> >     function?
> >
> >     Regards,
> >     Zelphir
> >
> >     --
> >     repositories: https://notabug.org/ZelphirKaltstahl
> >
> >
> --
> repositories: https://notabug.org/ZelphirKaltstahl
>
>