Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

UNIX enhancements aren't.


devel / comp.lang.python / Re: new sorting algorithm

SubjectAuthor
o Re: new sorting algorithmDan Stromberg

1
Re: new sorting algorithm

<mailman.287.1651447230.20749.python-list@python.org>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=18097&group=comp.lang.python#18097

  copy link   Newsgroups: comp.lang.python
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: drsali...@gmail.com (Dan Stromberg)
Newsgroups: comp.lang.python
Subject: Re: new sorting algorithm
Date: Sun, 1 May 2022 16:20:16 -0700
Lines: 38
Message-ID: <mailman.287.1651447230.20749.python-list@python.org>
References: <CADs8Xt5LE4f5ayJ5n94+KKyR3bGQ13dk-Tr_u7XhFaEuwxpVOg@mail.gmail.com>
<CAPTjJmq3VgD+OyiL4W=m2Bo0BJwHaYY69a=mAPJx5vMnfBdHFg@mail.gmail.com>
<CAGGBd_p9iNwiAe87E1x759Oo659HTAO9Frs7L8fzpTq9+J0Rmg@mail.gmail.com>
<CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
<CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
X-Trace: news.uni-berlin.de H0WcGiQMNA/YKHtzsXGg7QaETtV45HbtRybHq1fLGOoQ==
Return-Path: <drsalists@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
Authentication-Results: mail.python.org; dkim=pass
reason="2048-bit key; unprotected key"
header.d=gmail.com header.i=@gmail.com header.b=kr4f6wUf;
dkim-adsp=pass; dkim-atps=neutral
X-Spam-Status: OK 0.008
X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; '2022': 0.05; 'real-world':
0.07; 'sun,': 0.07; 'angelico': 0.09; 'dan': 0.09; 'fact,': 0.09;
'&gt;': 0.14; 'that.': 0.15; 'algorithms,': 0.16; 'append': 0.16;
'bulk': 0.16; 'from:addr:drsalists': 0.16; 'from:name:dan
stromberg': 0.16; 'handful': 0.16; 'purely': 0.16; 'sorted': 0.16;
'wrote:': 0.16; 'to:addr:python-list': 0.20; 'list,': 0.24;
'cannot': 0.25; "isn't": 0.27; 'chris': 0.28; 'fact': 0.28;
'sense': 0.28; 'it,': 0.29; 'seem': 0.31; 'message-
id:@mail.gmail.com': 0.32; 'develop': 0.32; 'but': 0.32; "i'm":
0.33; 'header:In-Reply-To:1': 0.34; 'received:google.com': 0.34;
'item': 0.35; 'close': 0.35; 'from:addr:gmail.com': 0.35; 'mon,':
0.36; 'using': 0.37; "it's": 0.37; 'received:209.85': 0.37;
'hard': 0.37; 'received:209': 0.39; 'quite': 0.39; 'list': 0.39;
'received:209.85.222': 0.39; 'still': 0.40; 'advantage': 0.40;
'case.': 0.40; 'data.': 0.40; 'method': 0.61; 'data,': 0.63;
'entire': 0.67; 'items': 0.68; 'speed': 0.71; 'practical': 0.84;
'battle': 0.84; 'uphill': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=DJqVrgrsN7FEinAOCmjTEDTwi4vy9+H0cn1AgcMDcpc=;
b=kr4f6wUfwAZCXSTYsrZ98bJziAdEQmyI+U534X+vmdE2fF1PHKp1efWSHRwe3RXQ+I
8IVLAj3bwxBFYTRBJ7lOqYDXFJ4yPWB+/HbmBeCpilWPz0rZ42cNKRwpIjDeX8HiKhBT
8affN+I8FOtCMpUYcAeGE7hT6xUonqedz/j5oNhQ2sd1yjhyCX4Ep0pZU9vOT/hBOw8W
4ERg6MNRkEbPLEkHx39MJwL6EOBSu7kMr2Bpach6biwW3jNWPKW2i661EC1b6WSNisMC
UysjrV/Juh7g+GtfFLByVbpqEmw3eYXE+2Hq0rHaW8mXqkYh065Y4j+SwOOVHvFYAx6Z
aAuw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to;
bh=DJqVrgrsN7FEinAOCmjTEDTwi4vy9+H0cn1AgcMDcpc=;
b=fsgSC9b417ds8iu2UIASajyUxH5PCj6x1T9ncjb7f3vY1/EF481wTAt9Z1GgvtSwmZ
XIhFJH3gFYrEKpinaUb4/X3Ta7Vg1HOJOl4uKta0brg3LTpNiKfPDTwsnO/h3OR2ICUT
mKQet3FeRIOC8P0pk8xh55GhsvXqfrQkTbevsWuIIgJNS+rEfynZy8j+EIoyAFCLDXSt
iUw1HqPTJuA+Go3H3HCp+EB98Mhxka9JG1anijMieoONGxaiUqCfBMTF3yHXeVLg37NF
lEuxUxp8Nq7lr/Lx9BAHTabkVMGApeyS9RrBPTOEDYlfr/A+djTNqmOdRw/xQrhCne9E
YmpA==
X-Gm-Message-State: AOAM532qBPAxYfqld1o+m4pYSIpvR1eq2clovlWTCqvC4CbORIxEmrCM
C8dXaEgB8XYuLnLq0lf0J4Lxn6Zugjum9R8YjdB2xDof
X-Google-Smtp-Source: ABdhPJzU6Zl5kfb+n3yB0DKKZ6QBlgP5KCyFFCsqR6Lm91u/f3KgP0PCbWqzqNZNtoTcGxxhxOQwcSXnpD1rMZ+joEY=
X-Received: by 2002:ab0:3850:0:b0:362:8021:7b95 with SMTP id
h16-20020ab03850000000b0036280217b95mr2257019uaw.39.1651447227584; Sun, 01
May 2022 16:20:27 -0700 (PDT)
In-Reply-To: <CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
X-Content-Filtered-By: Mailman/MimeDel 2.1.39
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: General discussion list for the Python programming language
<python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>,
<mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <https://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>,
<mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
X-Mailman-Original-References: <CADs8Xt5LE4f5ayJ5n94+KKyR3bGQ13dk-Tr_u7XhFaEuwxpVOg@mail.gmail.com>
<CAPTjJmq3VgD+OyiL4W=m2Bo0BJwHaYY69a=mAPJx5vMnfBdHFg@mail.gmail.com>
<CAGGBd_p9iNwiAe87E1x759Oo659HTAO9Frs7L8fzpTq9+J0Rmg@mail.gmail.com>
<CAPTjJmpZEQSgzL2b50FK+mK7dNJgJwd2YteqjxyxWZi_o4UUJQ@mail.gmail.com>
 by: Dan Stromberg - Sun, 1 May 2022 23:20 UTC

On Sun, May 1, 2022 at 1:44 PM Chris Angelico <rosuav@gmail.com> wrote:

> On Mon, 2 May 2022 at 06:43, Dan Stromberg <drsalists@gmail.com> wrote:
> > On Sun, May 1, 2022 at 11:10 AM Chris Angelico <rosuav@gmail.com> wrote:
> >>
> >> On Mon, 2 May 2022 at 01:53, Nas Bayedil <nbayedil@gmail.com> wrote:
> >> > We believe that using this method to develop completely new, fast
> >> > algorithms, approaching the speed of the famous *QuickSort*, the
> speed of
> >> > which cannot be surpassed, but its drawback can be circumvented, in
> the
> >> > sense of stack overflow, on some data.
> >>
> >> Hmm, actually TimSort *does* exceed the speed of quicksort for a lot
> >> of real-world data. For instance, if you take a large sorted list,
> >> append a handful of (unsorted) items to it, and then sort the list,
> >> TimSort can take advantage of the fact that the bulk of the list is
> >> sorted. It ends up significantly faster than re-sorting the entire
> >> list.
> >
> >
> > In fact, Timsort is O(n) for already-sorted data, while many quicksorts
> are O(n^2) for already-sorted data.
> >
> > Quicksort can be salvaged by using a median-of-3 partitioning, but it's
> still O(n^2) in the (less common) worst case.
> >
>
> This is true, but purely sorted data isn't a very practical case. The
> case of mostly-sorted data IS practical, though, so it's a quite big
> win that it can be close to O(n), and still faster than inserting each
> item individually.
>

You seem to be of the impression that nearly-sorted data isn't an uphill
battle with a straightforward quicksort.

I'm having a hard time convincing myself of that.

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor