Wednesday, December 14, 2016

Digest for comp.lang.c++@googlegroups.com - 24 updates in 7 topics

Juha Nieminen <nospam@thanks.invalid>: Dec 14 10:26AM

> 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" <alf.p.steinbach+usenet@gmail.com>: Dec 14 01:05PM +0100

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.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)