Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"Any excuse will serve a tyrant." -- Aesop

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

SubjectAuthor
o Re: new sorting algorithmjan

1
Re: new sorting algorithm

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

  copy mid

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

  copy link   Newsgroups: comp.lang.python
Path: i2pn2.org!i2pn.org!news.swapon.de!fu-berlin.de!uni-berlin.de!not-for-mail
From: rtm4...@googlemail.com (jan)
Newsgroups: comp.lang.python
Subject: Re: new sorting algorithm
Date: Mon, 2 May 2022 10:24:36 +0100
Lines: 77
Message-ID: <mailman.295.1651483480.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>
<CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
<CADJx9Ldr9R9MiVjjBeP9058xoErCZCsuSxjrNUDdOzHc1Sh4xg@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
X-Trace: news.uni-berlin.de AHFLj2HLCrF1rdN4rERFAwSdu3af+ks/pxF2LhdJepOg==
Return-Path: <rtm443x@googlemail.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=googlemail.com header.i=@googlemail.com header.b=DkNshJae;
dkim-adsp=pass; dkim-atps=neutral
X-Spam-Status: OK 0.001
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; '2022': 0.05; "python's":
0.05; 'real-world': 0.07; 'sun,': 0.07; 'angelico': 0.09; 'cc:addr
:python-list': 0.09; 'check,': 0.09; 'dan': 0.09; 'fact,': 0.09;
'from:addr:googlemail.com': 0.09; 'manages': 0.09; 'tricks': 0.09;
'log': 0.12; 'url:mailman': 0.15; 'that.': 0.15; '(plus,': 0.16;
'algorithms,': 0.16; 'append': 0.16; 'bulk': 0.16; 'cc:name:python
list': 0.16; 'chrisa': 0.16; 'handful': 0.16; 'hardly': 0.16;
'naive': 0.16; 'partitioning': 0.16; 'purely': 0.16; 'slow': 0.16;
'sort,': 0.16; 'sorted': 0.16; 'wrote:': 0.16;
'cc:addr:python.org': 0.20; "i've": 0.22; 'list,': 0.24; "i'd":
0.24; 'url-ip:188.166.95.178/32': 0.25; 'url-ip:188.166.95/24':
0.25; 'url:listinfo': 0.25; 'cannot': 0.25; 'cc:2**0': 0.25; 'url-
ip:188.166/16': 0.25; "isn't": 0.27; '>>>': 0.28; 'chris': 0.28;
'fact': 0.28; 'sense': 0.28; 'it,': 0.29; 'seem': 0.31; 'looked':
0.31; 'url-ip:188/8': 0.31; 'think': 0.32; 'cool': 0.32; '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; 'fix': 0.36; 'mon,': 0.36; 'using':
0.37; "it's": 0.37; 'received:209.85': 0.37; 'hard': 0.37;
'could': 0.38; 'received:209': 0.39; 'quite': 0.39; 'list': 0.39;
'still': 0.40; 'advantage': 0.40; 'case.': 0.40; 'data.': 0.40;
'best': 0.61; 'method': 0.61; 'merge': 0.62; 'data,': 0.63;
'clear': 0.64; 'entire': 0.67; 'items': 0.68; 'cost': 0.69;
'speed': 0.71; 'cheers': 0.76; 'known': 0.84; 'practical': 0.84;
'battle': 0.84; 'feature,': 0.84; 'reversed': 0.84; 'uphill':
0.84; 'wondered': 0.91
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlemail.com; s=20210112;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=0VcRAB5SV8DJ3ncF3KHL2SaVvhyLXjgT28bdQhmG8BY=;
b=DkNshJaeNRBOBEEvvubX/T9dqQCO+mgVK4/ZsURKarBQkAvsZdbN41g6V/TS+oFC0Z
VYCZrpClLynVEEKdj+/tLjg2PrxLtFeS9w3toKEOyk7IfxOYnwNdO7ZPBShxi1rNEsr2
CNSBkj33mBmLM4O7LusdtMo6VqoXBc6ugZfJC55FHbrkGEdFkLL9mv4vFzJp0EDKZ3ad
8UxfyIECUFku1dNw4GjwwyIe/wfWQU58eLn/EHOfRza/tJ6lKJo4X3gfgNo7X02YmE+a
iCLruNXxYFdgOGNdYggg7X5SJ4y4Dk+aK/F7LZvu/DZuA0so7qvbHujmXVYjyBGr5hzg
Bi/g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=0VcRAB5SV8DJ3ncF3KHL2SaVvhyLXjgT28bdQhmG8BY=;
b=Zjd1xXH54J25oGEYQwW44aXR6ugTQJOjXUVrjIyKoJPMzS8XXxKPRcibCIaIl9tzO6
xDmYzuJ+69MSlq00v7nZyU06ZdOliJ4wmigOBtP/B1IWgcO44cd9bZa5jBXZ/CkkGBKo
42hLv9FT7i/hl3EvjXLYcjB1/NRSLP6C61z8glfNZGICsPwcrHJBNt5jvsb9P2HKJzT8
S6v+XsC83NTBJ+Ptmyqql978SOtfeW7+ENW32uGVlzFgpnXSnGquklO+MA0VIsLXIflU
ZebodAXbl+PWdwl81xDGecXlrraDaaTClEuIhpLy9ppyIwutpm9GMuJkeQJ3k0CF1EHX
dmPw==
X-Gm-Message-State: AOAM530QZ0bdaBSSV4O+XjuNhb3kzor6F3LpZs7f0PWiMwX29He11oVf
yWdIaV61XUn3BHa5j2CI9P2tZXsxCRCIGoYyiBuoQFAc
X-Google-Smtp-Source: ABdhPJy30ZdrOZqbcIlRABdi/9KG0aXHiK8M1wGvNYdszAQvQexJuQ7t0Hua0TRDWfvAqkN35NjlzpB8Suq3zMvwN1g=
X-Received: by 2002:a17:902:70c8:b0:156:509b:68e3 with SMTP id
l8-20020a17090270c800b00156509b68e3mr11077445plt.113.1651483477271; Mon, 02
May 2022 02:24:37 -0700 (PDT)
In-Reply-To: <CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
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: <CADJx9Ldr9R9MiVjjBeP9058xoErCZCsuSxjrNUDdOzHc1Sh4xg@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>
<CAGGBd_otruOBmwWv5yhhRZB=BJ547pitiTCTODXwV0Km8OnMRw@mail.gmail.com>
<CAPTjJmotvBiPTQC8bpYUS+y3Avrt1gyr5y5O6WCmVHNyWJiEHA@mail.gmail.com>
 by: jan - Mon, 2 May 2022 09:24 UTC

Hi,

> The median-of-three partitioning technique makes that work reasonably
well, so it won't be pathologically slow

Just to be clear because I've wondered but haven't looked into it, we
know naive quicksorting of already-sorted data is pathalogical, but
median-of-3 is known to fix this pathology?

cheers

jan

On 02/05/2022, Chris Angelico <rosuav@gmail.com> wrote:
> On Mon, 2 May 2022 at 09:20, Dan Stromberg <drsalists@gmail.com> wrote:
>>
>>
>> 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.
>>
>
> The median-of-three partitioning technique makes that work reasonably
> well, so it won't be pathologically slow. It's hardly Quicksort's best
> feature, but it could easily be a lot worse. I'd have to check, but I
> think it still manages to be O(n log n). Merge sort, of course, is a
> lot more consistent, but the asymptotic cost is still broadly the
> same.
>
> But Timsort manages to be close to O(n) for sorted data, reversed
> data, nearly-sorted or nearly-reversed data, etc. Makes it very handy
> for jobs like "click a heading to sort by it", where you might add
> multiple sort keys.
>
> (Plus, Python's implementation has some cool tricks for small
> collections that make it quite efficient.)
>
> ChrisA
> --
> https://mail.python.org/mailman/listinfo/python-list
>

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor