Algorithm for sorting names

[XboxOne2019]

Hey guys, I am trying to figure out how to write this algorithm for a program we are doing. We have to read in names and phone numbers as strings and then store them in a link list. I cannot figure out how to write the code to add the names as they are read in. Every line either has the word "lastname" or "surname" on each line telling you if that value will be the last name. If it were on the end of each line it wouldn't be an issue. The problem is it can be in the middle, also some names do not have a middle name.

We read in, capitalize, and sort by last name. We are to read in the phone numbers as strings or characters. We have learned, arrays (1 & 2D), link lists, structs, classes (barely, as a struct replacement), not vectors or stringstream

so: FName, MName (if there is one), LName, Phone#

I'm maybe needing a counter to see if there are 4 or 3 inputs per line to know if a middle name is needed or is there some kind of flag that lets me know when I have reached the end of each line?

Official instructions:
You are to write a program that will read in names and phone numbers, rearrange each person’s name, and create a sorted phone directory in a link list format. The list has been collected form different places, placed in a file where the names are not in some standard format. A person’s last name may appear last or it may appear first on the input. A label has been associated with each name to identify where the last name appears. Either “surname” or “lastname” appears just before a person’s last name. The other will be his first name followed by optionally middle initial or name. Capitalize the first letters in each part of the name. Below are examples of inputs. Input file: ‘NamesAndPhoneV2.txt’

Read in the names, and arrange them with the first name first, followed by his middle name or initial if it exist followed by the last name. You must use a link list for your data structure and the list must be a sorted list, sorted on the last name. You must insert a new name into the link list and maintain a sorted order link list. Print out the resulting names and phone directory.

Hint: Read input as ‘strings’ even the phone number. Look for ‘\n’ for the end of line character if reading one char at a time, or optionally if the last string you read had a digit in it (ie looking for a digit might be the better way).

lastname Taylor marie denise 939-1512
james wilis surname thomas 261-8342
Stone Rock lastname Brown 544-2372
surname lea lee high 266-8324
stephens lastname reynolds 696-9231
lastname jam Dirdy toe 555-2391
lastname Russell mack 123-1234
surname Lewis Michelle Tee 828-2148
john mark surname marshall 888-2891
lastname Moto hasey 823-8000
o e lastname vey 177-1423
Twosee or surname knocktosee 823-8321
two B surname orknot 394-8425
Mack lastname Camp 284-9843
Cant never lastname kound 940-8324
surname finitee two N 724-8234
lastname ghigher Eve N 398-1453
Ttow surname jammer 924-5231
Uh nuther lastname won 432-4345
surname Lotts lue Knew 743-4594
knot zo lastname much  824-3943
lastname Macperlly sherrly swirly 243-3453
Ah C lastname moto 849-3324
surname much too 883-2923
lastname done Jjust abot 463-9002
Al Dah surname zame 632-7432
lastname auf Tu Phinish 382-8324

Needs to look like:

Marie Denise Taylor 939-1512
James Willis Thomas 261-8342
etc...

string temp;
string first;
string middle;
string last;

while(infile>>temp)
{
  if(temp=="lastname")
    {
       infile>>last;
       //don't know what the next would be cause sometimes
    ]  //its last, first, middle
       //sometimes it is just first, middle, then last 

   if(temp=="surname")
    {
      infile>>last;
      //same problem here 
    }
}

Thank you for taking the time to read this and be patient with me as I am still very new and learning (struggling...)

[jonnin]

existing linked lists can be sorted nicely using the mergesort idea. you can basically find the midpoint of your list and break it into 2 lists, recursively doing this.

they can also be sorted easily in N*N type by 'insert in order' concept where you find where a record goes and put it there (in sorted order) on every insert.

as far as breaking the data up, you have to find a way to do that using the clues in the file.
there are various ways you can do it... read one big string and break it up with keywords or read one by one and taking actions when you find keywords... give it a try.
you have to figure out which name it is and put it in the right field of your struct's data.

I can't make much sense of your data, so I would probably just do FCFS ... find the lastname/surname and then take the rest in order, first one is first name, second one is middle. If you get more than 3, you decide... flag as an error, discard extra, shove extra into an extra unknown field...
sigh, we have to peel off prefix an suffix ... so Dr james t kirk MD III kind of thing but we know its prefix/first/middle/last/suffixes and prefix/suffix are all from a known list. Not that it matters, just saying, this is a practical real world problem. When we standardize, we put extra/unknown/garbage in a field, where it is not totally gone but its removed from the cleaned up output. Its effectively thrown away/hidden but internal processes can match against it if they want to.

[Niccolo]

The data I see suggests that "surname" and "lastname" have about the same meaning, which is to say the next "word" in order is the last name.

Any other words that appear are, it seems, in order first and optionally a middle name.

There are too many ways to do this to offer an algorithm for you, that's part of your assignment (to figure it out).

Some posters here have the habit of providing a full demonstration, but I'm not one of them.

However, I do offer some thoughts which may help you figure this out.

First, it appears you can't rely upon the number of fields of input. If the pattern holds with certainty, you could check to see if the content is numeric (perhaps just check if the first character is a digit). If so, it appears that is always the phone number, and the last field of a line.

So, if you continue reading in by words, as it appears you're doing, you might have to contend with the possibility that "lastname" could be capitalized, which would imply calling a "tolower" function to be sure (you could skip that if you know they'll never be capitalized).

That said, the "if" clauses you show above treat "lastname" and "firstname" the same way, which is to say the logic could be "if lastname or surname", take the next word as the last name.

ELSE...use else such that whever you read a word (remember the phone number test above), you're reading first name or middle name. If the name were a last name, one of the "markers" (lastname or surname) would have already taken that.

Perhaps you'll use a "flag". Set this to false for every new line (which is to say start it out as false, and set it BACK to false when you load a phone number). If you read a name that is not a last name, it is a first name when this flag is false. Set the first name, then set the flag to true. If you read another name, its the middle name. If there isn't one, leave that "empty" - the next word read would be the phone number, which ends the line and resets the flag for the next loop.

So, you read in a loop one word at a time. Note the "lastname" marker, taking the last name, otherwise take in the first name and set the flag.

So, no doubt you just wondered, "what loop". Well, you have a variable number of entries to read. This should be a loop which determines what is being read, word after word, where the loop is terminated when you read a phone number.

That's the loop.

It also responds to the variable number of words, using the flag to switch between first and middle name, the marker to read a last name, and the check for a digit to read a phone and end the line.

[XboxOne2019]

I almost have the program done. Its due by tomorrow night. My last thing I have to do is bubble sort the nodes. I've tried viewing some things online to see how to implement them since we didn't learn bubble sorting with linked lists, only arrays and structs. I did the structs one wrong before because I used array [].

Everything works so far to add the names in the nodes and print them out. We used a sample handout the teacher gave us to help in writing it all except the sort. I like writing complete words out and being very easy if possible. I just cant figure out the sort. I did a struct sort, but it was different.

I need to swap by last names and make the other info swap at the same time

class recordList  //the class to hold the records 
{
 public:
     string LName;
     string MName;   
     string FName;
     string phone_num;
     recordList * linky;  
};   

typedef recordList * Node;     
Node ListHead;		

  recordList * newNode()      //Function to create a new node 
  {    recordList * temp;
       temp = new recordList();   
       temp->FName = " ";
       temp->MName = " ";
       temp->LName = " ";
       temp->phone_num = " ";
       temp->linky = NULL;
       return temp;
   }

 void insert( string w, string x, string y, string z)  //inserting all the values into the nodes.
    {   
      Node current, previous, next;
        if (ListHead == NULL)  //if empty 
        {                                                     
           ListHead = newNode();
           ListHead->FName = w;
           ListHead->MName = x;
           ListHead->LName = y;
           ListHead->phone_num = z;
           ListHead->linky = NULL;  /* not needed */
        }
        else
           {  
              current = ListHead ;
              while (current != NULL)            
              {  
                  previous = current;
                  current = current->linky;     
              }
              next = newNode();
              next->FName = w;
              next->MName = x;
              next->LName = y;
              next->phone_num = z;
              previous->linky = next;
           };
    };
    
    void sort()  //function to bubble sort by last name 
    {  //I don't fully understand all this 
        int i;
        Node current=ListHead;  //the head 
        Node next;
        
      for(i=0;i<27;i++)  //there are 27 names 
      {
        while(current!=NULL)  //while not empty 
        {
            
            if(current->LName>next->LName)
            {
                current->LName=next->LName;
                next->LName=current->LName;  //swap them 
               
                
            }
        }
        
    }
    }
    void printList()  //printing the nodes, works great 
    {  
        Node current;
        current = ListHead;
        while ( current )
        {   
            cout<<current->FName<<" "<<current->MName<<" "<<current->LName<<" "<<current->phone_num<<endl; 
            current = current->linky;
        }
    }