Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #47017 > unrolled thread

Qucksort for Linked List

Started byxerofoify <xerofoify@gmail.com>
First post2016-12-02 10:14 -0800
Last post2016-12-03 08:05 +0100
Articles 20 on this page of 128 — 21 participants

Back to article view | Back to comp.lang.c++

Contents

  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 5 of 7 — ← Prev page 1 2 3 4 [5] 6 7  Next page →

#47446

FromGareth Owen <gwowen@gmail.com>
Date2016-12-19 19:31 +0000
Message-ID<87mvfr3ecg.fsf@gmail.com>
In reply to#47443
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

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

No.  You said average-case algorithmic complexity was worse.
That's not the same thing at all.

[toc] | [prev] | [next] | [standalone]

#47447

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2016-12-19 19:45 +0000
Message-ID<7pWdnfnfgoh0pcXFnZ2dnUU7-LHNnZ2d@giganews.com>
In reply to#47446
On 19/12/2016 19:31, Gareth Owen wrote:
> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:
>
>> 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.
>
> No.  You said average-case algorithmic complexity was worse.
> That's not the same thing at all.

No I said (as a complete guess I admit) the worst-case complexity was 
more likely (which may be wrong, don't much care).  However I have 
already said that I haven't actually looked at linked list qsort 
implementation and I don't intend to ever do so as I would never use 
qsort to sort a linked list.

/Flibble

[toc] | [prev] | [next] | [standalone]

#47449

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2016-12-19 20:19 +0000
Message-ID<bKmdndJWT_oj3cXFnZ2dnUU7-UGdnZ2d@giganews.com>
In reply to#47447
On 19/12/2016 19:45, Mr Flibble wrote:
> On 19/12/2016 19:31, Gareth Owen wrote:
>> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:
>>
>>> 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.
>>
>> No.  You said average-case algorithmic complexity was worse.
>> That's not the same thing at all.
>
> No I said (as a complete guess I admit) the worst-case complexity was
> more likely (which may be wrong, don't much care).  However I have
> already said that I haven't actually looked at linked list qsort
> implementation and I don't intend to ever do so as I would never use
> qsort to sort a linked list.

 From Wikipedia:

"Although quicksort can be implemented as a stable sort using linked 
lists, it will often suffer from poor pivot choices without random access."

https://en.wikipedia.org/wiki/Quicksort#Relation_to_other_algorithms

/Flibble

[toc] | [prev] | [next] | [standalone]

#47452

FromJuha Nieminen <nospam@thanks.invalid>
Date2016-12-20 07:18 +0000
Message-ID<o3alvq$9kn$1@adenine.netfront.net>
In reply to#47443
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
> So qsort is 40% slower than merge sort on a linked list eh Gareth 
> matey?.  So I was correct. 40. %. slower.

Your problem is that you don't understand what asymptotic complexity
and the big-O notation mean.

Your claim was about the asymptotic complexity of quicksort on
linked lists, not on absolute speed (ie. in practice the constant
factor in terms of computational complexity).

In addition to that, you weren't comparing quicksort on linked
lists to merge sort on linked lists. You were comparing quicksort
on linked lists to quicksort on random access arrays (and claiming
that the former is worse in terms of asymptotic complexity). It's
useless to now cling onto those quicksort vs mergesort numbers,
because that wasn't your original claim, nor what people objected to.

[toc] | [prev] | [next] | [standalone]

#47453

Fromleigh.v.johnston@googlemail.com
Date2016-12-20 04:31 -0800
Message-ID<49d489dd-7c85-4bbf-a6a3-1d3e8034d6b0@googlegroups.com>
In reply to#47452
Mr Flibble fully understands asymptotic complexity and Big-O notation.

Mr Flibble claimed that the worst case complexity was more likely due to poor pivot choice.

Again Mr Flibble didn't claim the former was worse in asymptotic complexity just that worst case complexity was more likely.

[toc] | [prev] | [next] | [standalone]

#47466

FromJuha Nieminen <nospam@thanks.invalid>
Date2016-12-21 07:08 +0000
Message-ID<o3d9os$2dmh$1@adenine.netfront.net>
In reply to#47453
leigh.v.johnston@googlemail.com wrote:
> just that worst case complexity was more likely.

No, he didn't claim that.

[toc] | [prev] | [next] | [standalone]

#47485

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2016-12-21 19:39 +0000
Message-ID<7tidnZmIoaYWR8fFnZ2dnUU7-dmdnZ2d@giganews.com>
In reply to#47466
On 21/12/2016 07:08, Juha Nieminen wrote:
> leigh.v.johnston@googlemail.com wrote:
>> just that worst case complexity was more likely.
>
> No, he didn't claim that.

Yes, he did.

[toc] | [prev] | [next] | [standalone]

#47490

FromGareth Owen <gwowen@gmail.com>
Date2016-12-21 20:54 +0000
Message-ID<87h95xovf2.fsf@gmail.com>
In reply to#47485
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

> On 21/12/2016 07:08, Juha Nieminen wrote:
>> leigh.v.johnston@googlemail.com wrote:
>>> just that worst case complexity was more likely.
>>
>> No, he didn't claim that.
>
> Yes, he did.

He claimed both.  They're equally wrong.

[toc] | [prev] | [next] | [standalone]

#47484

FromGareth Owen <gwowen@gmail.com>
Date2016-12-21 19:28 +0000
Message-ID<87poklozd5.fsf@gmail.com>
In reply to#47453
leigh.v.johnston@googlemail.com writes:

> Mr Flibble fully understands asymptotic complexity and Big-O notation.
>
> Mr Flibble claimed that the worst case complexity was more likely due
> to poor pivot choice.
>
> Again Mr Flibble didn't claim the former was worse in asymptotic
> complexity just that worst case complexity was more likely.


"AFAIK quicksort will not work with linked lists;"
"If by "works" you mean "works slowly, O(n)".
"By "O(n)" I actually meant "worse than O(n)*O(lg N)".

   *******************************************************
   ***** 'I actually meant "worse than O(n)*O(lg N)"' ****
   *******************************************************
   
I look forward to you Stuckling out of that.

[Incidentally, you *actually* meant 'worse than O(N * lg N)']

[toc] | [prev] | [next] | [standalone]

#47486

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2016-12-21 19:43 +0000
Message-ID<7tidnZiIoabdRsfFnZ2dnUU7-dmdnZ2d@giganews.com>
In reply to#47484
On 21/12/2016 19:28, Gareth Owen wrote:
> leigh.v.johnston@googlemail.com writes:
>
>> Mr Flibble fully understands asymptotic complexity and Big-O notation.
>>
>> Mr Flibble claimed that the worst case complexity was more likely due
>> to poor pivot choice.
>>
>> Again Mr Flibble didn't claim the former was worse in asymptotic
>> complexity just that worst case complexity was more likely.
>
>
> "AFAIK quicksort will not work with linked lists;"
> "If by "works" you mean "works slowly, O(n)".
> "By "O(n)" I actually meant "worse than O(n)*O(lg N)".
>
>    *******************************************************
>    ***** 'I actually meant "worse than O(n)*O(lg N)"' ****
>    *******************************************************
>
> I look forward to you Stuckling out of that.

"Due to poor pivot choice worst case performance will manifest more 
often and that is quadratic complexity."

So fuck off; I am right and you are wrong.

>
> [Incidentally, you *actually* meant 'worse than O(N * lg N)']

O(N)*O(lg N) is the same as O(N * lg N) (the latter being a simplification)

/Flibble

[toc] | [prev] | [next] | [standalone]

#47487

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2016-12-21 20:34 +0000
Message-ID<87vaudc971.fsf@bsb.me.uk>
In reply to#47486
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

> On 21/12/2016 19:28, Gareth Owen wrote:
>> leigh.v.johnston@googlemail.com writes:
>>
>>> Mr Flibble fully understands asymptotic complexity and Big-O notation.
>>>
>>> Mr Flibble claimed that the worst case complexity was more likely due
>>> to poor pivot choice.
>>>
>>> Again Mr Flibble didn't claim the former was worse in asymptotic
>>> complexity just that worst case complexity was more likely.
>>
>>
>> "AFAIK quicksort will not work with linked lists;"
>> "If by "works" you mean "works slowly, O(n)".
>> "By "O(n)" I actually meant "worse than O(n)*O(lg N)".
>>
>>    *******************************************************
>>    ***** 'I actually meant "worse than O(n)*O(lg N)"' ****
>>    *******************************************************
>>
>> I look forward to you Stuckling out of that.
>
> "Due to poor pivot choice worst case performance will manifest more
> often and that is quadratic complexity."

Is this a sociological claim rather than a technical one?  There's no
technical reason why the choice of pivot should be a poor one in a
linked list implementation, but the last time that was pointed out your
reply was simply "Nah", so maybe you do still think you are raising a
technical issue about algorithms.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#47489

FromGareth Owen <gwowen@gmail.com>
Date2016-12-21 20:53 +0000
Message-ID<87lgv9ovgn.fsf@gmail.com>
In reply to#47486
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

> "Due to poor pivot choice worst case performance will manifest more
> often and that is quadratic complexity."

Not true - Quicksort is O(N log(N)) on average even with the simplest
choice of pivot (the last element).

If you believe otherwise, please explain why.

> So fuck off; I am right and you are wrong.

Not true.  Maths isn't a strong point, is it?

[toc] | [prev] | [next] | [standalone]

#47491

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2016-12-21 20:58 +0000
Message-ID<48mdnel_q6ZhccfFnZ2dnUU7-VGdnZ2d@giganews.com>
In reply to#47489
On 21/12/2016 20:53, Gareth Owen wrote:
> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:
>
>> "Due to poor pivot choice worst case performance will manifest more
>> often and that is quadratic complexity."
>
> Not true - Quicksort is O(N log(N)) on average even with the simplest
> choice of pivot (the last element).
>
> If you believe otherwise, please explain why.

 From Wikipedia:

"Although quicksort can be implemented as a stable sort using linked 
lists, it will often suffer from poor pivot choices without random access."

https://en.wikipedia.org/wiki/Quicksort

>
>> So fuck off; I am right and you are wrong.
>
> Not true.  Maths isn't a strong point, is it?

This has nothing to do with maths; this is to do with analysing 
algorithmic complexity.  See Wikipedia above.

/Flibble

[toc] | [prev] | [next] | [standalone]

#47496

FromGareth Owen <gwowen@gmail.com>
Date2016-12-21 23:34 +0000
Message-ID<87bmw4n9g3.fsf@gmail.com>
In reply to#47491
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

>>> So fuck off; I am right and you are wrong.
>>
>> Not true.  Maths isn't a strong point, is it?
>
> This has nothing to do with maths; this is to do with analysing
> algorithmic complexity.

*facepalm*  Analysing algorithms is a discipline of mathematics.

> See Wikipedia above.

Nevertheless, if you were capable of doing the mathematics, you'd see
that the average case performance is still O(N log N).  The proof that
quicksort is O(N log N) on average is independent of the underlying data
structure.  The reason for this is that choosing a sane pivot (median of
nine say) is O(n), and you can do a fixed number of different O(n) at
each recursive step you don't change the algorithmic complexity (but you
might screw up the constants so badly that it runs much slower than
mergesort).

The Wikipedia section on "Selection based pivoting" describes a scheme
based on this fact.

Note also that proviso in Wikipedia is about *stable* quicksort, and
std::list::sort is *not* required to be stable.  Note also, that some
time ago I mentioned that mergesort is often preferred because it is
stable, where quicksort isn't.

> /Flibble

PS: Your killfile is broken

[toc] | [prev] | [next] | [standalone]

#47498

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2016-12-22 00:19 +0000
Message-ID<I_WdnVvyA_qSgcbFnZ2dnUU7-e2dnZ2d@giganews.com>
In reply to#47496
On 21/12/2016 23:34, Gareth Owen wrote:
> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:
>
>>>> So fuck off; I am right and you are wrong.
>>>
>>> Not true.  Maths isn't a strong point, is it?
>>
>> This has nothing to do with maths; this is to do with analysing
>> algorithmic complexity.
>
> *facepalm*  Analysing algorithms is a discipline of mathematics.

No, it isn't; it is a discipline of computer science and algorithmics.

[snip]


> Note also that proviso in Wikipedia is about *stable* quicksort, and
> std::list::sort is *not* required to be stable.  Note also, that some
> time ago I mentioned that mergesort is often preferred because it is
> stable, where quicksort isn't.

Wrong. std::list::sort *is* required to be stable.

/Flibble

[toc] | [prev] | [next] | [standalone]

#47815

FromJuha Nieminen <nospam@thanks.invalid>
Date2017-01-04 07:04 +0000
Message-ID<o4i6q8$2ocj$1@adenine.netfront.net>
In reply to#47498
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
>> *facepalm*  Analysing algorithms is a discipline of mathematics.
> 
> No, it isn't; it is a discipline of computer science and algorithmics.

That's like saying "that's not physics, it's astronomy".

> Wrong. std::list::sort *is* required to be stable.

Who was talking about std::list? The discussion was about linked lists.

[toc] | [prev] | [next] | [standalone]

#47820

FromDaniel <danielaparker@gmail.com>
Date2017-01-04 07:18 -0800
Message-ID<937c9a06-0973-4c53-a5e4-be46e0459354@googlegroups.com>
In reply to#47815
On Wednesday, January 4, 2017 at 2:04:52 AM UTC-5, Juha Nieminen wrote:
> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
> 
> > Wrong. std::list::sort *is* required to be stable.
> 
> Who was talking about std::list? The discussion was about linked lists.

Well, Gareth Owen wrote "std::list::sort is *not* required to be stable", and Mr 
Flibble replied correctly that it is. That was in the text that you snipped.

Regards,
Daniel

[toc] | [prev] | [next] | [standalone]

#47827

FromGareth Owen <gwowen@gmail.com>
Date2017-01-04 18:39 +0000
Message-ID<87k2aau0tp.fsf@gmail.com>
In reply to#47820
Daniel <danielaparker@gmail.com> writes:

> On Wednesday, January 4, 2017 at 2:04:52 AM UTC-5, Juha Nieminen wrote:
>> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
>> 
>> > Wrong. std::list::sort *is* required to be stable.
>> 
>> Who was talking about std::list? The discussion was about linked lists.
>
> Well, Gareth Owen wrote "std::list::sort is *not* required to be
> stable", and Mr Flibble replied correctly that it is. That was in the
> text that you snipped.

Yup.  In this regard, Flibble was entirely correct.

[toc] | [prev] | [next] | [standalone]

#47844

FromDaniel <danielaparker@gmail.com>
Date2017-01-05 07:29 -0800
Message-ID<59401c01-8b51-4f65-ae15-6d7ceaca717f@googlegroups.com>
In reply to#47827
On Wednesday, January 4, 2017 at 1:39:33 PM UTC-5, gwowen wrote:
> 
> Yup.  In this regard, Flibble was entirely correct.

You know, you could be setting a dangerous precedent by conceding something on 
comp.lang.c++. Where might it all end? Rick conceding that Flibble has a point 
about the lack of evidence for an historical jesus? Jerry conceding that voltage 
can exist without current? Flibble conceding that sausages are bad for you? Brian 
conceding that ::std is silly?

Better to just brazen it out, like most of us here.

Best regards,
Daniel

[toc] | [prev] | [next] | [standalone]

#47855

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2017-01-05 21:21 +0000
Message-ID<HMWdnY415Mx2JfPFnZ2dnUU7-amdnZ2d@giganews.com>
In reply to#47844
On 05/01/2017 15:29, Daniel wrote:
> On Wednesday, January 4, 2017 at 1:39:33 PM UTC-5, gwowen wrote:
>>
>> Yup.  In this regard, Flibble was entirely correct.
>
> You know, you could be setting a dangerous precedent by conceding something on
> comp.lang.c++. Where might it all end? Rick conceding that Flibble has a point
> about the lack of evidence for an historical jesus? Jerry conceding that voltage
> can exist without current? Flibble conceding that sausages are bad for you? Brian
> conceding that ::std is silly?
>
> Better to just brazen it out, like most of us here.

Sausages are bad for me? Oh noes! Luckily I have just started dieting so 
I won't be eating many sausages.

/Flibble

[toc] | [prev] | [next] | [standalone]

Page 5 of 7 — ← Prev page 1 2 3 4 [5] 6 7  Next page →

Back to top | Article view | comp.lang.c++

csiph-web