From: Bill Markmann <bmarkmann@gmail.com>
To: Zelphir Kaltstahl <zelphirkaltstahl@posteo.de>
Cc: Guile User <guile-user@gnu.org>
Subject: Re: Sorting implemented in Guile standard library
Date: Sun, 16 Aug 2020 17:11:19 -0400 [thread overview]
Message-ID: <CAKfsddAWHk_Jr_5zpKOmOMuXiMMU0Bvj=4umdJButF6kApFUmg@mail.gmail.com> (raw)
In-Reply-To: <1218f943-ea4d-2c67-7ff4-b4747a12194d@posteo.de>
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
>
>
>
next prev parent reply other threads:[~2020-08-16 21:11 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-08-16 20:56 Sorting implemented in Guile standard library Zelphir Kaltstahl
2020-08-16 21:11 ` Bill Markmann [this message]
2020-08-18 19:32 ` Zelphir Kaltstahl
2020-08-18 20:01 ` Stefan Israelsson Tampe
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAKfsddAWHk_Jr_5zpKOmOMuXiMMU0Bvj=4umdJButF6kApFUmg@mail.gmail.com' \
--to=bmarkmann@gmail.com \
--cc=guile-user@gnu.org \
--cc=zelphirkaltstahl@posteo.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).