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

Groups > comp.lang.c++ > #47032

Re: Qucksort for Linked List

From Melzzzzz <mel@zzzzz.com>
Newsgroups comp.lang.c++
Subject Re: Qucksort for Linked List
Date 2016-12-02 22:37 +0100
Organization albasani.net
Message-ID <20161202223747.59c00cde@maxa-pc> (permalink)
References <dfa00771-7568-443b-ab45-174f0749a176@googlegroups.com> <K8mdnXD8M6gvVdzFnZ2dnUU7-aednZ2d@giganews.com> <20161202220931.321c2349@maxa-pc> <zMOdnVY9K6mJetzFnZ2dnUU7-IWdnZ2d@giganews.com>

Show all headers | View raw

On Fri, 2 Dec 2016 21:26:46 +0000
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:

> On 02/12/2016 21:09, Melzzzzz wrote:
> > On Fri, 2 Dec 2016 19:17:08 +0000
> > Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
> >  
> >>
> >> AFAIK quicksort will not work with linked lists; try merge sort
> >> instead.  
> >
> > Quick sort will work with linked lists alright if swap is value
> > based. Anyway I have found that algorithms that change order of
> > linked list nodes are bad for cache efficiency on x86.
> > Surprisingly quick sort that uses just bidirectional iterator is
> > quite efficient on x86. So that it is much faster then std libs
> > merge sort.  
> 
> O(n) is never "quite efficient".
> 
> /Flibble
> 

Try it out. It is not that bad at all is you go from beginning from one
side and from end of array on the other side. Surprisingly finding out
pivot is not slow at all if list nodes are successive.


-- 
press any key to continue or any other to quit

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web