Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #164751
| From | Meredith Montgomery <mmontgomery@levado.to> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: on legal definitions of a certain algorithm |
| Date | 2022-02-02 11:10 -0300 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <86czk59x5s.fsf@levado.to> (permalink) |
| References | (3 earlier) <86h79tomko.fsf@linuxsc.com> <86sft55qgd.fsf_-_@levado.to> <87sft4di1w.fsf@bsb.me.uk> <868ruw1vmh.fsf@levado.to> <quicksort-20220131041344@ram.dialup.fu-berlin.de> |
ram@zedat.fu-berlin.de (Stefan Ram) writes:
> Meredith Montgomery <mmontgomery@levado.to> writes:
>> while True:
>> while True:
>> i = i + 1
>> if A[i] >= pivot:
>> break
>
> I'm not sure whether, in Python, this loop will ever exit!
It won't. I messed up the indentation. Here it is again.
--8<---------------cut here---------------start------------->8---
def qsort(A, lo, hi):
if lo < hi:
p = partition(A, lo, hi)
qsort(A, lo, p)
qsort(A, p + 1, hi)
return A
def partition(A, lo, hi):
pivot = A[lo]
i = lo - 1
j = hi + 1
while True:
while True:
i = i + 1
if A[i] >= pivot:
break
while True:
j = j - 1
if A[j] <= pivot:
break
if i >= j:
return j
A[i], A[j] = A[j], A[i]
--8<---------------cut here---------------end--------------->8---
>>I had a feeling his problem was with functional programming. He seemed
>>to think it was impossible to call anything quicksort that did not sort
>>in place.
>
> I wrote this quicksort that's not only functional, but also visual:
Beautiful! But is it ``quicksort''?
>
> .--------------------------------------------.
> | .---------------. |
> | | .----. | |
> | | ->| | | |
> .-------. | | | <= | -> | |
> [] --->| qsort |---> [] | | x ->| | | |
> '-------' | | '----' | |
> | '---------------' |
> | | |
> | v .---. |
> | .------. .-------. | | |
> .---------------. | xs -->| grep | ->| qsort | --->| | |
> | .---. | | '------' '-------' | j | |
> | x -->| | | .-------. | .------. | o | |
> | | : | -> |-->| qsort | ->| x --->| list | --------------->| i | --> |
> | xs ->| | | '-------' | '------' | n | |
> | '___' | | .------. .-------. | | |
> '---------------' | xs -->| grep | ->| qsort | --->| | |
> | '------' '-------' | | |
> | ^ '---' |
> | | |
> | .---------------. |
> | | .----. | |
> | | x ->| | | |
> | | | < | -> | |
> | | ->| | | |
> | | '----' | |
> | '---------------' |
> '--------------------------------------------'
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
ben.usenet@bsb.me.uk Arslan RK <itsarslanfiverr@gmail.com> - 2022-01-17 10:08 -0800
Re: ben.usenet@bsb.me.uk scott@slp53.sl.home (Scott Lurndal) - 2022-01-17 18:15 +0000
Re: ben.usenet@bsb.me.uk Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2022-01-17 18:24 +0000
Re: ben.usenet@bsb.me.uk Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-01-17 10:45 -0800
Re: ben.usenet@bsb.me.uk Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-17 20:43 +0000
Re: ben.usenet@bsb.me.uk "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-01-17 14:03 -0800
Re: **********@b*****.uk Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-23 15:48 +0000
Re: **********@b*****.uk Richard Damon <Richard@Damon-Family.org> - 2022-01-23 13:13 -0500
Re: **********@b*****.uk Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-23 19:10 -0800
on legal definitions of a certain algorithm (Was: Re: **********@b*****.uk) Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 10:00 -0300
Re: on legal definitions of a certain algorithm Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-01-30 21:34 +0000
Re: on legal definitions of a certain algorithm Meredith Montgomery <mmontgomery@levado.to> - 2022-01-30 23:34 -0300
Re: on legal definitions of a certain algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-30 20:58 -0800
Re: on legal definitions of a certain algorithm Meredith Montgomery <mmontgomery@levado.to> - 2022-02-02 11:10 -0300
Re: on legal definitions of a certain algorithm Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-01-30 21:04 -0800
Re: **********@b*****.uk Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-01-23 11:15 -0800
This newsgroup (Was: for some totally inexplicable reason, **********@b*****.uk) gazelle@shell.xmission.com (Kenny McCormack) - 2022-01-23 20:09 +0000
csiph-web