Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #47017 > unrolled thread
| Started by | xerofoify <xerofoify@gmail.com> |
|---|---|
| First post | 2016-12-02 10:14 -0800 |
| Last post | 2016-12-03 08:05 +0100 |
| Articles | 20 on this page of 128 — 21 participants |
Back to article view | Back to comp.lang.c++
Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 10:14 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 19:17 +0000
Re: Qucksort for Linked List Melzzzzz <mel@zzzzz.com> - 2016-12-02 22:09 +0100
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 21:26 +0000
Re: Qucksort for Linked List Melzzzzz <mel@zzzzz.com> - 2016-12-02 22:37 +0100
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 21:41 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-12 13:16 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-12 18:32 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-12 18:34 +0000
Re: Qucksort for Linked List asetofsymbols@gmail.com - 2016-12-12 10:44 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-12 21:30 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-13 07:26 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-13 17:51 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-13 14:52 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-14 10:26 +0000
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-14 13:05 +0100
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-14 14:06 +0000
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-14 16:59 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-14 20:19 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-14 21:23 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-14 21:42 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-14 22:43 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-16 11:02 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-16 23:00 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-16 23:00 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-17 20:17 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 21:15 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 21:49 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 21:51 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 21:52 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 21:56 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 22:04 +0000
Re: Qucksort for Linked List Paavo Helde <myfirstname@osa.pri.ee> - 2016-12-19 00:22 +0200
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-19 00:18 +0100
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-19 08:58 +0100
Re: Qucksort for Linked List gwowen <gwowen@gmail.com> - 2016-12-19 06:17 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 20:14 +0000
Re: Qucksort for Linked List woodbrian77@gmail.com - 2016-12-23 10:55 -0800
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2016-12-23 12:08 -0800
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-27 10:39 +0100
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 17:48 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 17:53 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 18:52 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 19:06 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 19:17 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 21:05 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 21:15 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 21:21 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-27 21:29 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-27 21:33 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-28 10:03 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-28 15:34 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-29 09:38 +0100
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-28 16:40 +0000
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2016-12-28 08:55 -0800
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-28 17:02 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-28 17:12 +0000
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-28 17:21 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-29 11:05 -0600
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-29 17:43 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-30 09:48 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-30 11:37 +0000
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-30 13:23 +0100
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-29 11:00 +0100
Re: Qucksort for Linked List David Brown <david.brown@hesbynett.no> - 2016-12-29 09:43 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 22:56 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-18 22:52 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-18 23:07 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 05:48 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-19 08:09 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-19 08:06 +0000
Re: Qucksort for Linked List leigh.v.johnston@googlemail.com - 2016-12-19 04:46 -0800
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-19 15:04 +0100
Re: Qucksort for Linked List gwowen <gwowen@gmail.com> - 2016-12-19 06:40 -0800
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-19 18:48 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 18:53 +0000
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-19 21:26 +0100
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 20:32 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 19:09 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 19:14 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-19 19:31 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 19:45 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-19 20:19 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-20 07:18 +0000
Re: Qucksort for Linked List leigh.v.johnston@googlemail.com - 2016-12-20 04:31 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-21 07:08 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-21 19:39 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 20:54 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 19:28 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-21 19:43 +0000
Re: Qucksort for Linked List Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-12-21 20:34 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 20:53 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-21 20:58 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-21 23:34 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-22 00:19 +0000
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2017-01-04 07:04 +0000
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2017-01-04 07:18 -0800
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2017-01-04 18:39 +0000
Re: Qucksort for Linked List Daniel <danielaparker@gmail.com> - 2017-01-05 07:29 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2017-01-05 21:21 +0000
Re: Qucksort for Linked List Ian Collins <ian-news@hotmail.com> - 2017-01-06 10:35 +1300
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-22 21:43 -0800
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-22 22:09 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 17:00 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-23 12:03 -0800
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 20:25 +0000
Re: Qucksort for Linked List Gareth Owen <gwowen@gmail.com> - 2016-12-23 20:56 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 22:02 +0000
Re: Qucksort for Linked List Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-23 22:14 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-29 13:56 -0800
Re: Qucksort for Linked List Mr Flibble <flibble@i42.co.uk> - 2016-12-29 23:26 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-29 20:25 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2017-01-04 07:07 +0000
Re: Qucksort for Linked List Tim Rentsch <txr@alumni.caltech.edu> - 2017-01-26 22:40 -0800
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 13:47 -0800
Re: Qucksort for Linked List ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:38 -0500
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 14:53 -0800
Re: Qucksort for Linked List Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-02 19:50 -0500
Re: Qucksort for Linked List ruben safir <ruben@mrbrklyn.com> - 2016-12-02 21:17 -0500
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 20:44 -0800
Re: Qucksort for Linked List xerofoify <xerofoify@gmail.com> - 2016-12-02 20:52 -0800
Re: Qucksort for Linked List Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-12-03 11:07 +0000
Re: Qucksort for Linked List ruben safir <ruben@mrbrklyn.com> - 2016-12-03 13:38 -0500
Re: Qucksort for Linked List Öö Tiib <ootiib@hot.ee> - 2016-12-03 01:46 -0800
Re: Qucksort for Linked List Juha Nieminen <nospam@thanks.invalid> - 2016-12-12 13:18 +0000
Re: Qucksort for Linked List "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 01:16 +0100
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-03 08:25 +0100
Re: Qucksort for Linked List bartekltg <bartekltg@gmail.com> - 2016-12-03 08:05 +0100
Page 4 of 7 — ← Prev page 1 2 3 [4] 5 6 7 Next page →
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2016-12-30 09:48 +0100 |
| Message-ID | <o456uh$1hh$1@dont-email.me> |
| In reply to | #47724 |
On 29/12/16 18:43, Gareth Owen wrote:
> David Brown <david.brown@hesbynett.no> writes:
>
>> And as for "bounded" and "unbounded", you have to be very careful of
>> what you mean. These terms refer to order, not size. The set
>>
>> {x ∈ ℝ : x > 0 and x < 1}
>>
>> is infinite and unbounded (since the limits, 0 and 1, are not in the
>> set), while the set
>
> That's not what we were taught re bounded and unbounded. The definition
> I was taught was to do with there being a metric, and that there was a
(You need an order, not a metric - though a metric can give you an order.)
>
> ∃r ∈ ℝ such that ||x|| < r ∀x ∈ S
>
The set {x ∈ ℝ : x > 0 and x < 1} is bounded within ℝ, but not as a
stand-alone set by itself, as the limits are not inside the set. That's
why we have to be careful about the details here.
So the set of non-negative integers is normally called "unbounded"
because it has no limit within the set. But viewed as ordinals, they
/have/ a limit - ω₀, so within the set of countable ordinals, the finite
ordinals are infinite but bounded.
It is a /long/ time since I was at university, so I can't be entirely
sure that my terminology is correct here. But I think you can
understand what I mean.
>> {x ∈ ℝ : x ≥ 0 and x ≤ 1}
>>
>> is infinite and bounded.
>
> This is closer to the definition I know for open/closed (but not the same)
>
>> (All finite sets are bounded.)
>
> Still true.
>
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-30 11:37 +0000 |
| Message-ID | <87wpeh1wbv.fsf@gmail.com> |
| In reply to | #47749 |
David Brown <david.brown@hesbynett.no> writes:
>> That's not what we were taught re bounded and unbounded. The definition
>> I was taught was to do with there being a metric, and that there was a
>
> (You need an order, not a metric - though a metric can give you an order.)
>
>>
>> ∃r ∈ ℝ such that ||x|| < r ∀x ∈ S
>>
>
> The set {x ∈ ℝ : x > 0 and x < 1} is bounded within ℝ, but not as a
> stand-alone set by itself, as the limits are not inside the set. That's
> why we have to be careful about the details here.
Again, "contains all its limit points" is one of the usual equivalent
definitions of closed set. For that you don't need an order, but you do
need a topology.
> So the set of non-negative integers is normally called "unbounded"
> because it has no limit within the set. But viewed as ordinals, they
> /have/ a limit - ω₀, so within the set of countable ordinals, the finite
> ordinals are infinite but bounded.
Then we were taught different nomenclature.
> It is a /long/ time since I was at university, so I can't be entirely
> sure that my terminology is correct here. But I think you can
> understand what I mean.
Oh, I understand completely, you're just using different terms than I'm
used to. As you gave your definitions, it was totally comprehensible.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2016-12-30 13:23 +0100 |
| Message-ID | <o45jhn$9ch$1@dont-email.me> |
| In reply to | #47753 |
On 30/12/16 12:37, Gareth Owen wrote:
> David Brown <david.brown@hesbynett.no> writes:
>
>>> That's not what we were taught re bounded and unbounded. The definition
>>> I was taught was to do with there being a metric, and that there was a
>>
>> (You need an order, not a metric - though a metric can give you an order.)
>>
>>>
>>> ∃r ∈ ℝ such that ||x|| < r ∀x ∈ S
>>>
>>
>> The set {x ∈ ℝ : x > 0 and x < 1} is bounded within ℝ, but not as a
>> stand-alone set by itself, as the limits are not inside the set. That's
>> why we have to be careful about the details here.
>
> Again, "contains all its limit points" is one of the usual equivalent
> definitions of closed set. For that you don't need an order, but you do
> need a topology.
>
It sounds like I am mixing up my definitions here, and I'm grateful to
you for stirring up my old memories and bringing them to the surface again.
When I had been talking about "bounded", I really meant /closed and
bounded/ - i.e., the bounds are within the set. But you are correct -
to be bounded, a set needs to have limits but the limits do not have to
be in the set.
>> So the set of non-negative integers is normally called "unbounded"
>> because it has no limit within the set. But viewed as ordinals, they
>> /have/ a limit - ω₀, so within the set of countable ordinals, the finite
>> ordinals are infinite but bounded.
>
> Then we were taught different nomenclature.
No, you just remember it better :-)
>
>> It is a /long/ time since I was at university, so I can't be entirely
>> sure that my terminology is correct here. But I think you can
>> understand what I mean.
>
> Oh, I understand completely, you're just using different terms than I'm
> used to. As you gave your definitions, it was totally comprehensible.
>
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2016-12-29 11:00 +0100 |
| Message-ID | <o42mob$n4k$1@dont-email.me> |
| In reply to | #47694 |
On 28/12/16 18:12, Mr Flibble wrote:
> On 28/12/2016 16:55, Daniel wrote:
>> On Wednesday, December 28, 2016 at 11:41:06 AM UTC-5, Mr Flibble wrote:
>>>
>>> There is no such thing as the set of finite ordinals as there
>>> is an infinite number of ordinals;
>>
>> The set of finite ordinals is infinite.
>
> Bullshit; you cannot have a set of infinite things as infinity is,
> unlike a set, unbounded. Countable infinities are unbounded just like
> uncountable infinities despite what Wikipedia says.
>
Sets don't have to be finite - why on earth would you think that?
And as for "bounded" and "unbounded", you have to be very careful of
what you mean. These terms refer to order, not size. The set
{x ∈ ℝ : x > 0 and x < 1}
is infinite and unbounded (since the limits, 0 and 1, are not in the
set), while the set
{x ∈ ℝ : x ≥ 0 and x ≤ 1}
is infinite and bounded.
(All finite sets are bounded.)
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2016-12-29 09:43 +0100 |
| Message-ID | <o42i7t$9bj$1@dont-email.me> |
| In reply to | #47691 |
On 28/12/16 17:40, Mr Flibble wrote: > On 28/12/2016 09:03, David Brown wrote:ω. >> >> There is no such thing as "the set of ordinals". There /is/ "the set of >> all finite ordinals", which is ω, since each ordinal is the set > > Bullshit. There is no such thing as the set of finite ordinals as there > is an infinite number of ordinals; you have also been drinking the > koolaid like that idiot Owen. > /You/ referred to "the set of ordinals" a couple of posts back. Now you don't believe in the "set of /finite/ ordinals", which is clearly going to be a subset of the set /you/ mentioned? Perhaps you are unsure about what a "set" actually is, or what an "ordinal" is, or what "finite" means?
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-18 22:56 +0000 |
| Message-ID | <87lgvckfso.fsf@gmail.com> |
| In reply to | #47417 |
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:
> As I can read you like a book and anticipate your next reply: yes the
> complex plane is an abstraction and no I don't think complex number
> theory is bullshit. This is not the same kind of abstraction as made
> with projective geometry.
"God created the integers. Everything else is the work of man."
-- Leonard Kronecker (he was a mathematician, you won't know him)
In other words, its all abstractions, darling.
Instead of claiming to read me like a book, go read an actual book.
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-18 22:52 +0000 |
| Message-ID | <87pokokfyd.fsf@gmail.com> |
| In reply to | #47416 |
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > No I don't dismiss the harder stuff; I dismiss bollocks such as > projective geometry. It isn't mathematics it is an abstraction of > mathematics. What a terrifically, splendiferously meaningless statement. Mathematics is not a strength, is it? >> Tell us again how linked lists change the order of quicksort. > > See my other reply. Offered no evidence or subject knowledge to back up your assertion. Clearly mathematics is not a strength. >> Show your working. > > Fuck off you self important cunt. Now you just sound like Jerry Stuckle (albeit with a more enjoyably Anglo-Saxon vocabulary). Maybe best stick to saying "sausages" and pissing off fundies, yeah? Clearly, that is where you true abilities lie.
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2016-12-18 23:07 +0000 |
| Message-ID | <QKqdnQYPmbQ_i8rFnZ2dnUU7-fPNnZ2d@giganews.com> |
| In reply to | #47424 |
On 18/12/2016 22:52, Gareth Owen wrote: > Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > >> No I don't dismiss the harder stuff; I dismiss bollocks such as >> projective geometry. It isn't mathematics it is an abstraction of >> mathematics. > > What a terrifically, splendiferously meaningless statement. > Mathematics is not a strength, is it? > >>> Tell us again how linked lists change the order of quicksort. >> >> See my other reply. > > Offered no evidence or subject knowledge to back up your assertion. > Clearly mathematics is not a strength. > >>> Show your working. >> >> Fuck off you self important cunt. > > Now you just sound like Jerry Stuckle (albeit with a more enjoyably > Anglo-Saxon vocabulary). Maybe best stick to saying "sausages" and > pissing off fundies, yeah? > > Clearly, that is where you true abilities lie. It is ironic that you mentioned Stuckle as I am now classifying you the same as I classify him... *plonk* /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-19 05:48 +0000 |
| Message-ID | <87vaug5v08.fsf@gmail.com> |
| In reply to | #47426 |
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > It is ironic that you mentioned Stuckle as I am now classifying you > the same as I classify him... *plonk* Oh deary. Did getting called out on your nonsense hurt you feelings? Try saying sausages a few times.
[toc] | [prev] | [next] | [standalone]
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Date | 2016-12-19 08:09 +0000 |
| Message-ID | <o384jc$1irf$2@adenine.netfront.net> |
| In reply to | #47416 |
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote: >> Show your working. > > Fuck off you self important cunt. You do realize that's pretty much a concession? If you were an honest person, you would simply admit outright that you were wrong. Instead, you have to make the admission indirectly by resorting to insults.
[toc] | [prev] | [next] | [standalone]
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Date | 2016-12-19 08:06 +0000 |
| Message-ID | <o384ef$1irf$1@adenine.netfront.net> |
| In reply to | #47394 |
Tim Rentsch <txr@alumni.caltech.edu> wrote: > There is no reason that the choice of a pivot value has to be any > worse in a linked list quicksort than an array quicksort. In > particular, the entire linked list can be scanned, any constant > number of times, looking for a pivot value, without changing the > order of the algorithm. In addition, it's possible to optimize the constant factor of the computational complexity, for example if you would want to use the median-of-the-first-last-and-middle pivot method: The very first time you perform the partitioning just choose the first element as the pivot, but as you distribute the nodes into the two new lists, keep note of the last and middle elements of said lists. Then when partitioning them, you can choose their pivots from those three nodes. No need to scan the lists.
[toc] | [prev] | [next] | [standalone]
| From | leigh.v.johnston@googlemail.com |
|---|---|
| Date | 2016-12-19 04:46 -0800 |
| Message-ID | <c2dff3d8-e8f3-4c2a-901c-21682bb22918@googlegroups.com> |
| In reply to | #47432 |
Answer me this: why do all std::list::sort implementations use merge sort rather than qsort? Sausage sorting is a tricky business.
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Date | 2016-12-19 15:04 +0100 |
| Message-ID | <o38pcj$vja$1@node2.news.atman.pl> |
| In reply to | #47434 |
On 19.12.2016 13:46, leigh.v.johnston@googlemail.com wrote: > Answer me this: why do all std::list::sort implementations use merge sort rather than qsort? > > Sausage sorting is a tricky business. And why std::sort uses introsort (qsort + heapsort as fallback), and not, for example, in place merge sort? Both have complexity O(n log n). Because introsort is faster. Mergesort run log_2(n) times through the whole list. Qsort, 2 ln(2) log_2(n) = 1.39 log_2(n) times in average case (with median pivot a bit better, 1.188). Qsort for list is ~40% worse. But it is still a valid sorting methods for lists. Just not the best one nor the easiest one. bartekltg
[toc] | [prev] | [next] | [standalone]
| From | gwowen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-19 06:40 -0800 |
| Message-ID | <42d98296-3339-4814-8ba9-d8d71607e5bc@googlegroups.com> |
| In reply to | #47434 |
On Monday, December 19, 2016 at 12:46:44 PM UTC, leigh.v....@googlemail.com wrote: > Answer me this: why do all std::list::sort implementations use merge sort > rather than qsort? LMGTFY: http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort https://www.quora.com/What-algorithm-do-popular-C++-compilers-use-for-std-sort-and-std-stable_sort Short answer: These days they mostly use introsort. And they do so because introsort is faster, particularly on almost-sorted datasets, and its good to avoid pathological behaviour, even if it isn't necessary to meet the average-case complexity. They used to use merge-sort, because merge-sort is stable, and quicksort/intro-sort is unstable unless you do some extra bookkeeping (which does not increase the big-Oh behaviour). NB: All those intro/quick/merge sort behaviours are the same for arrays, vectors and other containers.
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Date | 2016-12-19 18:48 +0100 |
| Message-ID | <o396gv$cqe$1@node2.news.atman.pl> |
| In reply to | #47439 |
On 19.12.2016 15:40, gwowen wrote: > On Monday, December 19, 2016 at 12:46:44 PM UTC, > leigh.v....@googlemail.com wrote: >> Answer me this: why do all std::list::sort implementations use >> merge sort rather than qsort? > > LMGTFY: At leas you could do it correctly. > http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort > > Short answer: These days they mostly use introsort. And they do so > because introsort is faster, particularly on almost-sorted datasets, > and its good to avoid pathological behaviour, even if it isn't > necessary to meet the average-case complexity. And yo get it from what? From this sentence from the first answer: "...std::sort is implemented as a intro-sort (introspective sort),..." Jerry Coffin didn't understand the question. When you go to the second answer or to the second thread: http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort You get the real answer. You can also look at the code in your computer. In my it is mergesort gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 > NB: All those intro/quick/merge sort behaviours are the same for > arrays, vectors and other containers. What do you mean? bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-19 18:53 +0000 |
| Message-ID | <87inqf698n.fsf@gmail.com> |
| In reply to | #47440 |
bartekltg <bartekltg@gmail.com> writes: > Jerry Coffin didn't understand the question. When you go to the > second answer or to the second thread: > > http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort > > You get the real answer. I stand corrected[0]. See also here. http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117 Leigh please note: The answer is *not* because quicksort on linked lists is worse O(n log n) on average. > What do you mean? That intro-sort is a better choice that quicksort for sorting all sorts of containers for exactly the same reasons its a better choice for sorting lists. Which is true. [0] Well, I suppose I could just shout abuse at you, or call you a troll.
[toc] | [prev] | [next] | [standalone]
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Date | 2016-12-19 21:26 +0100 |
| Message-ID | <o39fpj$jdq$1@node1.news.atman.pl> |
| In reply to | #47441 |
On 19.12.2016 19:53, Gareth Owen wrote: > bartekltg <bartekltg@gmail.com> writes: > >> Jerry Coffin didn't understand the question. When you go to the >> second answer or to the second thread: >> >> http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort >> >> You get the real answer. > > I stand corrected[0]. See also here. > > http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117 > > Leigh please note: The answer is *not* because quicksort on linked lists > is worse O(n log n) on average. I'm not sure, did you change your opinion? std::list::sort is almost (*) always mergesort *) I didn't see implementation with different algorithm, but of course I can't be sure there is none ;-) >> What do you mean? > > That intro-sort is a better choice that quicksort for sorting all sorts > of containers for exactly the same reasons its a better choice for > sorting lists. Containers with random access, so vector (array...) implemented in continuous memory block. Merge sort do _less_ work, but mergesort need either additional (linear in size) memory or quite complicated tricks, while qsort is quite cache friendly. As a results, qsort work faster on vector and similar containers. Both, disadvantage of mergesort and advantage of qsort, disappears in the case of a list. Just write both and compare. For a list mergesort (written in proper way, look at std::list::sort) is faster. bartekltg
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-19 20:32 +0000 |
| Message-ID | <87lgvb8xtg.fsf@gmail.com> |
| In reply to | #47450 |
bartekltg <bartekltg@gmail.com> writes: > On 19.12.2016 19:53, Gareth Owen wrote: >> bartekltg <bartekltg@gmail.com> writes: >> >>> Jerry Coffin didn't understand the question. When you go to the >>> second answer or to the second thread: >>> >>> http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort >>> >>> You get the real answer. >> >> I stand corrected[0]. See also here. >> >> http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117 >> >> Leigh please note: The answer is *not* because quicksort on linked lists >> is worse O(n log n) on average. > > > I'm not sure, did you change your opinion? Which opinion? > std::list::sort is almost (*) always mergesort I agree with this now. > *) I didn't see implementation with different algorithm, > but of course I can't be sure there is none ;-) Of course. > As a results, qsort work faster on vector and similar containers. But only by a multiplicative factor, so time-big-Oh sense they're the same. Or rather intro-sort and merge-sort are big-Oh-the-same (worst case n*log n) but the multiplicative factor changes depending on whether you can do random access or you have to traverse the list.
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2016-12-19 19:09 +0000 |
| Message-ID | <ve-dndpVRPIarcXFnZ2dnUU7-RnNnZ2d@giganews.com> |
| In reply to | #47439 |
On 19/12/2016 14:40, gwowen wrote: > On Monday, December 19, 2016 at 12:46:44 PM UTC, leigh.v....@googlemail.com wrote: >> Answer me this: why do all std::list::sort implementations use merge sort >> rather than qsort? > > LMGTFY: > http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort > https://www.quora.com/What-algorithm-do-popular-C++-compilers-use-for-std-sort-and-std-stable_sort > > Short answer: These days they mostly use introsort. And they do so because introsort is faster, particularly on almost-sorted datasets, and its good to avoid pathological behaviour, even if it isn't necessary to meet the average-case complexity. > > They used to use merge-sort, because merge-sort is stable, and quicksort/intro-sort is unstable unless you do some extra bookkeeping (which does not increase the big-Oh behaviour). > > NB: All those intro/quick/merge sort behaviours are the same for arrays, vectors and other containers. So qsort is 40% slower than merge sort on a linked list eh Gareth matey?. So I was correct. 40. %. slower. If I am totally honest I have not actually looked at the implementation of qsort for linked lists I just had a gut feeling that it would be non-optimal compared to other methods as qsort was designed for arrays however you are forgetting one very important thing: Being wrong (even deliberately so) on the Internet is the quickest way to illicit correct information on the Internet. /Flibble P.S. Liver and onions tonight not sausages.
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2016-12-19 19:14 +0000 |
| Message-ID | <ve-dndVVRPIFrMXFnZ2dnUU7-RmdnZ2d@giganews.com> |
| In reply to | #47443 |
On 19/12/2016 19:09, Mr Flibble wrote: > > Being wrong (even deliberately so) on the Internet is the quickest way > to illicit correct information on the Internet. s/illicit/elicit/ /Flibble
[toc] | [prev] | [next] | [standalone]
Page 4 of 7 — ← Prev page 1 2 3 [4] 5 6 7 Next page →
Back to top | Article view | comp.lang.c++
csiph-web