Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #47049
| From | "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: Qucksort for Linked List |
| Date | 2016-12-03 01:16 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <o1t2vs$3er$1@dont-email.me> (permalink) |
| References | <dfa00771-7568-443b-ab45-174f0749a176@googlegroups.com> |
On 02.12.2016 19: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 }
You can either swap the data in the nodes, or you can swap nodes by
unlinking them and reinserting.
To unlink a node that you have a pointer to, without copying data, and
without searching from the start of the list, you need a doubly linked list.
That said, quicksort is not really suited for linked lists. It's quick
(on average) because one can determine the two halves of an array in
constant time. With a linked list this is a linear time operation.
With a linked list you can instead use a merge sort.
Essentially this is the reason why you cannot do
std::list<T> items;
std::sort( items.begin(), items.end() ); //! Nah.
but must do e.g.
items.sort();
Well I've never understood why `std::sort` isn't just overloaded for
`std::list`, forwarding to the `sort` member function, that is, I've
never understood why `std::sort` /requires/ random access iterators, why
it can't just do the practical thing for the container at hand.
But, there is an issue.
Cheers & hth.,
- Alf
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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