Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #47017 > unrolled thread
| 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 6 of 7 — ← Prev page 1 2 3 4 5 [6] 7 Next page →
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2017-01-06 10:35 +1300 |
| Message-ID | <ed7shiFatdfU2@mid.individual.net> |
| In reply to | #47855 |
On 01/ 6/17 10:21 AM, Mr Flibble wrote: > 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. Change your diet, or eat better quality sausages! Sausages (not those oxymoronic vegetarian or budget supermarket crap) should be the key ingredient of a healthy diet. -- Ian
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2016-12-22 21:43 -0800 |
| Message-ID | <kfnlgv7dwtk.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #47496 |
Gareth Owen <gwowen@gmail.com> writes: > [...] std::list::sort is *not* required to be stable. [...] AFAICT C++03, C++11, and C++14 all require std::list::sort to be a stable sort.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2016-12-22 22:09 -0800 |
| Message-ID | <kfnh95vdvmc.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #47432 |
Juha Nieminen <nospam@thanks.invalid> writes:
> Tim Rentsch <txr@alumni.caltech.edu> wrote:
>> There is no reason that the choice of a pivot value has to be any
>> worse in a linked list quicksort than an array quicksort. In
>> particular, the entire linked list can be scanned, any constant
>> number of times, looking for a pivot value, without changing the
>> order of the algorithm.
>
> In addition, it's possible to optimize the constant factor of the
> computational complexity, for example if you would want to use the
> median-of-the-first-last-and-middle pivot method: The very first
> time you perform the partitioning just choose the first element as
> the pivot, but as you distribute the nodes into the two new lists,
> keep note of the last and middle elements of said lists. Then when
> partitioning them, you can choose their pivots from those three
> nodes. No need to scan the lists.
I think what you say is true, although it's a little tricky to
keep track of the middle element (in each of the two partitions)
because you don't know ahead of time how many elements will be in
each partition.
OTOH, there are lots of different things that can affect the
constants, and usually there are tradeoffs between different
choices. For example, dealing with linked lists makes it easy to
divide the initial list into, say, 16 different sublists based on
15 different pivot values, and recurse on each sublist before
gluing them together. For this scheme we might use random
sampling to get the 15 pivot values (for each sublist, ready for
the next pass), which greatly reduces the chance of O(n**2)
behavior, and may give an improvement in the constant factor as
well. (A value may be assigned to a sublist using just 4 or 5
compares, depending on whether a compare operation gives 1 bit
of information or a {less, equal, greater} result.) And of
course there are local optimizations to consider, which often
are good for a factor of, oh, let's say 1.5 or 2; but then
again these may be swamped by the cost of doing the compares.
I guess my general rule is that anything affecting just the
constants is a possible optimization that I leave for such time
as performance has been shown to be an issue. Before then I
pretend not to care what the constants are. :)
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2016-12-23 17:00 +0000 |
| Message-ID | <rJGdncoOaMmTxcDFnZ2dnUU7-emdnZ2d@giganews.com> |
| In reply to | #47539 |
On 23/12/2016 06:09, Tim Rentsch wrote: [snip] > > I think what you say is true, although it's a little tricky to > keep track of the middle element (in each of the two partitions) > because you don't know ahead of time how many elements will be in > each partition. ^^ this. My initial guess that worst case performance is more likely is starting to get legs I think. :D Sausages. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2016-12-23 12:03 -0800 |
| Message-ID | <kfnbmw2za3d.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #47550 |
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > On 23/12/2016 06:09, Tim Rentsch wrote: > > [snip] > >> I think what you say is true, although it's a little tricky to >> keep track of the middle element (in each of the two partitions) >> because you don't know ahead of time how many elements will be in >> each partition. > > ^^ this. My initial guess that worst case performance is more likely > is starting to get legs I think. That doesn't matter because the change being discussed is still within a constant factor and so doesn't affect the order. In fact any change that differs only by a constant factor doesn't affect the order - not the average behavior, not the worst case behavior, not how often worst case behavior occurs relative to average behavior. All of the changes we have been talking about affect only constant factors, and hence have no impact on asymptotic complexity, worst-case or otherwise.
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2016-12-23 20:25 +0000 |
| Message-ID | <qqGdnYbwue6uFcDFnZ2dnUU7-budnZ2d@giganews.com> |
| In reply to | #47557 |
On 23/12/2016 20:03, Tim Rentsch wrote: > Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > >> On 23/12/2016 06:09, Tim Rentsch wrote: >> >> [snip] >> >>> I think what you say is true, although it's a little tricky to >>> keep track of the middle element (in each of the two partitions) >>> because you don't know ahead of time how many elements will be in >>> each partition. >> >> ^^ this. My initial guess that worst case performance is more likely >> is starting to get legs I think. > > That doesn't matter because the change being discussed is still > within a constant factor and so doesn't affect the order. In > fact any change that differs only by a constant factor doesn't > affect the order - not the average behavior, not the worst case > behavior, not how often worst case behavior occurs relative to > average behavior. All of the changes we have been talking about > affect only constant factors, and hence have no impact on > asymptotic complexity, worst-case or otherwise. So how to get the middle element without traversing linked list O(n) times for each partition? You are basically contradicting yourself. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2016-12-23 20:56 +0000 |
| Message-ID | <87a8bm4b5t.fsf@gmail.com> |
| In reply to | #47560 |
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes:
> So how to get the middle element without traversing linked list O(n)
> times for each partition?
If each interation used to take k*n steps (fixed k) now takes (k+1)*n steps,
**** YOU HAVEN'T CHANGED THE ORDER ****
If each interation used to take k*n steps and now takes 1000*k*n steps,
you've slowed the algorithm down egregiously but....
**** YOU STILL HAVEN'T CHANGED THE ORDER ****
Maths not a strong suit, is it?
> You are basically contradicting yourself.
You are wrong. Go read a book.
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2016-12-23 22:02 +0000 |
| Message-ID | <2MOdneFss69BA8DFnZ2dnUU7-aXNnZ2d@giganews.com> |
| In reply to | #47562 |
On 23/12/2016 20:56, Gareth Owen wrote: > Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > >> So how to get the middle element without traversing linked list O(n) >> times for each partition? > > If each interation used to take k*n steps (fixed k) now takes (k+1)*n steps, > **** YOU HAVEN'T CHANGED THE ORDER **** Except overall you are actually taking lg n * n extra steps so it is not dependent on a constant but on n. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> |
|---|---|
| Date | 2016-12-23 22:14 +0000 |
| Message-ID | <D8udndsqdv1CPMDFnZ2dnUU7-IOdnZ2d@giganews.com> |
| In reply to | #47567 |
On 23/12/2016 22:02, Mr Flibble wrote: > On 23/12/2016 20:56, Gareth Owen wrote: >> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: >> >>> So how to get the middle element without traversing linked list O(n) >>> times for each partition? >> >> If each interation used to take k*n steps (fixed k) now takes (k+1)*n >> steps, >> **** YOU HAVEN'T CHANGED THE ORDER **** > > Except overall you are actually taking lg n * n extra steps so it is not > dependent on a constant but on n. But as 2 * O(n * lg n) = O(n * lg n) then yeah, I seemed to have guessed wrong but like I said elsewhere I have not actually looked at the quicksort algorithm for linked lists as I would never use quicksort on linked lists because it is slower than mergesort even if it is the same algorithmic complexity. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2016-12-29 13:56 -0800 |
| Message-ID | <kfnful6v1p5.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #47560 |
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > On 23/12/2016 20:03, Tim Rentsch wrote: >> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: >> >>> On 23/12/2016 06:09, Tim Rentsch wrote: >>> >>> [snip] >>> >>>> I think what you say is true, although it's a little tricky to >>>> keep track of the middle element (in each of the two partitions) >>>> because you don't know ahead of time how many elements will be in >>>> each partition. >>> >>> ^^ this. My initial guess that worst case performance is more likely >>> is starting to get legs I think. >> >> That doesn't matter because the change being discussed is still >> within a constant factor and so doesn't affect the order. In >> fact any change that differs only by a constant factor doesn't >> affect the order - not the average behavior, not the worst case >> behavior, not how often worst case behavior occurs relative to >> average behavior. All of the changes we have been talking about >> affect only constant factors, and hence have no impact on >> asymptotic complexity, worst-case or otherwise. > > So how to get the middle element without traversing linked list O(n) > times for each partition? You are basically contradicting yourself. I gather you now agree that this can be done without changing the order, so I guess there is no need to explain further. The problem of finding the middle element of a list while traversing the list once does make an amusing little exercise.
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@i42.co.uk> |
|---|---|
| Date | 2016-12-29 23:26 +0000 |
| Message-ID | <6cWdnZZX3ooNBvjFnZ2dnUU78RudnZ2d@giganews.com> |
| In reply to | #47712 |
On 29/12/2016 21:56, Tim Rentsch wrote: > Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: > >> On 23/12/2016 20:03, Tim Rentsch wrote: >>> Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> writes: >>> >>>> On 23/12/2016 06:09, Tim Rentsch wrote: >>>> >>>> [snip] >>>> >>>>> I think what you say is true, although it's a little tricky to >>>>> keep track of the middle element (in each of the two partitions) >>>>> because you don't know ahead of time how many elements will be in >>>>> each partition. >>>> >>>> ^^ this. My initial guess that worst case performance is more likely >>>> is starting to get legs I think. >>> >>> That doesn't matter because the change being discussed is still >>> within a constant factor and so doesn't affect the order. In >>> fact any change that differs only by a constant factor doesn't >>> affect the order - not the average behavior, not the worst case >>> behavior, not how often worst case behavior occurs relative to >>> average behavior. All of the changes we have been talking about >>> affect only constant factors, and hence have no impact on >>> asymptotic complexity, worst-case or otherwise. >> >> So how to get the middle element without traversing linked list O(n) >> times for each partition? You are basically contradicting yourself. > > I gather you now agree that this can be done without changing > the order, so I guess there is no need to explain further. > > The problem of finding the middle element of a list while > traversing the list once does make an amusing little exercise. Yes I have thought about that problem and I am guessing it involves powers of 2 if you know what I mean. :) /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2016-12-29 20:25 -0800 |
| Message-ID | <kfny3yyt54v.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #47725 |
Mr Flibble <flibble@i42.co.uk> writes: > On 29/12/2016 21:56, Tim Rentsch wrote: >>[...] >> >> The problem of finding the middle element of a list while >> traversing the list once does make an amusing little exercise. > > Yes I have thought about that problem and I am guessing it involves > powers of 2 if you know what I mean. :) I don't know about other folks but my solution involves exactly two powers of 2 -- 2**0 and 2**1.
[toc] | [prev] | [next] | [standalone]
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Date | 2017-01-04 07:07 +0000 |
| Message-ID | <o4i6vc$2ocj$2@adenine.netfront.net> |
| In reply to | #47539 |
Tim Rentsch <txr@alumni.caltech.edu> wrote: > I think what you say is true, although it's a little tricky to > keep track of the middle element (in each of the two partitions) > because you don't know ahead of time how many elements will be in > each partition. Every second time you add to the list, advance the "middle" iterator. Sure, that adds a bit to the constant factor of the complexity, but on the other hand it may be worth it, if the median-of-three pivot choice compensated for it on average.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2017-01-26 22:40 -0800 |
| Message-ID | <kfnh94lhup0.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #47816 |
Juha Nieminen <nospam@thanks.invalid> writes: > Tim Rentsch <txr@alumni.caltech.edu> wrote: >> I think what you say is true, although it's a little tricky to >> keep track of the middle element (in each of the two partitions) >> because you don't know ahead of time how many elements will be in >> each partition. > > Every second time you add to the list, advance the "middle" iterator. Yes, I didn't say impossible, just a little tricky. And the details change if one is dealing with an ordinary linked list (as I was imagining) rather than an iterable one. > Sure, that adds a bit to the constant factor of the complexity, but > on the other hand it may be worth it, if the median-of-three pivot > choice compensated for it on average. All things considered, it probably makes more sense to select three elements at random during the scan, and use the median of those three random elements as the pivot.
[toc] | [prev] | [next] | [standalone]
| From | xerofoify <xerofoify@gmail.com> |
|---|---|
| Date | 2016-12-02 13:47 -0800 |
| Message-ID | <1ba2e953-7e72-4bb0-9e3c-d9babf290a81@googlegroups.com> |
| In reply to | #47017 |
On Friday, December 2, 2016 at 1:14:46 PM UTC-5, 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 }
I am wondering how to write quicksort by swapping the Nodes themselves not the data. So was wondering how to do that and make the above quicksort work.
[toc] | [prev] | [next] | [standalone]
| From | ruben safir <ruben@mrbrklyn.com> |
|---|---|
| Date | 2016-12-02 17:38 -0500 |
| Message-ID | <o1st51$4ld$1@reader1.panix.com> |
| In reply to | #47035 |
On 12/02/2016 04:47 PM, xerofoify wrote: > I am wondering how to write quicksort by swapping the Nodes themselves not the data. So was wondering how to do that and make the above quicksort work. that is standard in every text book. Go look
[toc] | [prev] | [next] | [standalone]
| From | xerofoify <xerofoify@gmail.com> |
|---|---|
| Date | 2016-12-02 14:53 -0800 |
| Message-ID | <afeb4d7b-66a1-41a0-86dc-0027820fca41@googlegroups.com> |
| In reply to | #47038 |
No there isn't. They should how to create a linked list not quicksort by swapping nodes. Here's the complete question how do I get this to work for when I have iterators not to invalidate the data by swapping the nodes in order to implement quicksort by swapping nodes data. There are no examples online or in any textbook I can find. I am looking for actual code not pseduo code.
[toc] | [prev] | [next] | [standalone]
| From | Jerry Stuckle <jstucklex@attglobal.net> |
|---|---|
| Date | 2016-12-02 19:50 -0500 |
| Message-ID | <o1t4q8$86k$1@jstuckle.eternal-september.org> |
| In reply to | #47044 |
On 12/2/2016 5:53 PM, xerofoify wrote: > No there isn't. They should how to create a linked list not quicksort by swapping nodes. Here's the complete question how do I get this to work for when I have iterators not to invalidate the data by swapping the nodes in order to implement quicksort by swapping nodes data. There are no examples online or in any textbook I can find. I am looking for actual code not pseduo code. > If you swap a node, then by definition any iterator pointing at that node will become invalid, at least as far as being properly positioned. For instance, if your list's nodes contained values 5,10,7,1 and you have a forward iterator pointing at the first node and a backwards iterator pointing at the last node, and swap the nodes. Now your forward iterator is pointing at the last node, and your backward iterator is pointing at the first node. Advancing either one will fall off one end of the list or the other - not continue to step through the list. -- ================== Remove the "x" from my email address Jerry Stuckle jstucklex@attglobal.net ==================
[toc] | [prev] | [next] | [standalone]
| From | ruben safir <ruben@mrbrklyn.com> |
|---|---|
| Date | 2016-12-02 21:17 -0500 |
| Message-ID | <o1t9vs$df9$1@reader1.panix.com> |
| In reply to | #47044 |
On 12/02/2016 05:53 PM, xerofoify wrote: > No there isn't. I guess your in an alternate universe. This is a standard HS home work assignment
[toc] | [prev] | [next] | [standalone]
| From | xerofoify <xerofoify@gmail.com> |
|---|---|
| Date | 2016-12-02 20:44 -0800 |
| Message-ID | <7a1c65f5-c6c7-42f1-9c53-d33a755a6511@googlegroups.com> |
| In reply to | #47059 |
On Friday, December 2, 2016 at 9:17:40 PM UTC-5, ruben safir wrote:
> On 12/02/2016 05:53 PM, xerofoify wrote:
> > No there isn't.
>
> I guess your in an alternate universe. This is a standard HS home work
> assignment
for (Node *j = l; j != h; j = j->next_) {
163 if (j->data_ <= x) {
I am confused about why this two lines are segfaulting for me through.
[toc] | [prev] | [next] | [standalone]
Page 6 of 7 — ← Prev page 1 2 3 4 5 [6] 7 Next page →
Back to top | Article view | comp.lang.c++
csiph-web