C++

Forum

 
Sorting names within a linked list

puffybear123 (12)
Hi I am at a lost of how to sort names in alphabetical order after having the user input them into a linked list. I manage to create a program that did have the person input names into the linked list and when it is printed it displays the names in the order of how the user inputted the names. I just don't know how to sort it, any help would be appreciated!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
#include <cstdlib>
#include <iostream>
using namespace std;
#include <string>

class NodeType {
      public:
       string NodeValue;
       NodeType *link;
};
      
class ListType {
      NodeType *next, *last, *start;
     
      public:
      ListType() { start = NULL; }        
      void buildList(void);
      void printList(void);
      void sortList(void);
      NodeType *searchList(string);
      void addValToEnd(string);
 
};

NodeType *ListType::searchList(string who)
    {
         next = start;
         while(next != NULL)
          {
             if(next->NodeValue == who)
               return next;
             else
               {
                 next = next->link;
               }
             } 
          return next;
}
         
void ListType::buildList(void)
  {
     string name;
     cout << "\n\nEnter a name or xxx to quit : ";
     cin >> name;
     while(name != "xxx")
      {
        if(start == NULL)
         {
           start = new NodeType;
           start->NodeValue = name;
           start->link = NULL;
           last = start;
         }
        else 
        {
           next = new NodeType;
           next->NodeValue = name;
           next->link = NULL;
           last->link = next;
           last = next;
        }
      cout << "\n\nEnter a name or xxx to quit: ";
      cin >> name;
      }
};
 
void ListType::printList(void)
{

     if(start == NULL)
       cout << "List is empty\n\n";
     else {
        cout << "\n\nCurrent contents of list:\n\n";
        next = start;
        while (next != NULL)
         {
           cout << next->NodeValue << "\n";
           next = next->link;
         }
      }
}
void ListType::sortList(void)
{
     
}
     
 
int main(int argc, char *argv[])
{
    bool notDone = true;
    ListType aList;
    string person, resp;
    aList.buildList();
    NodeType *loc;
    aList.printList();             
   
    system("PAUSE");
    return EXIT_SUCCESS;
}
Smac89 (1727)
Bottom-up merge sort is a fast sorting algorithm that can be used to sort linked lists

http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/7-Sort/merge-sort5.html
Topic archived. No new replies allowed.