Thread: Sorting linked list

I have a code able to import a file containing words and numbers to a linked list, but I also need to sort this linked list alphabetically. I've done research on this involving bubble sorting, but no explanation has helped me achieve this objective. Could anyone help me with this?

Below is the code that can only put the file into linked list:

Code:

#include<iostream>
#include<conio.h>
#include"U:\C++\WordClass2\WordClass2\WordClass.cpp"
#include<fstream>
#include<vector>
#include<string>
using namespace std;


struct node
{
    string dictionary;
    node *next;
};


void main()
{
    ifstream inFile;
    ofstream outFile;
    string dictionary;
    inFile.open("llmessage.txt");
    outFile.open("outstream.txt");
    node *first=NULL, *temp=NULL, *curr=NULL, *last=NULL, *list=NULL;
    cout<<"Enter a file to read: ";
    getline(cin,dictionary);
    inFile.open(dictionary);
    while(!inFile.eof())
    {
        node *temp = new node;
        inFile>>temp->dictionary;
        //last->word=temp;
        if(temp->dictionary=="")
        {
            temp=NULL;
            if(temp==NULL)
            {
                break;
            }
        }
        else
        {
            if(first==NULL)
            {
                first=temp;
                last=temp;
            }
            else
            {
                if(temp>first)
                {
                    first->next=temp;
                }
                else
                {
                    last->next=temp;
                    last=temp;
                    last->next=NULL;
                }
            }
        }
    }
    temp=first;
    outFile.open("outstream.txt");
    while(1)
    {
        if(temp->next==NULL){break;}
        cout<<temp->dictionary<<endl;
        outFile<<temp->dictionary<<endl;
        temp=temp->next;
    }
    cout<<temp->dictionary<<endl;
    getch();
}

Originally Posted by iMalc

Forget Bubble Sorting in this instance. While that's easy to implement for an array, it's hideously difficult to implement correctly for a linked-list, assuming you do it by re-linking the list's nodes.
By far the easiest sorting algorithm to implement for a list is Insertion Sort. Next to learn after that, if you want something faster for longer lists, is Merge Sort.

Why won't merge sort be faster for *all* lists (unless almost sorted)?
Unlike arrays, the merging here does not involve copying, so I though that the constant was much lower.

Originally Posted by hss1194

Code:

#include"U:\C++\WordClass2\WordClass2\WordClass.cpp"

I strongly recommend against doing this for two reasons:

1. Including source files is simply wrong. Don't do it.
2. Absolute paths are highly sensitive to folder structure changes. Add the path as an include path in the compiler options, and simply include the file by name, not the full path.