Sorting linked list

This is a discussion on Sorting linked list within the C++ Programming forums, part of the General Programming Boards category; I have a code able to import a file containing words and numbers to a linked list, but I also ...

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    12

    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();
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,528
    Quote Originally Posted by iMalc View Post
    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.
    Manasij Mukherjee | gcc-4.9.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Remember, for four items, n*n/2 = 8 and n*log2(n) = 8
    The sorts that are more efficient at larger sizes tend to also do extra things that the O(n*n) sort doesn't need to. Like walk through a list to cut it in half, make recursive calls, have more variables than fits into registers easily, or have more branches for the CPU to mispredict.
    Whether it's arrays or lists, O(n*n) sorts do tend to win for the smaller numbers. It might be only up to 8 that they win, or it might be up to 32, depending upon the actual implementations.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,806
    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.
    Do you have to use your own linked list implementation rather than an existing one (the STL list class for example)?





    Code:
    void main()
    From the FAQ:
    What's the deal with void main()

    Under regular function calling/returning in C and C++, if your don't ever want to return anything from a function, you define it's return type as void. For example, a function that takes no arguments, and returns nothing can be prototyped as:

    void foo(void);

    A common misconception is that the same logic can be applied to main(). Well, it can't, main() is special, you should always follow the standard and define the return type as int. There are some exceptions where void main() is allowed, but these are on specialized systems only. If you're not sure if you're using one of these specialized systems or not, then the answer is simply no, you're not. If you were, you'd know it.

    Be warned that if you post your "void main" code on the forums, you're going to get told to correct it. Responding with "my teacher said it's OK" is no defence; teachers have a bad habit of being wrong. Be safe, and post only standard code, and you'll find people concentrate on answering your other problems, rather than waste time telling you about this type of thing.



    Code:
    #include <conio.h>
    
    ...
    
    getch();
    These represent a non-standard header/function. Non-standard things should be avoided where possible. There should be no reason for you to use them when a simple call - or two - to cin.get() should suffice.




    Code:
    while(!inFile.eof())
    FAQ > Explanations of... > Why it's bad to use feof() to control a loop
    The link describes the problem using C code but the lesson does translate to the C++ realm.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  6. #6
    Registered User
    Join Date
    Oct 2006
    Posts
    2,590
    Quote Originally Posted by hss1194 View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting a linked list
    By Anass in forum C Programming
    Replies: 7
    Last Post: 10-27-2010, 07:56 AM
  2. Linked List Sorting
    By oddworld in forum C Programming
    Replies: 4
    Last Post: 04-27-2007, 11:42 PM
  3. linked list sorting..
    By dlcp in forum C Programming
    Replies: 7
    Last Post: 04-10-2007, 07:03 AM
  4. Sorting a linked list
    By thoseion in forum C Programming
    Replies: 6
    Last Post: 11-13-2006, 10:34 AM
  5. sorting linked list
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 11:08 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21