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

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

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:09 +0100
Organization albasani.net
Message-ID <20161202220931.321c2349@maxa-pc> (permalink)
References <dfa00771-7568-443b-ab45-174f0749a176@googlegroups.com> <K8mdnXD8M6gvVdzFnZ2dnUU7-aednZ2d@giganews.com>

Show all headers | View raw

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.




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