Thread: linkedlist sort

I am new to the world of c++ and am trying to learn on my own i was wondering if i have a linked list

struct node
{
int item;
node* next;
};

what would be the best wat to sort this list (in assending order)
and could you please show me what that sort would look like
thanks

Well unregged, you might have better luck using an STL list rather than a plain single link list.

.sort() will automatically and quickly sort your list, provided operator< is defined for whatever data type the list is of.
.reverse() will turn it around

.copy() will dump the list into another iterator.

.copy()'ing to ostream_iterator<WHATEVER_YOUR_TYPE_IS>(cout, "\n") will output it. You can change the \n to any delimiter you want.

Load this, c/l/r it, then see if you can adapt it to your problem:

Code:

#include <iostream>
#include <list>
#include <string>         

   int main () {           
      list<string>f;
      f.push_back("Tarp");
      f.push_back("Yellow");
      f.push_back("Alpha");
      f.push_back("Doggie");
      f.push_back("Markers");
      f.push_back("Bush");
      copy(f.begin(), f.end(), ostream_iterator<string>(cout, "\n"));
      f.sort();
      cout << '\n';
      copy(f.begin(), f.end(), ostream_iterator<string>(cout, "\n"));
      f.reverse();
      cout << '\n';
      copy(f.begin(), f.end(), ostream_iterator<string>(cout, "\n"));
      return 0;
   }

Enjoy

Whoops put a using namespace std; in there, sorry.

How can you overload the operator< for you own datatype that is stored in the list ?

do you have an example using a class say Myclass sorting on the attribute char * (points to a new char array) maybe sorting alphabetically ?

you could try this. not compiled. not tested:

Code:

//use keyword class if you prefer, but make members public then
struct myStruct
{
  char name[20];
  bool operator <(const & rhs);
};

//overload the < operator for myStruct
//this will be case sensitive comparison!
bool myStruct::operator <(const & rhs)
{
  if(strcmp(name, rhs.name) < 0)
    return true;
  return false;
}

//create list using type myStruct as type in list
list <myStruct> myList;

//variables for loop counter and to hold user input 
int i;
myStruct dummy;

//add 5 instances of myStruct to end of myList using user input
for(i = 0; i < 5; i++)
{
  cout << "enter a name without spaces" << endl;
  cin >> myStruct.name;
  myList.push_back(myStruct);
}

//sort myList alphabetically using list::sort()
//uses overloaded < operator for type myStruct
myList.sort();