Linked List sorting

[jadmakh]

hello!

what is the code to sort a Linked List of Linked lists ? thank you for your help.

[o3hC5Di1]

Hi there,

That depends on several factors, such as which sorting algorithm you would like to use and what you would like to sort on.

Are the contained linked list sorted themselves, or do they need to be sorted too?
Are you using std::list or a custom implementation?

If you would be so kind as to provide us some more information I'm someone will be happy to help you.

All the best,
NwN

[jadmakh]

Thank you so much! the contained linked lists (of char *) are already sorted, I'm not sure which sorting algorithm I have to use, it doesn't matter I guess.
I have to sort the "big" linked list alphabetically according to the first element in each contained list.

hope I'm clear enough

thank you again

for example

car rac
dog god
bed

will become :

bed
car rac
dog god


(actually this is a final step of a big problem about finding anagrams and sorting them, I did all the work this part is still missing)

[o3hC5Di1]

Hi there,

Is your "small list" a different list-type (class) than your "big list"?
If so, you could simply overload operator<() and use std::sort to do the hard work:
http://www.cplusplus.com/reference/algorithm/sort/

If you are required to do it "manually", for linked lists i think bubble sort is probably the easiest to implement because it just traverses the list. A very good explanation on bubble sort is available here:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/bubble-sort/

In short:

- Loop through the big list, if the first element of the child is smaller than the next one, swap the two.
- keep doing this until the list is sorted (no swaps were made).

Please do come back to us with some of your code if you require any further assistance.

All the best,
NwN

[jadmakh]

#include <iostream>
#include <algorithm>
#include <string>
#include <llist.h>
#include <fstream>

using namespace std;


template <typename E> class sortedLList: public LList<E> {
public:



sortedLList () : LList () {};


void removeall() { // Return link nodes to free store
while(head != NULL) {
curr = head;
head = head->next;
delete curr;
}
}

~sortedLList() { removeall(); }


void insert (const E& item)
{


if(cnt!=0)
{
curr = head;

while(true)
{
if ( lessthan(item,curr->next->element) ){break;}
if(curr->next == tail) {curr = curr->next; break;}
curr = curr->next;
}
}

curr->next = new Link<E>(item, curr->next);
if (tail == curr) tail = curr->next; // New tail
cnt++;

}



void print()
{
Link<E> * g = curr;

curr = head->next;
while(curr!=tail)
{
cout<<curr->element<<' ';
curr = curr->next;
}
cout<<curr->element;

curr = g;

}



};

bool findAnagram (char * t, char *s)
{ string a=t;
string b=s;
char *y;
char *x;
y=new char [a.size ()+1];
x=new char [b.size()+1];
std::sort (a.begin(),a.end());
std::sort (b.begin (), b.end ());
std::strcpy (y,a.c_str());
std::strcpy(x,b.c_str());

if (strcmp (x,y)==0) return true;
if (strcmp(x,y)!=0) return false;

}


bool lessthan(char * a, char * b);


int main ()
{

ifstream in;
char *t1;
char *t2;
char *t3;
string s2;
char * t;
string s;

in.open ("anagramEasy.txt",ios::in);
sortedLList<char *> A;
LList <sortedLList<char *> *> B;

B.insert (&A);

in>>s;
t1=new char [s.size ()+1];
std::strcpy(t1,s.c_str());
A.insert(t1);


in>>s;
while (!in.fail())
{
t3=new char [s.size()+1];

std::strcpy (t3,s.c_str());


std::sort (s.begin (), s.end ());
t2=new char [s.size()+1];
std::strcpy (t2,s.c_str());
B.moveToStart();
bool i=false;
while (B.curr->next!=NULL)
{ s2=B.getValue ()->head->next->element;

std::sort (s2.begin (), s2.end ());
t=new char [s2.size()+1];
std::strcpy (t,s2.c_str());
if (findAnagram (t,t2))
{B.getValue()->insert(t3);
i=true;
break;
}




B.next();
}

if (i==false )
{
sortedLList<char *>*C= new sortedLList <char *> ;
B.insert(C);
C->insert (t3);

}




in>>s;

}
/*
int r;

char* temp;
char* m;
char*n;
temp=new char [];
m=new char [];
n=new char [];

for (B.curr=B.head;B.curr->next->next!=NULL;B.curr=B.curr->next)

{
m=B.getValue()->curr->element;
n=B.getValue()->curr->next->element;


if (n<m)
{temp=B.getValue()->curr->element;
B.getValue()->curr->element=B.getValue()->curr->next->element;
B.getValue()->curr->next->element=temp;
}

}*/


int n=B.length();


}

for (B.curr=B.head;B.curr->next!=NULL;B.curr=B.curr->next)
{
B.getValue ()->print();
cout << endl;
}







}
bool lessthan(char * a, char * b)
{

string s1 = a;
string s2 = b;
if (s1<s2) return true; else return false;

}


this is my code and i'd like to sort B

[Josue Molina]

Given you have a linked list of linked lists, you first need to lexicographically sort the strings in the linked lists, and then lexicographically sort the lists in the linked list based on their first element.

[jadmakh]

that's exactly what I don't how to do, how can I " lexicographically sort the lists in the linked list based on their first element. " ?

[Josue Molina]

Suppose that I have a list of lists L, and that the elements of each L[i] are sorted. Then, to sort L, I would iterate it, comparing against L[i][0]. Does that make more sense?

Here is some pseudo code:

do
    has_swapped = false
    for i from 0 to L.size - 1,
        if L[i][0] > L[i + 1][0]
            swap(L[i][0], L[i + 1][0])
            has_swapped = true
while has_swapped

[jadmakh]

how can I transform a List into an array?

[Josue Molina]

You don't have to transform the list into an array; I used array notation only to be succinct.

Here's a visualization of your list:

https://dl.dropboxusercontent.com/u/12189012/list%20of%20lists.png

The red circles are what you're comparing against to sort L.

I hope this vivifies my suggestion above.

Edit: here's a quick, commented, working example of everything I've been suggesting to you:

http://ideone.com/AISZqA

If I were you, I would add a (re) sort method to my linked list class that takes a comparer lambda expression; this would make it even more general, as I could then kill many birds with one stone.