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

Qucksort for Linked List

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

#47017 — Qucksort for Linked List

From	xerofoify <xerofoify@gmail.com>
Date	2016-12-02 10:14 -0800
Subject	Qucksort for Linked List
Message-ID	<dfa00771-7568-443b-ab45-174f0749a176@googlegroups.com>

I am trying to write a linked list quicksort that works by only swapping the Nodes and was wondering why the below code does not work as I can't see why:
//Swap function for nodes
154         void swap ( Node* a, Node* b )
155         {   Node t = *a;      *a = *b;       *b = t;    }
156         //Partion function for nodes
157         Node* partition(Node *l, Node *h)
158         {   
159             T x  = h->data_;
160 
161             Node *i = l->prev_; 
162             for (Node *j = l; j != h; j = j->next_) {
163                 if (j->data_ <= x) {
164                     i = (i == nullptr)? l : i->next_;
165                     swap(i, j);
166                 }
167             } 
168             i = (i == nullptr)? l : i->next_;
169             swap(i, h);
170             return i;
171         }
172         /*this does qsort recursively on the elements from the Node at the first iterator passed up to
173         and including the Node at iterator two*/
174         void qSortrecursive(iterator first, iterator second) {
175                 Node* h = first.getNode();
176                 Node* l = second.getNode();
177                 if (h != NULL && l != h && l != h->next_)
178                 {
179                         struct Node *p = partition(l, h);
180                         qSortrecursive(l, p->prev_);
181                         qSortrecursive(p->next_, h);
182                 }
183         }

[toc] | [next] | [standalone]

#47018

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-02 19:17 +0000
Message-ID	<K8mdnXD8M6gvVdzFnZ2dnUU7-aednZ2d@giganews.com>
In reply to	#47017

On 02/12/2016 18:14, xerofoify wrote:
> I am trying to write a linked list quicksort that works by only swapping the Nodes and was wondering why the below code does not work as I can't see why:
> //Swap function for nodes
> 154         void swap ( Node* a, Node* b )
> 155         {   Node t = *a;      *a = *b;       *b = t;    }
> 156         //Partion function for nodes
> 157         Node* partition(Node *l, Node *h)
> 158         {
> 159             T x  = h->data_;
> 160
> 161             Node *i = l->prev_;
> 162             for (Node *j = l; j != h; j = j->next_) {
> 163                 if (j->data_ <= x) {
> 164                     i = (i == nullptr)? l : i->next_;
> 165                     swap(i, j);
> 166                 }
> 167             }
> 168             i = (i == nullptr)? l : i->next_;
> 169             swap(i, h);
> 170             return i;
> 171         }
> 172         /*this does qsort recursively on the elements from the Node at the first iterator passed up to
> 173         and including the Node at iterator two*/
> 174         void qSortrecursive(iterator first, iterator second) {
> 175                 Node* h = first.getNode();
> 176                 Node* l = second.getNode();
> 177                 if (h != NULL && l != h && l != h->next_)
> 178                 {
> 179                         struct Node *p = partition(l, h);
> 180                         qSortrecursive(l, p->prev_);
> 181                         qSortrecursive(p->next_, h);
> 182                 }
> 183         }

AFAIK quicksort will not work with linked lists; try merge sort instead.

/Flibble

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

#47028

From	Melzzzzz <mel@zzzzz.com>
Date	2016-12-02 22:09 +0100
Message-ID	<20161202220931.321c2349@maxa-pc>
In reply to	#47018

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

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

#47030

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-02 21:26 +0000
Message-ID	<zMOdnVY9K6mJetzFnZ2dnUU7-IWdnZ2d@giganews.com>
In reply to	#47028

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

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

#47032

From	Melzzzzz <mel@zzzzz.com>
Date	2016-12-02 22:37 +0100
Message-ID	<20161202223747.59c00cde@maxa-pc>
In reply to	#47030

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

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

#47033

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-02 21:41 +0000
Message-ID	<Zp6dncv6Cb8_d9zFnZ2dnUU7-cOdnZ2d@giganews.com>
In reply to	#47032

On 02/12/2016 21:37, Melzzzzz wrote:
> 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.

I am sure what you are saying is fine if n is small however n isn't 
always small.

/Flibble

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

#47312

From	Juha Nieminen <nospam@thanks.invalid>
Date	2016-12-12 13:16 +0000
Message-ID	<o2m7v7$2s1e$1@adenine.netfront.net>
In reply to	#47018

Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
> AFAIK quicksort will not work with linked lists; try merge sort instead.

"AFAIK"? Would it be too much to ask to not post guesses as answers?

Quicksort works with linked lists just fine. It's one of the standard
examples in language that use linked lists as its primary container
type (such as lisp and haskell).

It's only when you start using some fancier optimizations that it
becomes more difficult. For example choosing the pivot point as
the median of the first, last and middle elements. (This is still
possible with linked lists after the first partition, but requires
extra bookkeeping.)

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

#47324

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-12 18:32 +0000
Message-ID	<a8ydnTLbnp2tcNPFnZ2dnUU7-bGdnZ2d@giganews.com>
In reply to	#47312

On 12/12/2016 13:16, Juha Nieminen wrote:
> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
>> AFAIK quicksort will not work with linked lists; try merge sort instead.
>
> "AFAIK"? Would it be too much to ask to not post guesses as answers?
>
> Quicksort works with linked lists just fine. It's one of the standard
> examples in language that use linked lists as its primary container
> type (such as lisp and haskell).
>
> It's only when you start using some fancier optimizations that it
> becomes more difficult. For example choosing the pivot point as
> the median of the first, last and middle elements. (This is still
> possible with linked lists after the first partition, but requires
> extra bookkeeping.)

If by "works" you mean "works slowly, O(n)".

/Flibble

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

#47325

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-12 18:34 +0000
Message-ID	<a8ydnS3bnp1VcNPFnZ2dnUU7-bGdnZ2d@giganews.com>
In reply to	#47324

On 12/12/2016 18:32, Mr Flibble wrote:
> On 12/12/2016 13:16, Juha Nieminen wrote:
>> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
>>> AFAIK quicksort will not work with linked lists; try merge sort instead.
>>
>> "AFAIK"? Would it be too much to ask to not post guesses as answers?
>>
>> Quicksort works with linked lists just fine. It's one of the standard
>> examples in language that use linked lists as its primary container
>> type (such as lisp and haskell).
>>
>> It's only when you start using some fancier optimizations that it
>> becomes more difficult. For example choosing the pivot point as
>> the median of the first, last and middle elements. (This is still
>> possible with linked lists after the first partition, but requires
>> extra bookkeeping.)
>
> If by "works" you mean "works slowly, O(n)".

By "O(n)" I actually meant "worse than O(n)*O(lg N)".

/Flibble

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

#47326

From	asetofsymbols@gmail.com
Date	2016-12-12 10:44 -0800
Message-ID	<3521c250-e7a8-4d7a-b7f8-cd3ba5e89054@googlegroups.com>
In reply to	#47324

O(n) is better than O(n*log(n)) in the few I know...

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

#47328

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-12 21:30 +0000
Message-ID	<Gs2dnalHSvOVitLFnZ2dnUU7-QudnZ2d@giganews.com>
In reply to	#47326

On 12/12/2016 18:44, asetofsymbols@gmail.com wrote:
> O(n) is better than O(n*log(n)) in the few I know...

FFS. You didn't bother to read my correction reply then?

/Flibble

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

#47331

From	Juha Nieminen <nospam@thanks.invalid>
Date	2016-12-13 07:26 +0000
Message-ID	<o2o7q6$2prn$1@adenine.netfront.net>
In reply to	#47324

Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
>> Quicksort works with linked lists just fine. It's one of the standard
>> examples in language that use linked lists as its primary container
>> type (such as lisp and haskell).
>>
>> It's only when you start using some fancier optimizations that it
>> becomes more difficult. For example choosing the pivot point as
>> the median of the first, last and middle elements. (This is still
>> possible with linked lists after the first partition, but requires
>> extra bookkeeping.)
> 
> If by "works" you mean "works slowly, O(n)".

Its asymptotic behavior is exactly the same for linked lists as it is
for random access arrays. There's nothing in the basic quicksort algorithm
that requires random access.

Maybe you missed the part where I said that quicksort is one of those
classical quintessential examples in languages where linked lists are
the basic data container? Maybe your problem is that you just don't
know how to implement quicksort for linked lists. It's quite easy,
really.

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

#47338

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-13 17:51 +0000
Message-ID	<yuudnRfdreaAqM3FnZ2dnUU7-LudnZ2d@giganews.com>
In reply to	#47331

On 13/12/2016 07:26, Juha Nieminen wrote:
> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
>>> Quicksort works with linked lists just fine. It's one of the standard
>>> examples in language that use linked lists as its primary container
>>> type (such as lisp and haskell).
>>>
>>> It's only when you start using some fancier optimizations that it
>>> becomes more difficult. For example choosing the pivot point as
>>> the median of the first, last and middle elements. (This is still
>>> possible with linked lists after the first partition, but requires
>>> extra bookkeeping.)
>>
>> If by "works" you mean "works slowly, O(n)".
>
> Its asymptotic behavior is exactly the same for linked lists as it is
> for random access arrays. There's nothing in the basic quicksort algorithm
> that requires random access.
>
> Maybe you missed the part where I said that quicksort is one of those
> classical quintessential examples in languages where linked lists are
> the basic data container? Maybe your problem is that you just don't
> know how to implement quicksort for linked lists. It's quite easy,
> really.

Wrong. Quicksort will be worse than O(n . lg n) for linked lists.

/Flibble

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

#47345

From	Tim Rentsch <txr@alumni.caltech.edu>
Date	2016-12-13 14:52 -0800
Message-ID	<kfnk2b3igqf.fsf@x-alumni2.alumni.caltech.edu>
In reply to	#47338

Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:

> On 13/12/2016 07:26, Juha Nieminen wrote:
>> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
>>>> Quicksort works with linked lists just fine.  It's one of the standard
>>>> examples in language that use linked lists as its primary container
>>>> type (such as lisp and haskell).
>>>>
>>>> It's only when you start using some fancier optimizations that it
>>>> becomes more difficult.  For example choosing the pivot point as
>>>> the median of the first, last and middle elements.  (This is still
>>>> possible with linked lists after the first partition, but requires
>>>> extra bookkeeping.)
>>>
>>> If by "works" you mean "works slowly, O(n)".
>>
>> Its asymptotic behavior is exactly the same for linked lists as it is
>> for random access arrays.  There's nothing in the basic quicksort algorithm
>> that requires random access.
>>
>> Maybe you missed the part where I said that quicksort is one of those
>> classical quintessential examples in languages where linked lists are
>> the basic data container?  Maybe your problem is that you just don't
>> know how to implement quicksort for linked lists.  It's quite easy,
>> really.
>
> Wrong.  Quicksort will be worse than O(n . lg n) for linked lists.

Maybe you mean something different by quicksort in this context.
A properly implemented quicksort - meaning, select a pivot
element, partition the list into sublists that are less than,
equal to, and greater than the pivot element, recurse on the
two sublists that are not equal, and join the resulting sorted
lists into a single list - will have the same asymptotic order
(ie, within a constant factor) as does quicksort on an array.

This isn't the best way to sort linked lists, but it does have
the same order as array-based quicksort.

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

#47350

From	Juha Nieminen <nospam@thanks.invalid>
Date	2016-12-14 10:26 +0000
Message-ID	<o2r6oc$2dmm$1@adenine.netfront.net>
In reply to	#47338

Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> wrote:
> Wrong. Quicksort will be worse than O(n . lg n) for linked lists.

The number of comparisons and swaps (or, in the case of linked lists,
updating the pointers) will be exactly the same regardless of whether
it's a random access array, or a linked list. It will work even for
a singly-linked list; you don't need to traverse the list backwards
to partition a linked list. You simply need to traverse it forwards
and distribute the nodes among two sub-lists, which you then
concatenate. The asymptotic complexity is exactly the same.

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

#47351

From	"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>
Date	2016-12-14 13:05 +0100
Message-ID	<o2rcld$nhd$1@dont-email.me>
In reply to	#47338

On 13.12.2016 18:51, Mr Flibble wrote:
>
> Quicksort will be worse than O(n . lg n) for linked lists.

/That/ depends very much on the implementation, or possibly what one's 
idea of the defining characteristic of Quicksort, is.

The basic idea as I see it, is a partitioning of an array into values 
that are less than a pivot and values that are greater than that pivot 
(plus a partition with the pivot values). There's no need to combine the 
partitions afterwards because they're already successive parts of the 
array. For a natural linked list implementation they need to be 
explicitly combined in an extra set of steps that in total are O(n).

The below array implementation took me several attempts to get right. I 
am still not 100% sure it's correct because the earlier attempts all 
/seemed/ to be correct, with no way that they could malf, but they did. 
However, instead of testing this to death I just post it:


[code]
// Array version of QuckSort.
#include <algorithm>        // std::swap
#include <assert.h>         // assert
#include <iostream>
#include <stdlib.h>         // size_t, ptrdiff_t
using namespace std;

using Size = ptrdiff_t;
using Index = Size;

void qsort(
     double* const       items,
     Index const         i_first,
     Index const         i_last
     )
{
     using std::swap;
     if( i_first >= i_last ) { return; }

     double const pivot = (items[i_first] + items[i_last])/2;
     Index i_end_of_p1     = i_first;
     Index i_before_pivot;
     Index i_start_of_p2   = i_last;
     clog << "Pivot " << pivot << endl;
     for( ;; )
     {
         // Nice trace output.
         clog << i_end_of_p1 << " " << i_start_of_p2 << "      ";
         for( Index i = 0; i < i_end_of_p1; ++i ) { clog << "  "; }
         for( Index i = i_end_of_p1; i <= i_start_of_p2; ++i ) { clog << 
items[i] << " "; }
         clog << endl;

         // Pivot needs to be in one of the partitions, lest two pivots 
block things.
         while( items[i_end_of_p1] < pivot ) { ++i_end_of_p1; }
         i_before_pivot = i_end_of_p1 - 1;
         while( items[i_end_of_p1] == pivot and i_end_of_p1 <= i_last ) 
{ ++i_end_of_p1; }
         while( items[i_start_of_p2] > pivot ) { --i_start_of_p2; }

         // The stopping values are in disjoint sets, or i_end_of_p1 is 
off the end, so
         // the indices can't be equal.
         if( i_end_of_p1 > i_start_of_p2 )
         {
             break;
         }
         swap( items[i_end_of_p1], items[i_start_of_p2] );
     }
     swap( i_end_of_p1, i_start_of_p2 );
     assert( i_end_of_p1 < i_start_of_p2 );
     qsort( items, i_first, i_before_pivot );
     qsort( items, i_start_of_p2, i_last );
}

template< class Item, size_t n >
auto n_items_of( Item (&)[n] ) -> Size { return n; }

auto main()
     -> int
{
     double a[]{ 3, 1, 4, 1, 5, 9, 2, 6, 5, 4 };
     qsort( a, 0, n_items_of( a ) - 1 );
     for( double const x : a )
     {
         cout << x << ' ';
     }
     cout << endl;
}
[/code]


The linked list version, on the other hand, has no subtle conditions or 
state, and (ignoring a little typo thing) worked on the first try:


[code]
// Linked list version of QuckSort.
#include <iostream>
using namespace std;

namespace list {
     struct Node
     {
         double      value;
         Node*       next;
     };

     auto const nil = static_cast<Node*>( nullptr );

     auto last_node_from( Node& first_node )
         -> Node*
     {
         Node* p = &first_node;
         while( p->next != nil ) { p = p->next; }
         return p;
     }

     void append_to( Node*& first, Node* other_list )
     {
         (first == nil? first : last_node_from( *first )->next) = 
other_list;
     }

     auto unlinked( Node*& p_first )
         -> Node*
     {
         Node* result = p_first;
         p_first = result->next;
         result->next = nil;
         return result;
     }
}  // namespace list

void qsort( list::Node*& items )
{
     if( items == list::nil or items->next == list::nil ) { return; }

     list::Node* const first_item    = items;
     list::Node* const last_item     = list::last_node_from( *first_item 
);  // O(n)
     double const pivot = ( first_item->value + last_item->value)/2;
     clog << "Pivot " << pivot << endl;

     list::Node*     p1              = list::nil;
     list::Node*     p_middle        = list::nil;            // Pivot 
values in order.
     list::Node*     p2              = list::nil;

     // O(n)
     {
         list::Node**    end_of_p1       = &p1;
         list::Node**    end_of_p_middle = &p_middle;
         list::Node**    end_of_p2       = &p2;

         list::Node* p = first_item;
         while( p != list::nil )
         {
             static auto const link_in_after = [](
                 list::Node**& end_of_partition, list::Node* node
                 ) -> void
             {
                 *end_of_partition = node;
                 end_of_partition = &node->next;
             };

             double const v = p->value;  // Logically necessary, not 
just convenience.
             link_in_after(
                 (v < pivot? end_of_p1 : v== pivot? end_of_p_middle : 
end_of_p2),
                 list::unlinked( p )
                 );
         }

         qsort( p1 );
         qsort( p2 );
     }

     list::append_to( p_middle, p2 );
     list::append_to( p1, p_middle );
     items = p1;
}

#ifdef _MSC_VER
#   pragma warning( disable: 4701 )     // Potentially indeterminate value.
#   pragma warning( disable: 4703 )     // Potentially indeterminate 
pointer value.
#endif

auto main()
     -> int
{
     list::Node*     items = list::nil;
     list::Node*     p_last_node;
     for( int const v : { 3, 1, 4, 1, 5, 9, 2, 6, 5, 4 } )
     {
         auto const p_new_node = new list::Node{ double( v ), list::nil };
         if( items == list::nil )
         {
             items = p_new_node;
             p_last_node = p_new_node;
         }
         else
         {
             p_last_node->next = p_new_node;
             p_last_node = p_new_node;
         }
     }

     qsort( items );
     for( list::Node* p = items; p != list::nil; p = p->next )
     {
         cout << p->value << ' ';
     }
     cout << endl;
}
[/code]


The pointer manipulation adds some overhead to the partitioning, I think 
well in excess of the array partitioning. Then on top of that there's 
the recombination steps at the end. So I'd say it's in practice 
impossible to get array-like fastish behavior for the linked list QS.


Cheers & hth.,

- Alf

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

#47353

From	Juha Nieminen <nospam@thanks.invalid>
Date	2016-12-14 14:06 +0000
Message-ID	<o2rjlu$1d85$1@adenine.netfront.net>
In reply to	#47351

Alf P. Steinbach <alf.p.steinbach+usenet@gmail.com> wrote:
> The linked list version, on the other hand, has no subtle conditions or 
> state, and (ignoring a little typo thing) worked on the first try:

I didn't look at the implementation very closely, but I think you are
doing it in a needlessly complicated manner.

To partition a list, simply distribute its nodes into two lists.
This is easiest done by popping each node from the beginning of
the list and pushing it to the beginning of one of those two
other lists (depending on the comparison with the pivot).
(Since the ordering of the nodes within the new partitions doesn't
matter for quicksort, it's just easiest to push them to the front.)

Call the partitioning for each sublist recursively, and then
splice one list to the end of the other. (You don't need to
necessarily traverse the list to do this, as you can keep a
pointer to the original first node inserted into the list.
You can use it to splice the other list after it.)

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

#47355

From	"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>
Date	2016-12-14 16:59 +0100
Message-ID	<o2rqbp$7jn$1@dont-email.me>
In reply to	#47353

On 14.12.2016 15:06, Juha Nieminen wrote:
> Alf P. Steinbach <alf.p.steinbach+usenet@gmail.com> wrote:
>> The linked list version, on the other hand, has no subtle conditions or
>> state, and (ignoring a little typo thing) worked on the first try:
>
> I didn't look at the implementation very closely, but I think you are
> doing it in a needlessly complicated manner.
>
> To partition a list, simply distribute its nodes into two lists.
> This is easiest done by popping each node from the beginning of
> the list and pushing it to the beginning of one of those two
> other lists (depending on the comparison with the pivot).
> (Since the ordering of the nodes within the new partitions doesn't
> matter for quicksort, it's just easiest to push them to the front.)
>
> Call the partitioning for each sublist recursively, and then
> splice one list to the end of the other. (You don't need to
> necessarily traverse the list to do this, as you can keep a
> pointer to the original first node inserted into the list.
> You can use it to splice the other list after it.)

I use three lists, otherwise the logic is as you describe.

Maybe you can show how to do it with two lists.


Cheers!,

- Alf

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

#47360

From	Gareth Owen <gwowen@gmail.com>
Date	2016-12-14 20:19 +0000
Message-ID	<87d1gue00s.fsf@gmail.com>
In reply to	#47351

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes:

> On 13.12.2016 18:51, Mr Flibble wrote:
>>
>> Quicksort will be worse than O(n . lg n) for linked lists.
>
> /That/ depends very much on the implementation, or possibly what one's
> idea of the defining characteristic of Quicksort, is.

Just be aware that Flibble has shown on multiple occasions that
mathematics is not one of his strengths.

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

#47366

From	Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date	2016-12-14 21:23 +0000
Message-ID	<mrSdnUOdRsH4JczFnZ2dnUU7-TGdnZ2d@giganews.com>
In reply to	#47360

On 14/12/2016 20:19, Gareth Owen wrote:
> "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes:
>
>> On 13.12.2016 18:51, Mr Flibble wrote:
>>>
>>> Quicksort will be worse than O(n . lg n) for linked lists.
>>
>> /That/ depends very much on the implementation, or possibly what one's
>> idea of the defining characteristic of Quicksort, is.
>
> Just be aware that Flibble has shown on multiple occasions that
> mathematics is not one of his strengths.

By asserting that there is no such thing as negative zero and that 
division by zero is undefined?  My assertions are correct mate.

/Flibble

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

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

csiph-web

Qucksort for Linked List

Contents

#47017 — Qucksort for Linked List

#47018

#47028

#47030

#47032

#47033

#47312

#47324

#47325

#47326

#47328

#47331

#47338

#47345

#47350

#47351

#47353

#47355

#47360

#47366