Qucksort for Linked List

[xerofoify]

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 }

[Mr Flibble]

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

/Flibble

[Melzzzzz]

On Fri, 2 Dec 2016 19:17:08 +0000
Mr Flibble <flibbleREM...@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

[Mr Flibble]

O(n) is never "quite efficient".

/Flibble

[Melzzzzz]

On Fri, 2 Dec 2016 21:26:46 +0000

Mr Flibble <flibbleREM...@i42.co.uk> wrote:

> On 02/12/2016 21:09, Melzzzzz wrote:
> > On Fri, 2 Dec 2016 19:17:08 +0000
> > Mr Flibble <flibbleREM...@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.

[Mr Flibble]

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

/Flibble

[xerofoify]

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.

[ruben safir]

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

[xerofoify]

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.

[Alf P. Steinbach]

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

[Jerry Stuckle]

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
jstu...@attglobal.net
==================

[ruben safir]

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

[xerofoify]

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.

[xerofoify]

This is my complete code.
#pragma once
#include <utility>
#include<iostream>
template<typename T>
class DList {
private:

/*This is the Node object used for each list element
data members
@data - represents the data held inside the Node and of type T or the List's data type
@prev - previous element in the list
@next - next element in the list
*/
struct Node {
T data_;
Node* next_;
Node* prev_;
/*constructor
takes the following values as parameters
@ T data - type of data and value of data to be stored for this Node's data,
safe empty state by default
@Node* next - next Node in list
sets to NULL pointer by default
@Node* prev - pre Node in list
sets to NULL pointer by default
*/
Node(const T& data = T{}, Node* next = nullptr, Node* prev = nullptr) {
data_ = data;
next_ = next;
prev_ = prev;
}
};
/* head_ is the first node in the list and tail_ is the last node */
Node* head_;
Node* tail_;
/*Number of elements in the list*/
int size_;
public:
/*Iterator that is const in nature, i.e. cannot modifty the iterator after creation*/
class const_iterator {
protected:
Node* curr;
private:
friend class DList;
/*Constructor that sets Node to Node passed*/
const_iterator(Node* pass) {
curr = pass;
}
public:
/* A Constructor that sets internal Node to nullptr*/
const_iterator() {
curr = nullptr;
}
/*This function checks that the passed iterator is equal to the current
one including pointing to the same Node in the list*/
bool operator==(const_iterator rhs) {
return curr == rhs.curr;
}
/*This function is the opposite of the one above in that it
checks if the iterator passed is not equal in both being the
same object and pointing to the same Node in the list*/
bool operator!=(const_iterator rhs) {
return curr != rhs.curr;
}
/*This makes the interal Node point to the next Node in
the list before returning the current object as a point*/
const_iterator operator++() {
curr = curr->next_;
return *this;
}
/*This does the same as above but returns the previos
Node in the list as a iterator rather then *this*/
const_iterator operator++(int) {
const_iterator next = *this;
curr = curr->next_;
return next;
}

/*This moves the internal Node to the previous
object before returning the current object's
pointer*/
const_iterator operator--() {
curr = curr->prev_;
return *this;
}
/*Same as above but return a new iterator
that points to the previous Node rather
than *this*/
const_iterator operator--(int) {
const_iterator prev = *this;
curr = curr->prev_;
return prev;
}
/*Return the data held by this Node*/
const T& operator*() const {
return curr->data_;
}
};
/*This is the same as above except not const in nature i.e. can modifiy*/
class iterator :public const_iterator {
friend class DList;
/*Constructor that takes a parameter sets the Node to the Node passed*/
iterator(Node* pass) {
this->curr = pass;
}
/*Returns Node for Quicksort*/
Node* getNode() {
return this->curr;
}
public:
/*Constructor for this class
One that takes no parameters sets interal node used by interator to nullptr
*/
iterator() {
this->curr = nullptr;
}
/*Return the data held by this Node*/
T& operator*() {
return this->curr->data_;
}
/*This makes the interal Node point to the next Node in
the list before returning the current object as a point*/
iterator operator++() {
this->curr = this->curr->next_;
return *this;
}
/*This does the same as above but returns the previos
Node in the list as a iterator rather then *this*/
iterator operator++(int) {
iterator next = *this;
this->curr = this->curr->next_;
return next;
}
/*This moves the internal Node to the previous
object before returning the current object's
Same as above but return a new iterator */
iterator operator--() {
this->curr = this->curr->prev_;
return *this;
}
/*This moves the internal Node to the previous
object before returning the current object's
Same as above but return a new iterator
that points to the previous Node rather
than *this*/
iterator operator--(int) {
iterator prev = *this;
this->curr = this->curr->prev_;
return prev;
}
};
private:
//Swap function for nodes
void swap ( Node* a, Node* b ) {
Node *t = a;
a = b;
b = t;
}
//Partion function for nodes

Node* partition(Node *l, Node *h)

{

T x = h->data_;

Node *i = l->prev_;

Node* j = new Node();
for (j; j != h; j = j->next_) {

if (j->data_ <= x) {

i = (i == nullptr)? l : i->next_;

swap(i, j);

}
}
i = (i == nullptr)? l : i->next_;

swap(i, h);
return i;

}
/*this does qsort recursively on the elements from the Node at the first iterator passed up to

and including the Node at iterator two*/

void qSortrecursive(iterator first, iterator second) {

Node* h = first.getNode();
Node* l = second.getNode();

if (h != NULL && l != h && l != h->next_)

{

struct Node *p = partition(l, h);

qSortrecursive(l, p->prev_);
qSortrecursive(p->next_, h);
}
}
/*This does qsort as above but Iterative and not recursively*/
void qSortIterative(iterator first, iterator second) {
Node* h = first.getNode();
Node* l = second.getNode();
if (h != NULL && l != h && l != h->next_) {

struct Node *p = partition(l, h);

qSortIterative(l, p->prev_);
qSortIterative(p->next_, h);

}
}
public:
/*Constructor sets list to empty state
i.e. head_ and tail_ are nullptr and
size is 0, no Nodes*/
DList() {
head_ = new Node();
tail_ = new Node();
head_->next_ = tail_;
tail_->prev_ = head_;
size_ = 0;
}
/*Creates and returns a iterator to the beginning of the list*/
iterator begin() {
iterator begin(head_->next_);
return begin;
}
/*Returns a iterator to one after the end of the list after
creating a iterator that does so*/
iterator end() {
iterator end(tail_);
return end;
}
/*This is the same as iterator begin but creates a const_iterator
rather then a iterator*/
const_iterator begin() const {
const_iterator begin(head_->next_);
return begin;
}
/*This creates a const iterator to the Node after the end of the list*/
const_iterator end() const {
const_iterator end(tail_);
return end;
}
/* Pushs a new Node into the list's first element with a value
passed to it as the Node's data member*/
void push_front(const T& data) {
Node* first = head_->next_; //it is ok if this
//is back sentinel
Node* temp = new Node(data, first, head_);
head_->next_ = temp;
first->prev_ = temp;
size_++;
}
/* Pushs a new Node into the list's last element with a value
passed to it as the Node's data member*/
void push_back(const T& data) {
Node* last = tail_->prev_;
Node* temp = new Node(data, tail_, last);
tail_->prev_ = temp;
last->next_ = temp;
size_++;
}
/* Removes the Node at the beginning of the list*/
void pop_front() {
Node* first = head_->next_;
if (first != tail_) {
Node* secondFirst = first->next_;
head_->next_ = secondFirst;
secondFirst->prev_ = head_;
delete first;
size_--;
}
}
/*Removes the Node at the end of the list*/
void pop_back() {
Node* last = tail_->prev_;
if (last != head_) {
Node* secondLast = last->prev_;
tail_->prev_ = secondLast;
secondLast->next_ = tail_;
delete last;
size_--;
}
}
/*Insert Node at the point of the iterator passed with
the data passed becoming the inseted Node's data member*/
iterator insert(iterator loc, const T& data) {
Node* curr = loc.curr;
std::cout << loc.curr;
Node* prev = curr->prev_;
Node* New = new Node(data, curr, prev);
prev->next_ = New;
curr->prev_ = New;
size_++;
loc--;
return loc;
}
/*Removes the element at the position passsed in the iterator argument*/
void erase(iterator it) {
Node* loc = it.curr;
Node* next = loc->next_;
Node* prev = loc->prev_;
prev->next_ = next;
next->prev_ = prev;
size_--;
delete loc;
}
/*Removes all elements from the first to the last*/
void erase(iterator first, iterator last) {
iterator it = first;
while(++it != last) {
erase(it);
it = first;
}
erase(first);
}
/*Searchs for a Node with the data passed as a arugment if found
return a iterator founding to it otherwise return iterator pointing
to one element beyond end of list*/
iterator search(T& data) {
iterator it = begin();
while (it != end()) {
if (it.curr->data_ == data) {
return it;
}
it++;
}
return end();
}
/*Searchs for a Node with the data passed as a arguument if found
return a const iterator founding to it otherwise return iterator pointing
to one element beyond end of list*/
const_iterator search(const T& data) const {
const_iterator it = begin();
while (it != end()) {
if (it.data_->data_ == data) {
return it;
}
it++;
}
return end();
}
/*Quicksort wrapper for iterative verision*/
void sortIterative() {
iterator last = end()--;
qSortIterative(begin(),last);
}
void qSort(){
iterator last = end()--;
qSortrecursive(begin(),last);
}
/*Returns true if list has size set to zero or no Nodes otherwise false*/
bool empty() const {
if (size_ == 0) {
return true;
}
else {
return false;
}
}
/*Returns size of list*/
int size() const {
return size_;
}
/*Destructor, destorys and cleans up each Node's member when the
list is destoryed*/
~DList() {
if (empty()) {
return;
}
iterator itBegin = begin();
iterator itEnd = end();
erase(itBegin,itEnd);
}
/*Copy Constructor, creates a new List that is a copy of the src list
passed as a argument*/
DList(const DList& src) {
head_ = new Node();
tail_ = new Node();
head_->next_ = tail_;
tail_->prev_ = head_;
size_ = src.size_;
if (src.empty() == false) {
iterator i = end();
const_iterator c = src.end();
c--;
while(c != src.begin()){
i = insert(i,*c);
c--;
}
push_front(*c);
}
}
/*Copy Assigment operator, assigns a new List that is a copy of the src list
passed as a argument*/
DList& operator=(const DList& src) {
head_ = new Node();
tail_ = new Node();
head_->next_ = tail_;
tail_->prev_ = head_;
size_ = src.size_;
if (src.empty() == false && src.head_ != head_) {
iterator i = end();
const_iterator c = src.end();
c--;
while(c != src.begin()){
i = insert(i,*c);
c--;
}
push_front(*c);
}
return *this;
}

/*Move constructor - sets list to list passed in agrument src but steals or
moves it other rather then copies the values of the Nodes and themselves*/
DList(DList&& src) {
if (src.head_ == tail_) {
head_ = tail_ = nullptr;
size_ = 0;
}
else {
head_ = std::move(src.head_);
tail_ = std::move(src.tail_);
size_ = std::move(src.size_);
src.head_ = nullptr;
src.tail_ = nullptr;
size_ = src.size_;
}
}
/*Move Assignment operator - sets list to list passed in agrument src but steals or
moves it other rather then copies the values of the Nodes and themselves*/
DList& operator=(DList&& src) {
head_ = std::move(src.head_);
tail_ = std::move(src.tail_);
size_ = std::move(src.size_);
src.head_ = nullptr;
src.tail_ = nullptr;
size_ = src.size_;
return *this;
}
};
The reason I am asking is there appears to be no good examples for quicksort *with Node* swap not data swap which is what I want. So can someone point me to an example that does it by swapping the nodes and not the data.

[bartekltg]

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

You are not swapping nodes, nor you swaping values! ;-)


For example, we have 5 nodes:

{value, pointer next, pointer prev}

0 { 111, 1, null }
1 { 222, 2 , 0 }
2 { 333, 3 , 1 }
3 { 444, 4 , 2 }
4 { 555, null , 3 }

It looks like that:

111 - 222 - 333 - 444 - 555

And now you swap node number 1 and 3.
You swap everything inside dereferenced node.


0 { 111, 1, null }
1 { 444, 4 , 2 }
2 { 333, 3 , 1 }
3 { 222, 2 , 0 }
4 { 555, null , 3 }

And now draw the linked list...

111 - 222 - 333 - 444 - 555

Hmm, I'm quite sure this is the same list;) Just put in memory
in different way.

If you want to swap two element, a and b, in a linked list,
you have to go to neighbours of a and b and (up to four objects!)
and change its "next" and "prev" pointers.

Of course you have to update pointers in a and b too.

Be carefull, a and b can be neighbour, a or b (or both)
can be on the edge of the list, and you have to keep track of the head.

The first problem is just a one "if" statement.
The second one can be taken care of with sentinel nodes,
on the head and on the tail. Or more "ifs" ;-)


And, as others, I have to say it is veri ineffective way of sorting
list.

If you have to/want to do it with qsort, do not swap objects.
Traverse through the sub-list and move nodes with data>x on
one list, and the other ones to the second list. Then link
both new list and link it to the rest (nodes outside your sublist,
l->prev and h->next (*), there you see that sentinel nodes are usefull).

*) I assumed l is the first element, and h is the last (but still a
valid object you want to sort, not like in STL, where 'last' is not
included)


This new qsort will be much faster, but still worse than mergesort.
The number of operation in one level is similar.
It has the same number of 'levels' if the partition is each time
ideal, in the other case - qsort has more.





bartekltg

[bartekltg]

On 03.12.2016 01:16, Alf P. Steinbach wrote:
>


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

...So I can made a container with random access iterator and
do not have to rewrite whole <algorithm> header.
Or I write my own iterator.

> Well I've never understood why `std::sort` isn't just overloaded for
> `std::list`, forwarding to the `sort` member function, that is,

This is other, valid, question. Why std::sort do not check if
the container do not have method sort, and use default only
if needed.
One reason I can thing of is that iterators do not have information
about the container. Do it have information about the type of the
container, I don't remember, but I do not see why it can't.
But probably I'm wrong ;)


bartekltg

[Öö Tiib]

On Friday, 2 December 2016 23:47:15 UTC+2, xerofoify wrote:
> 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:
>

> 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 does not make sense logically.
A node of linked list contains data and pointers (IOW addresses) of
next and/or previous node.
So we can sort linked list by swapping data or we can sort it
by rearranging the pointers.
However if we swap both pointers and data of two nodes in list then
we just break integrity of the list instead of sorting it.

[Ben Bacarisse]

xerofoify <xero...@gmail.com> writes:

There seems to be more code than I'd expect and I don't have time to go
though it but here are two remarks that jump out at me...

<snip>

> //Swap function for nodes
> void swap ( Node* a, Node* b ) {
> Node *t = a;
> a = b;
> b = t;
> }

This function does nothing. It alters only local objects so has no
effect on the lists you are trying to alter.

> The reason I am asking is there appears to be no good examples for
> quicksort *with Node* swap not data swap which is what I want. So can
> someone point me to an example that does it by swapping the nodes and
> not the data.

It's not a natural list algorithm, so examples will be rare. It takes
care not to make it very inefficient on linked lists, but you can
probably find some tips about that in the literature about function
programming. Can I ask why you are using it?

--
Ben.

[ruben safir]

On 12/02/2016 11:44 PM, xerofoify wrote:
> 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.

the same reason why they always segfault is that your trying to assign
or look into a non-allocated space.

[Juha Nieminen]

Mr Flibble <flibbleREM...@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.)

[Juha Nieminen]

He is talking about changing the prev/next pointers of the nodes to
make them change place in the list (in contrast to swapping the
values of the nodes.)

[Mr Flibble]

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

/Flibble

[Mr Flibble]

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

/Flibble

[asetof...@gmail.com]

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

[Mr Flibble]

On 12/12/2016 18:44, asetof...@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

[Juha Nieminen]

Mr Flibble <flibbleREM...@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.

[Mr Flibble]

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

/Flibble

[Tim Rentsch]

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.

[Juha Nieminen]

Mr Flibble <flibbleREM...@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.

[Alf P. Steinbach]

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.

[Juha Nieminen]

Alf P. Steinbach <alf.p.stein...@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.)

[Alf P. Steinbach]

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

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


Cheers!,

- Alf

[Gareth Owen]

"Alf P. Steinbach" <alf.p.stein...@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.

[Mr Flibble]

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

/Flibble

[Gareth Owen]

They're true of the real numbers, but to suggest they're always true is
to deny the the existence of projective geometry.

Mathematics is not one of your strengths. I'll bet £1 to your favourite
charity that your best qualification in Mathematics is not better than a
'B' at 'A-level'.

[Mr Flibble]

On 14/12/2016 21:42, Gareth Owen wrote:
> Mr Flibble <flibbleREM...@i42.co.uk> writes:
>
>> On 14/12/2016 20:19, Gareth Owen wrote:
>>> "Alf P. Steinbach" <alf.p.stein...@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.
>
> They're true of the real numbers, but to suggest they're always true is
> to deny the the existence of projective geometry.

Projective bullshit more like.

>
> Mathematics is not one of your strengths. I'll bet £1 to your favourite
> charity that your best qualification in Mathematics is not better than a
> 'B' at 'A-level'.

Ad hom, a logical fallacy.

/Flibble

[Juha Nieminen]

Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> By asserting that there is no such thing as negative zero and that
> division by zero is undefined? My assertions are correct mate.

So maybe show us how the asymptotic behavior of quicksort on linked
lists is different than for random access arrays.

The question here is not what the asymptotic behavior of quicksort
is (because that's a bit complicated), but whether it's different
for linked lists.

[Mr Flibble]

Due to poor pivot choice worst case performance will manifest more often
and that is quadratic complexity.

/Flibble

[Tim Rentsch]

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.

[Mr Flibble]

Nah.

/Flibble

[Gareth Owen]

Mathematics is not a strength.

[Mr Flibble]

The bullshit branches of Mathematics are indeed not a strength mate
because I see them for what they are: nonsense; they should be an
adjunct to mathematics not a part of mathematics. There is no negative
zero; and division by zero is undefined.

/Flibble

[Mr Flibble]

And whilst on the subject of bullshit mathematics: a countable infinity
is unbounded just like an uncountable one.

/Flibble

[Gareth Owen]

Mathematics is not a strength is it. Simple maths - junior school maths
- you're ok with. Harder stuff you just dismiss.

Tell us again how linked lists change the order of quicksort.
Show your working.

[Mr Flibble]

On 18/12/2016 21:52, Gareth Owen wrote:
> Mr Flibble <flibbleREM...@i42.co.uk> writes:
>
>> On 18/12/2016 21:15, Gareth Owen wrote:
>>> Mr Flibble <flibbleREM...@i42.co.uk> writes:
>>>
>>>> On 17/12/2016 07:00, Tim Rentsch 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.
>>>>
>>>> Nah.
>>>
>>> Mathematics is not a strength.
>>
>> The bullshit branches of Mathematics are indeed not a strength mate
>> because I see them for what they are: nonsense; they should be an
>> adjunct to mathematics not a part of mathematics. There is no negative
>> zero; and division by zero is undefined.
>
> Mathematics is not a strength is it. Simple maths - junior school maths
> - you're ok with. Harder stuff you just dismiss.

No I don't dismiss the harder stuff; I dismiss bollocks such as
projective geometry. It isn't mathematics it is an abstraction of
mathematics.

>
> Tell us again how linked lists change the order of quicksort.

See my other reply.

> Show your working.

Fuck off you self important cunt.

/Flibble

[Mr Flibble]

On 18/12/2016 21:56, Mr Flibble wrote:
> On 18/12/2016 21:52, Gareth Owen wrote:
>> Mr Flibble <flibbleREM...@i42.co.uk> writes:
>>
>>> On 18/12/2016 21:15, Gareth Owen wrote:
>>>> Mr Flibble <flibbleREM...@i42.co.uk> writes:
>>>>>
>>>>> Nah.
>>>>
>>>> Mathematics is not a strength.
>>>
>>> The bullshit branches of Mathematics are indeed not a strength mate
>>> because I see them for what they are: nonsense; they should be an
>>> adjunct to mathematics not a part of mathematics. There is no negative
>>> zero; and division by zero is undefined.
>>
>> Mathematics is not a strength is it. Simple maths - junior school maths
>> - you're ok with. Harder stuff you just dismiss.
>
> No I don't dismiss the harder stuff; I dismiss bollocks such as
> projective geometry. It isn't mathematics it is an abstraction of
> mathematics.
>

As I can read you like a book and anticipate your next reply: yes the
complex plane is an abstraction and no I don't think complex number
theory is bullshit. This is not the same kind of abstraction as made
with projective geometry.

/Flibble

[Paavo Helde]

So, how do you tell apart which abstractions are good and which are bad?
In my naivety I have always thought all the maths is abstractions,
basically about the same kind ...

[Gareth Owen]

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

> No I don't dismiss the harder stuff; I dismiss bollocks such as
> projective geometry. It isn't mathematics it is an abstraction of
> mathematics.

What a terrifically, splendiferously meaningless statement.
Mathematics is not a strength, is it?

>> Tell us again how linked lists change the order of quicksort.
>
> See my other reply.

Offered no evidence or subject knowledge to back up your assertion.
Clearly mathematics is not a strength.

>> Show your working.
>
> Fuck off you self important cunt.

Now you just sound like Jerry Stuckle (albeit with a more enjoyably
Anglo-Saxon vocabulary). Maybe best stick to saying "sausages" and
pissing off fundies, yeah?

Clearly, that is where you true abilities lie.

[Gareth Owen]

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

> As I can read you like a book and anticipate your next reply: yes the
> complex plane is an abstraction and no I don't think complex number
> theory is bullshit. This is not the same kind of abstraction as made
> with projective geometry.

"God created the integers. Everything else is the work of man."
-- Leonard Kronecker (he was a mathematician, you won't know him)

In other words, its all abstractions, darling.
Instead of claiming to read me like a book, go read an actual book.

[Mr Flibble]

It is ironic that you mentioned Stuckle as I am now classifying you the
same as I classify him... *plonk*

/Flibble

[Alf P. Steinbach]

On 18.12.2016 23:22, Paavo Helde wrote:
>
> So, how do you tell apart which abstractions are good and which are bad?
> In my naivety I have always thought all the maths is abstractions,
> basically about the same kind ...

I think what Mr. Flibble means is that some esoteric mathematical
notions are being misunderstood as having practical utility for
calculations.


Cheers!,

- Alf

[Gareth Owen]

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

> It is ironic that you mentioned Stuckle as I am now classifying you
> the same as I classify him... *plonk*

Oh deary. Did getting called out on your nonsense hurt you feelings?
Try saying sausages a few times.

[David Brown]

"God made the integers, all else is the work of man"

I don't think Mr. Flibble likes any mathematics that can't be described
in terms of sausages. You can count sausages, so positive integers are
okay. You can owe someone sausages, so negative numbers are okay. You
can divide them, so rationals are okay. Basic geometry can be done with
strings of sausages. But algebraic structures of sausages, functions of
sausages, sausages in non-Euclidian spaces, all that is, in his mind,
irrelevant.

(There is nothing wrong with not being good at maths, or not knowing
much about higher level maths. Some people have studied maths at
university level - but most people have not. What bugs me about Mr.
Flibble is not that he doesn't know much maths - it's that he thinks he
knows all /real/ maths and that everything else is irrelevant nonsense.)

[Juha Nieminen]

Tim Rentsch <t...@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.

[Juha Nieminen]

Mr Flibble <flibbleREM...@i42.co.uk> wrote:
>> Show your working.
>
> Fuck off you self important cunt.

You do realize that's pretty much a concession?

If you were an honest person, you would simply admit outright that you
were wrong. Instead, you have to make the admission indirectly by resorting
to insults.

[leigh.v....@googlemail.com]

Answer me this: why do all std::list::sort implementations use merge sort rather than qsort?

Sausage sorting is a tricky business.

[bartekltg]

On 19.12.2016 13:46, leigh.v....@googlemail.com wrote:
> Answer me this: why do all std::list::sort implementations use merge sort rather than qsort?
>
> Sausage sorting is a tricky business.

And why std::sort uses introsort (qsort + heapsort as fallback), and
not, for example, in place merge sort? Both have complexity O(n log n).

Because introsort is faster.

Mergesort run log_2(n) times through the whole list.
Qsort, 2 ln(2) log_2(n) = 1.39 log_2(n) times in average case
(with median pivot a bit better, 1.188).

Qsort for list is ~40% worse. But it is still a valid sorting
methods for lists. Just not the best one nor the easiest one.

bartekltg

[gwowen]

On Monday, December 19, 2016 at 7:58:50 AM UTC, David Brown wrote:

> What bugs me about Mr. Flibble is not that he doesn't know much maths -
> it's that he thinks he knows all /real/ maths and that everything
> else is irrelevant nonsense.)

I agree completely with this sentiment.

Incidentally, one could probably abstract projective geometry using
the approximately-spherical layer of sausage meat that surrounds a
scotch egg. Maybe if someone were to formulate like that....

[gwowen]

On Monday, December 19, 2016 at 12:46:44 PM UTC, leigh.v....@googlemail.com wrote:
> Answer me this: why do all std::list::sort implementations use merge sort
> rather than qsort?

LMGTFY:
http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort
https://www.quora.com/What-algorithm-do-popular-C++-compilers-use-for-std-sort-and-std-stable_sort

Short answer: These days they mostly use introsort. And they do so because introsort is faster, particularly on almost-sorted datasets, and its good to avoid pathological behaviour, even if it isn't necessary to meet the average-case complexity.

They used to use merge-sort, because merge-sort is stable, and quicksort/intro-sort is unstable unless you do some extra bookkeeping (which does not increase the big-Oh behaviour).

NB: All those intro/quick/merge sort behaviours are the same for arrays, vectors and other containers.

[bartekltg]

On 19.12.2016 15:40, gwowen wrote:
> On Monday, December 19, 2016 at 12:46:44 PM UTC,
> leigh.v....@googlemail.com wrote:
>> Answer me this: why do all std::list::sort implementations use
>> merge sort rather than qsort?
>
> LMGTFY:

At leas you could do it correctly.

> http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort

>
> Short answer: These days they mostly use introsort. And they do so
> because introsort is faster, particularly on almost-sorted datasets,
> and its good to avoid pathological behaviour, even if it isn't
> necessary to meet the average-case complexity.

And yo get it from what?
From this sentence from the first answer:
"...std::sort is implemented as a intro-sort (introspective sort),..."

Jerry Coffin didn't understand the question. When you go to the
second answer or to the second thread:

http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort

You get the real answer.

You can also look at the code in your computer.
In my it is mergesort gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0

> NB: All those intro/quick/merge sort behaviours are the same for
> arrays, vectors and other containers.

What do you mean?



bartekltg

[Gareth Owen]

bartekltg <bart...@gmail.com> writes:

> Jerry Coffin didn't understand the question. When you go to the
> second answer or to the second thread:
>
> http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort
>
> You get the real answer.

I stand corrected[0]. See also here.

http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117

Leigh please note: The answer is *not* because quicksort on linked lists
is worse O(n log n) on average.

> What do you mean?

That intro-sort is a better choice that quicksort for sorting all sorts
of containers for exactly the same reasons its a better choice for
sorting lists. Which is true.

[0] Well, I suppose I could just shout abuse at you, or call you a troll.

[Mr Flibble]

So qsort is 40% slower than merge sort on a linked list eh Gareth
matey?. So I was correct. 40. %. slower.

If I am totally honest I have not actually looked at the implementation
of qsort for linked lists I just had a gut feeling that it would be
non-optimal compared to other methods as qsort was designed for arrays
however you are forgetting one very important thing:

Being wrong (even deliberately so) on the Internet is the quickest way
to illicit correct information on the Internet.

/Flibble

P.S. Liver and onions tonight not sausages.

[Mr Flibble]

On 19/12/2016 19:09, Mr Flibble wrote:
>
> Being wrong (even deliberately so) on the Internet is the quickest way
> to illicit correct information on the Internet.

s/illicit/elicit/

/Flibble

[Gareth Owen]

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

> On 19/12/2016 14:40, gwowen wrote:
>> On Monday, December 19, 2016 at 12:46:44 PM UTC, leigh.v....@googlemail.com wrote:
>>> Answer me this: why do all std::list::sort implementations use merge sort
>>> rather than qsort?
>>
>> LMGTFY:
>> http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort
>> https://www.quora.com/What-algorithm-do-popular-C++-compilers-use-for-std-sort-and-std-stable_sort
>>
>> Short answer: These days they mostly use introsort. And they do so
>> because introsort is faster, particularly on almost-sorted datasets,
>> and its good to avoid pathological behaviour, even if it isn't
>> necessary to meet the average-case complexity.
>>
>> They used to use merge-sort, because merge-sort is stable, and
>> quicksort/intro-sort is unstable unless you do some extra
>> bookkeeping (which does not increase the big-Oh behaviour).
>>
>> NB: All those intro/quick/merge sort behaviours are the same for
>> arrays, vectors and other containers.
>
> So qsort is 40% slower than merge sort on a linked list eh Gareth
> matey?. So I was correct. 40. %. slower.

No. You said average-case algorithmic complexity was worse.
That's not the same thing at all.

[Mr Flibble]

No I said (as a complete guess I admit) the worst-case complexity was
more likely (which may be wrong, don't much care). However I have
already said that I haven't actually looked at linked list qsort
implementation and I don't intend to ever do so as I would never use
qsort to sort a linked list.

/Flibble

[Mr Flibble]

Yes I agree totally: sausages are important. If it doesn't work with
sausages it is woo.

/Flibble

[Mr Flibble]

From Wikipedia:

"Although quicksort can be implemented as a stable sort using linked
lists, it will often suffer from poor pivot choices without random access."

https://en.wikipedia.org/wiki/Quicksort#Relation_to_other_algorithms

/Flibble

[bartekltg]

On 19.12.2016 19:53, Gareth Owen wrote:
> bartekltg <bart...@gmail.com> writes:
>
>> Jerry Coffin didn't understand the question. When you go to the
>> second answer or to the second thread:
>>
>> http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort
>>
>> You get the real answer.
>
> I stand corrected[0]. See also here.
>
> http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117
>
> Leigh please note: The answer is *not* because quicksort on linked lists
> is worse O(n log n) on average.

I'm not sure, did you change your opinion?


std::list::sort is almost (*) always mergesort

*) I didn't see implementation with different algorithm,
but of course I can't be sure there is none ;-)

>> What do you mean?
>
> That intro-sort is a better choice that quicksort for sorting all sorts
> of containers for exactly the same reasons its a better choice for
> sorting lists.

Containers with random access, so vector (array...) implemented in
continuous memory block.

Merge sort do _less_ work, but mergesort need either additional
(linear in size) memory or quite complicated tricks, while
qsort is quite cache friendly.

As a results, qsort work faster on vector and similar containers.

Both, disadvantage of mergesort and advantage of qsort, disappears
in the case of a list.

Just write both and compare. For a list mergesort (written in proper
way, look at std::list::sort) is faster.

bartekltg

[Gareth Owen]

bartekltg <bart...@gmail.com> writes:

> On 19.12.2016 19:53, Gareth Owen wrote:
>> bartekltg <bart...@gmail.com> writes:
>>
>>> Jerry Coffin didn't understand the question. When you go to the
>>> second answer or to the second thread:
>>>
>>> http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort
>>>
>>> You get the real answer.
>>
>> I stand corrected[0]. See also here.
>>
>> http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117
>>
>> Leigh please note: The answer is *not* because quicksort on linked lists
>> is worse O(n log n) on average.
>
>
> I'm not sure, did you change your opinion?

Which opinion?

> std::list::sort is almost (*) always mergesort

I agree with this now.

> *) I didn't see implementation with different algorithm,
> but of course I can't be sure there is none ;-)

Of course.

> As a results, qsort work faster on vector and similar containers.

But only by a multiplicative factor, so time-big-Oh sense they're the
same. Or rather intro-sort and merge-sort are big-Oh-the-same
(worst case n*log n) but the multiplicative factor changes depending on
whether you can do random access or you have to traverse the list.

[Juha Nieminen]

Mr Flibble <flibbleREM...@i42.co.uk> wrote:
> So qsort is 40% slower than merge sort on a linked list eh Gareth
> matey?. So I was correct. 40. %. slower.

Your problem is that you don't understand what asymptotic complexity
and the big-O notation mean.

Your claim was about the asymptotic complexity of quicksort on
linked lists, not on absolute speed (ie. in practice the constant
factor in terms of computational complexity).

In addition to that, you weren't comparing quicksort on linked
lists to merge sort on linked lists. You were comparing quicksort
on linked lists to quicksort on random access arrays (and claiming
that the former is worse in terms of asymptotic complexity). It's
useless to now cling onto those quicksort vs mergesort numbers,
because that wasn't your original claim, nor what people objected to.

[leigh.v....@googlemail.com]

Mr Flibble fully understands asymptotic complexity and Big-O notation.

Mr Flibble claimed that the worst case complexity was more likely due to poor pivot choice.

Again Mr Flibble didn't claim the former was worse in asymptotic complexity just that worst case complexity was more likely.

[Juha Nieminen]

leigh.v....@googlemail.com wrote:
> just that worst case complexity was more likely.

No, he didn't claim that.

[Gareth Owen]

"AFAIK quicksort will not work with linked lists;"
"If by "works" you mean "works slowly, O(n)".
"By "O(n)" I actually meant "worse than O(n)*O(lg N)".

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

I look forward to you Stuckling out of that.

[Incidentally, you *actually* meant 'worse than O(N * lg N)']

[Mr Flibble]

Yes, he did.

[Mr Flibble]

"Due to poor pivot choice worst case performance will manifest more
often and that is quadratic complexity."

So fuck off; I am right and you are wrong.

>
> [Incidentally, you *actually* meant 'worse than O(N * lg N)']

O(N)*O(lg N) is the same as O(N * lg N) (the latter being a simplification)

/Flibble

[Ben Bacarisse]

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

> On 21/12/2016 19:28, Gareth Owen wrote:
>> leigh.v....@googlemail.com writes:
>>
>>> Mr Flibble fully understands asymptotic complexity and Big-O notation.
>>>
>>> Mr Flibble claimed that the worst case complexity was more likely due
>>> to poor pivot choice.
>>>
>>> Again Mr Flibble didn't claim the former was worse in asymptotic
>>> complexity just that worst case complexity was more likely.
>>
>>
>> "AFAIK quicksort will not work with linked lists;"
>> "If by "works" you mean "works slowly, O(n)".
>> "By "O(n)" I actually meant "worse than O(n)*O(lg N)".
>>
>> *******************************************************
>> ***** 'I actually meant "worse than O(n)*O(lg N)"' ****
>> *******************************************************
>>
>> I look forward to you Stuckling out of that.
>
> "Due to poor pivot choice worst case performance will manifest more
> often and that is quadratic complexity."

Is this a sociological claim rather than a technical one? There's no
technical reason why the choice of pivot should be a poor one in a
linked list implementation, but the last time that was pointed out your
reply was simply "Nah", so maybe you do still think you are raising a
technical issue about algorithms.

<snip>
--
Ben.

[Gareth Owen]

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

> "Due to poor pivot choice worst case performance will manifest more
> often and that is quadratic complexity."

Not true - Quicksort is O(N log(N)) on average even with the simplest
choice of pivot (the last element).

If you believe otherwise, please explain why.

> So fuck off; I am right and you are wrong.

Not true. Maths isn't a strong point, is it?

[Gareth Owen]

He claimed both. They're equally wrong.

[Mr Flibble]

On 21/12/2016 20:53, Gareth Owen wrote:
> Mr Flibble <flibbleREM...@i42.co.uk> writes:
>
>> "Due to poor pivot choice worst case performance will manifest more
>> often and that is quadratic complexity."
>
> Not true - Quicksort is O(N log(N)) on average even with the simplest
> choice of pivot (the last element).
>
> If you believe otherwise, please explain why.

From Wikipedia:

"Although quicksort can be implemented as a stable sort using linked
lists, it will often suffer from poor pivot choices without random access."

https://en.wikipedia.org/wiki/Quicksort

>

>> So fuck off; I am right and you are wrong.
>
> Not true. Maths isn't a strong point, is it?

This has nothing to do with maths; this is to do with analysing
algorithmic complexity. See Wikipedia above.

/Flibble

[Gareth Owen]

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

>>> So fuck off; I am right and you are wrong.
>>
>> Not true. Maths isn't a strong point, is it?
>
> This has nothing to do with maths; this is to do with analysing
> algorithmic complexity.

*facepalm* Analysing algorithms is a discipline of mathematics.

> See Wikipedia above.

Nevertheless, if you were capable of doing the mathematics, you'd see
that the average case performance is still O(N log N). The proof that
quicksort is O(N log N) on average is independent of the underlying data
structure. The reason for this is that choosing a sane pivot (median of
nine say) is O(n), and you can do a fixed number of different O(n) at
each recursive step you don't change the algorithmic complexity (but you
might screw up the constants so badly that it runs much slower than
mergesort).

The Wikipedia section on "Selection based pivoting" describes a scheme
based on this fact.

Note also that proviso in Wikipedia is about *stable* quicksort, and
std::list::sort is *not* required to be stable. Note also, that some
time ago I mentioned that mergesort is often preferred because it is
stable, where quicksort isn't.

> /Flibble

PS: Your killfile is broken

[Mr Flibble]

On 21/12/2016 23:34, Gareth Owen wrote:
> Mr Flibble <flibbleREM...@i42.co.uk> writes:
>
>>>> So fuck off; I am right and you are wrong.
>>>
>>> Not true. Maths isn't a strong point, is it?
>>
>> This has nothing to do with maths; this is to do with analysing
>> algorithmic complexity.
>
> *facepalm* Analysing algorithms is a discipline of mathematics.

No, it isn't; it is a discipline of computer science and algorithmics.

[snip]

> Note also that proviso in Wikipedia is about *stable* quicksort, and
> std::list::sort is *not* required to be stable. Note also, that some
> time ago I mentioned that mergesort is often preferred because it is
> stable, where quicksort isn't.

Wrong. std::list::sort *is* required to be stable.

/Flibble

[Tim Rentsch]

Gareth Owen <gwo...@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.

[Tim Rentsch]

Juha Nieminen <nos...@thanks.invalid> writes:

> Tim Rentsch <t...@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. :)

[Mr Flibble]

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

[woodb...@gmail.com]

On Monday, December 19, 2016 at 1:58:50 AM UTC-6, David Brown wrote:
> On 18/12/16 23:22, Paavo Helde wrote:
> > On 19.12.2016 0:04, Mr Flibble wrote:
> >> On 18/12/2016 21:56, Mr Flibble wrote:

> >>> On 18/12/2016 21:52, Gareth Owen wrote:
> >>>> Mr Flibble <flibbleREM...@i42.co.uk> writes:
> >>>>
> >>>>> On 18/12/2016 21:15, Gareth Owen wrote:
> >>>>>> Mr Flibble <flibbleREM...@i42.co.uk> writes:
> >>>>>>>

> >>>>>>> Nah.
> >>>>>>
> >>>>>> Mathematics is not a strength.
> >>>>>
> >>>>> The bullshit branches of Mathematics are indeed not a strength mate
> >>>>> because I see them for what they are: nonsense; they should be an
> >>>>> adjunct to mathematics not a part of mathematics. There is no negative
> >>>>> zero; and division by zero is undefined.
> >>>>
> >>>> Mathematics is not a strength is it. Simple maths - junior school
> >>>> maths
> >>>> - you're ok with. Harder stuff you just dismiss.
> >>>
> >>> No I don't dismiss the harder stuff; I dismiss bollocks such as
> >>> projective geometry. It isn't mathematics it is an abstraction of
> >>> mathematics.
> >>>
> >>
> >> As I can read you like a book and anticipate your next reply: yes the
> >> complex plane is an abstraction and no I don't think complex number
> >> theory is bullshit. This is not the same kind of abstraction as made
> >> with projective geometry.
> >
> > So, how do you tell apart which abstractions are good and which are bad?
> > In my naivety I have always thought all the maths is abstractions,
> > basically about the same kind ...
> >
>
> "God made the integers, all else is the work of man"

I agree with the German astronomer Kepler when he
described his mathematical work as "thinking G-d's
thoughts after Him."

http://inventors.about.com/od/famousinventors/fl/Johannes-Kepler-Astronomy.htm

Johannes Kepler was born on December 27, 1571, in Weil der Stadt, Württemburg,
------------------------------------------------------------

Kepler sounds like he was a mensch -- a decent and humble man.


Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[Tim Rentsch]

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.

[Daniel]

On Monday, December 19, 2016 at 2:58:50 AM UTC-5, David Brown wrote:
>
> "God made the integers, all else is the work of man"
>

Depends where you want to start. You can start with set theory, and derive the
integers as equivalence classes. Mr Fliblle, as you note, starts with sausages.

God, of course, is the ultimate undefined concept. Assume there is a god with some
properties, and see what follows.

Best regards,
Daniel

[Mr Flibble]

So how to get the middle element without traversing linked list O(n)
times for each partition? You are basically contradicting yourself.

/Flibble

[Gareth Owen]

Mr Flibble <flibbleREM...@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.

[Mr Flibble]

On 23/12/2016 20:56, Gareth Owen wrote:
> Mr Flibble <flibbleREM...@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

[Mr Flibble]

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

[David Brown]

On 23/12/16 21:08, Daniel wrote:
> On Monday, December 19, 2016 at 2:58:50 AM UTC-5, David Brown wrote:
>>
>> "God made the integers, all else is the work of man"
>>
> Depends where you want to start. You can start with set theory, and derive the
> integers as equivalence classes. Mr Fliblle, as you note, starts with sausages.

Yes, you have to start somewhere. If you pick axiomatic set theory, you
can derive integers from there - but you can keep going and make
rationals, reals, complex numbers, infinite cardinals and ordinals (who
volunteers to explain to Mr. Flibble that the first countably infinite
ordinal, ω, has 1 + ω = ω, but ω + 1 > ω ?), and any other mathematics
you like. From a mathematical viewpoint, integers are as constructed as
anything else.

I don't think anyone has thought of a system more fundamental than set
theory (from which set theory could be derived). But maybe someone will
eventually.

[Mr Flibble]

On 27/12/2016 09:39, David Brown wrote:
> 1 + ω = ω

If "+" means addition than 1 + ω = ω is patently false.

/Flibble

[Mr Flibble]

This of course is predicated on ω being a variable and not a
classification: if it is a classification then I assume it means
something along the lines of:

1 + an integer = an integer

So basically, David Brown, stop being such a pompous dick.

/Flibble

[Gareth Owen]

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

> On 27/12/2016 17:48, Mr Flibble wrote:
>> On 27/12/2016 09:39, David Brown wrote:
>>> 1 + ω = ω
>>
>> If "+" means addition than 1 + ω = ω is patently false.
>
> This of course is predicated on ω being a variable and not a
> classification: if it is a classification then I assume it means
> something along the lines of:

It's the first transfinite ordinal - which you'd know if ... oh, never mind.

Suffice to say, it's the correct and normal notation used in explaining
the Hilbert Hotel paradox and such like, a formally correct way of
writing what we casually think of as
1+∞ = ∞

[Mr Flibble]

Not the same thing at all which you'd know if you weren't an autsy
fucktard*.

/Flibble

* Not all autistic people are fucktards

[Gareth Owen]

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

> Not the same thing at all which you'd know if you weren't an autsy
> fucktard*.

You're funny. Not massively smart, but funny.

[Mr Flibble]

Not smart? Infinity is not a member of the set of ordinals (which must
be integers). As I said you are the fucktarded one not me.

/Flibble

[Gareth Owen]

Omega is the first "transfinite ordinal". This is first-year university
level mathematics, so you won't have come across it. It is the ordinal
associated with the set integers but is not itself an integer. Rather
it is a member of a larger set of which the integers are a proper
subset. Note the first and fourth bullet points on this page

https://en.wikipedia.org/wiki/Transfinite_number

which prove, once again, that you don't know what you're talking about.

Go read a maths book above high school level, Leigh. Actually, don't,
you're much less boring when you're being stubbornly ignorant.

Also, didn't claim to have killfiled me last week?

Can you do it again please? I much prefer it when you don't reply to me,
as I don't feel obliged to endlessly point out how you know.

[Mr Flibble]

You are full of shit. Just as with the Riemann sphere, extended complex
plane and projective geometry which are all bullshit you think infinity
can be a member of a set. Infinity is NOT an ordinal number; these
abstractions are made up by minds which were fried; you have been
drinking the too much koolaid (or your mind is also fried) if you think
differently.

/Flibble