From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Bill Markmann Newsgroups: gmane.lisp.guile.user Subject: Re: Sorting implemented in Guile standard library Date: Sun, 16 Aug 2020 17:11:19 -0400 Message-ID: References: <1218f943-ea4d-2c67-7ff4-b4747a12194d@posteo.de> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="38989"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Guile User To: Zelphir Kaltstahl Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Sun Aug 16 23:11:52 2020 Return-path: Envelope-to: guile-user@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1k7PwW-000A1h-SM for guile-user@m.gmane-mx.org; Sun, 16 Aug 2020 23:11:52 +0200 Original-Received: from localhost ([::1]:59516 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1k7PwV-0003up-PF for guile-user@m.gmane-mx.org; Sun, 16 Aug 2020 17:11:51 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:46876) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1k7PwE-0003ui-RG for guile-user@gnu.org; Sun, 16 Aug 2020 17:11:34 -0400 Original-Received: from mail-ej1-x62c.google.com ([2a00:1450:4864:20::62c]:36286) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1k7PwC-0006yL-Vp for guile-user@gnu.org; Sun, 16 Aug 2020 17:11:34 -0400 Original-Received: by mail-ej1-x62c.google.com with SMTP id kq25so15469919ejb.3 for ; Sun, 16 Aug 2020 14:11:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=TwOoQR+fC6Tc1jI4njQKQ/Rf9YN+D/FvwJ16y2uf/r8=; b=lv15TAEynuDjFRoAYXGgPi+q6Wq95GQ20STw98GrqV0+9nAPNZLYmtejkaSEdL2aZn PmcM1dJHYGb5PwZl/jyyxtv4kFa7cEtAohAOgoR+jNq+IhhZbGlDeI783XBEMG13Tjyk +4XM7p4xtmv8IB4hLnzH+NHYSenqNtbabTSmMCD7G3nRpdwlGd8iyMynyav2jnu4z6vS K/Bf/UwkJTjE3/pg+TwJV2Dg4ew6WWFeclyesJyTyjkFW+5GmvNvevBPoYWIJGiK1ssI +iF2zUdId2r6X7gSpkuCs/P67NJMLbbGY9yvMZsOX8PFTx1m4UYP4Pw9583shwR/Q88u Jd/Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=TwOoQR+fC6Tc1jI4njQKQ/Rf9YN+D/FvwJ16y2uf/r8=; b=Ux3ig9OwZuhZEx21S7U4yrSDL3SY8t/aJGQVEALLWBwgtoaYliBNc7bgumbpZWoYEL SH2EYoGQO4kWo6P+RNOGviLIhJj9L5R8+VTPncj2V+cxr68cDo5DwHPRLk1v0O8s16XA H+QbrOFZHkgFnahWCXvgLoY5oLrdw3sCzTKb7m83dyK+qkntLla+uh7W1cisXgJaFpRo qVS7FH9oBT+FoeihN6RiEtPBtTW1sAfmiRg8FsCcUXeGHD8mKkAChGnm22RE2B9EsnT1 YKudoERGfKWvt/YgGJuzGwjNEkTttgE7my8d7tkZOhuaA6RiqdXeXxm860/ZgYvYOHYN mn/Q== X-Gm-Message-State: AOAM532O5vGEhFQgGAdNgyivO+SCtcTY81Lugz8w9BNnOaSIVt/EZi6o uWP7zHWi3GljtTyO/NtJMEYdDA7qQoS04zJcIDE= X-Google-Smtp-Source: ABdhPJwcYlTKXOh6g1FzMthHUoS/8Mtk1aeofKf0xTqezZnv+FZmp7fnz8azpLVMZIXMS1qK3jOoWsm/vTjKoP5bBBY= X-Received: by 2002:a17:906:6d91:: with SMTP id h17mr11681314ejt.531.1597612290632; Sun, 16 Aug 2020 14:11:30 -0700 (PDT) In-Reply-To: <1218f943-ea4d-2c67-7ff4-b4747a12194d@posteo.de> Received-SPF: pass client-ip=2a00:1450:4864:20::62c; envelope-from=bmarkmann@gmail.com; helo=mail-ej1-x62c.google.com X-detected-operating-system: by eggs.gnu.org: No matching host in p0f cache. That's all we know. X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Content-Filtered-By: Mailman/MimeDel 2.1.23 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.io gmane.lisp.guile.user:16807 Archived-At: 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 > > >