Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"Be *excellent* to each other." -- Bill, or Ted, in Bill and Ted's Excellent Adventure


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

SubjectAuthor
o Re: new sorting algorithmDan Stromberg

1
Re: new sorting algorithm

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

  copy mid

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

  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: Mon, 2 May 2022 19:11:19 -0700
Lines: 17
Message-ID: <mailman.302.1651543892.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>
<CAGGBd_qjsyNc_uBKePC=ySsanu09XY8TS=6Uxmz0gZFc9fujxA@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
X-Trace: news.uni-berlin.de RH/OU+Rt2J6aArkJAGuM3gV/gbZnMSL3aoMC+1D5/u7g==
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=HaVbuA0U;
dkim-adsp=pass; dkim-atps=neutral
X-Spam-Status: OK 0.036
X-Spam-Evidence: '*H*': 0.93; '*S*': 0.00; '2022': 0.05; 'cc:addr
:python-list': 0.09; 'construct': 0.09; '&gt;': 0.14;
'cc:name:python list': 0.16; 'from:addr:drsalists': 0.16;
'from:name:dan stromberg': 0.16; 'naive': 0.16; 'partitioning':
0.16; 'slow': 0.16; 'wrote:': 0.16; 'cc:addr:python.org': 0.20;
"i've": 0.22; 'cc:2**1': 0.23; 'email addr:python.org&gt;': 0.28;
'it,': 0.29; 'looked': 0.31; 'python-list': 0.32; 'message-
id:@mail.gmail.com': 0.32; 'but': 0.32; 'header:In-Reply-To:1':
0.34; 'received:google.com': 0.34; 'from:addr:gmail.com': 0.35;
'fix': 0.36; 'mon,': 0.36; "it's": 0.37; 'received:209.85': 0.37;
'received:209': 0.39; 'break': 0.39; 'still': 0.40; 'case.': 0.40;
'clear': 0.64; 'down': 0.64; 'less': 0.65; 'known': 0.84; 'email
name:&lt;python-list': 0.84; 'inputs': 0.84; 'wondered': 0.91
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
:cc; bh=N/Ct6TjlYRNYXZzlWuH5WZe1iOjN3sq7AKPD1D/mhb8=;
b=HaVbuA0UTXwjfoHGFWEIKyORMGWB4V3cqKutosvbQuuL839f+xa7UJfv+zorZaQxP7
1uYEBDNtvmfrYlIjJ3aJzZDdASEm7BVE3vqxNWVt87xSxleaMKHl2Ns6vxL4XGqBMK9x
N+sfGzC5R4+jpqnneQOenmDPfgh8PIrDI3XCCiVAPrM88Fk5jffuzaExmRRUlVOM1yaG
6mHjhiBy2Y3GRvn8hK3O/lh71sqy7lDwAzvPPtW1fGgP0HazJIBndo//KdsNRw1aJhuq
bmKq1BqkUU+I4SfBT0ogARNJLGwotah9tZc9NcnvKvbZe0OL68go7OO3vNAXDKJincuM
y6hA==
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:cc;
bh=N/Ct6TjlYRNYXZzlWuH5WZe1iOjN3sq7AKPD1D/mhb8=;
b=nDaFzg9WGYTZpiuYm/fC4vN78aJBzunbNlm6C9kCKInJOp+vJp21TAtyWbSaUO+c1O
DPd3/b8ev1ropdHLm/uR2L6cAPWnTkXuc89rA9ZXjRdKpquZ/Zvnkg2Y48JuOcXm7cNn
8HdLQVxnwTIWa93XHkuVmhJncPf3vAhufPYN/aTL//JWc9j93OcuUpDq//YwALmEt37x
07gMR0AgWgsZHwBrAllrV5Z1nZBFpdTus56IcWkyjXQ8UT0t96x2CByICJJ+HeJbRrv6
zWA8w7WRL769YQ1NlfiQNN1bs4c+xqtDlkjecdbZC65Mk6P7thQR3YQDEDVNg4xaJkpr
YmuA==
X-Gm-Message-State: AOAM533cdXGra12faWRK0rHnq5I0T8KPIMegGfQJz+EoOomDMVzbyvqu
iFM4jhtg6bizKCbY4Hej+encwl/bOWGDny3qXo3uMoYV
X-Google-Smtp-Source: ABdhPJz2MXS4vtj0L5Vyco3WbyYOUkLkF9QOn3RWhbkOWKRp+lVMg3RvYhTd83yWptqbeqyvhV5hNAdIWECjH8YPLW4=
X-Received: by 2002:a1f:2fd2:0:b0:351:cba8:ce79 with SMTP id
v201-20020a1f2fd2000000b00351cba8ce79mr735342vkv.27.1651543889942; Mon, 02
May 2022 19:11:29 -0700 (PDT)
In-Reply-To: <CADJx9Ldr9R9MiVjjBeP9058xoErCZCsuSxjrNUDdOzHc1Sh4xg@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_qjsyNc_uBKePC=ySsanu09XY8TS=6Uxmz0gZFc9fujxA@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>
<CADJx9Ldr9R9MiVjjBeP9058xoErCZCsuSxjrNUDdOzHc1Sh4xg@mail.gmail.com>
 by: Dan Stromberg - Tue, 3 May 2022 02:11 UTC

On Mon, May 2, 2022 at 2:25 AM jan via Python-list <python-list@python.org>
wrote:

> 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?
>

Median-of-3 helps, but it's still possible to construct inputs that make
quicksort break down to an O(n^2) algorithm in the worst case. These
inputs are much less common than sorting an already sorted, or
reverse-sorted list.


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

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor