-4

Possible Duplicate:
Sorting a Doubly Linked List C++ Question

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
}
Improve this question
5
  • This is confusing are you sorting the list or just the contents of the node? Any mixture does not make sense to me. Commented Sep 6, 2009 at 20:26
  • Duplicates stackoverflow.com/questions/1382273/… and stackoverflow.com/questions/1309960/linkedlist-part Commented Sep 6, 2009 at 20:26
  • It successfully sorts one node, But it keeps printing that Node because, it is the lowest node, So the function keeps returning it. I need to sort the rest, a second_least_node. Commented Sep 6, 2009 at 20:38
  • You should try to use the correct terminology otherwise, people will tend to get confused trying to understand you. For example, you are not "sorting" the list, you are "searching" it. Commented Sep 6, 2009 at 20:48
  • 1
    @lampshade: This is your third variation of this question, and you don't seem to be making much progress. Part of the problem may be that your questions are unclear: they use imprecise vocabulary, and you don't really say what is preventing you from moving forward. Are you stuck because (1) you don't actually understand the probelm that has been posed for you, (2) you don't know how to solve the problem using (say) a bunch on index cards and a pencil, (3) you can't translate the solution into the need c++ syntax, or (4) some other reason? Commented Sep 6, 2009 at 21:20

2 Answers 2

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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));
Improve this answer

4 Comments

Or use a sort algorithm which can be used with linked list structures, such as merge sort.
Im trying to get around the array.
what would i do after declaring a node **nArray = new node*[size]; ?
What do you want to do with it?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.