Sorting Doubly Linked List C++

Question

hey guys,

as of right now the sort function that I have only sorts 1 node out of the many.

I need this function disregard the node that is sorted only after it is printed.

I've tried removing the node so that it is not considered twice for the sort, because It will keep printing that same sorted node over and over again. That didnt work so here i am.

This is defined and its where I call my sorting function. It has one node *Paramater and returns a node.

void list::displayByName(ostream& out) const
{
 node *current_node  = headByName; // is  @the head of the list
 node *evil_node     = tail;

 while ( current_node != NULL )
 {
  current_node = sort( current_node );
  out << current_node->item.getName() << endl;
 }
}

Defined as a private function of my list class.

list::node * const list::sort( node *given_node ) const
{ 
 node *least_found_node = NULL;
 node *current_node    = given_node->nextByName;

 while ( current_node && current_node != given_node ) // while current_node != NULL and..
 {   
  if ( strcmp( current_node->item.getName(), given_node->item.getName() ) < 0 )
  {
   if ( least_found_node == NULL ||  
      ( strcmp( least_found_node->item.getName(), current_node->item.getName() ) > 0 ) )
   {
    least_found_node = current_node;
   }
  }
  current_node = current_node->nextByName;

 }

 return least_found_node; // return that sorted node
}

Answer 1

I think you are trying to do this all wrong. Your algorithm is likely to be extremely inefficient since you are doing a linear search repeatedly through the whole list. I would copy the list into an array, and then sort the array. Something like this:

node *current_node  = headByName

std::vector<node *> list;
while (current_node)
{
  list.push_back(current_node);
  current_node = current_node->nextByName;
}

std::sort(list.begin(), list.end(), someKindOfSortByNameFunction);

std::foreach(list.begin(), list.end(), std::ostream_iterator<node>(out, std::endl));

Answer 2

I bet you won't benefit from my answer, but there are O(Nlog(N)) algorithms that are applicable to doubly-linked lists.

The first one is merge-sort. This algorithm is applicable not only to doubly-linked lists, but for any sets (if we assume the Axiom of choice ;-) ). You select an arbitrary element from the list and then bulk your list into two piles: elements that are greater than the one picked and the elements that are greater that it. Then you recursively sort these piles and merge them together.

The second one is Hoare's quicksort. You pick an arbitrary element and iterate the list from its ends towards each other. You swap values referenced by the iterators if first one is greater that selected value and the second one is lower (we sort ascendingly). When iterators meet, you sort list to the left and list to the right in the same way.