Bubble sort a linked list

[XboxOne2019]

Hey guys, I have to finish this program by tonight and I have everything working except how to do a bubble sort on the linked list. Granted, I don't fully understand how I got it all working...I used a sample printout that the teacher gave us and modified it. I know how to bubble sort an array and a struct, but not a linked list.

We are supposed to read in a file that has a first name, sometimes a middle name, a last name, and phone number. We then have to sort the names by last name and printout. I just need to get the bubble sort working..

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 have no idea what I am doing.
        int i;
        Node current;
        Node temp;
        current = ListHead;
        Node next;
        
      //not sure if I need a for loop here? There are 27 names.
        while(current)  //while not empty 
        {
            
            if(current->LName>next->LName)
            {
                next->LName=current->LName;
                current->LName=next->LName;
                next->LName=current->LName;  //swap them 
               
                
                
            }
            //current=current->linky;  //idk why this is here, I saw
        }                              //the teacher had it on other parts
               
    }
    
    void printList() //prints the list 
    {  
        Node current;
        current = ListHead;
        while ( current )
        {   
            cout<<current->FName<<" "<<current->MName<<" "<<current->LName<<" "<<current->phone_num<<endl; 
            current = current->linky;
        }
    }

//output so far before being sorted 

Marie Denise Taylor 939-1512
James Wilis Thomas 261-8342
Stone Rock Brown 544-2372
Lee High Lea 266-8324
Stephens   Reynolds 696-9231
Dirdy Toe Jam 555-2391
Michelle Tee Lewis 828-2148
John Mark Marshall 888-2891
Hasey Bo Moto 823-8000
O E Vey 177-1423

[salem c]

> next->LName=current->LName; //swap them
You do know that to swap something, you need a temporary variable right?

You also need to swap all FOUR of your member variables (everything except your link pointer).

Though I rather suspect your tutor is looking for something which exchanges pointers rather than data.

Where in an array, you would do
swap(arr[i],arr[i+1]);

you would do
swap(current->linky,next->linky);

[XboxOne2019]

Can you possibly show me an example with linky? I did a bubble sort with structs and kinda copied that, but I know the logic is wrong.

 void sort()  //function to bubble sort by last name 
    {            //I have no idea what I am doing.
        Node current;
        Node temp;  //does this need to point to something? 
        current = ListHead;  //start at the beginning 
        Node next;  //do I set this to a specific? 
        
     
        while(current)  //while not empty 
        {
            
            
            if(current->LName>next->LName)
            {
               
                temp->LName=current->LName;
                temp->FName=current->FName;
                temp->MName=current->LName;
                temp->phone_num=current->phone_num;
                current->LName=next->LName;
                current->FName=next->FName;
                current->MName=next->MName;
                current->phone_num=next->phone_num;
                next->LName=temp->LName;
                next->FName=temp->FName;
                next->MName=temp->MName;
                next->phone_num=temp->phone_num;
               
            }
            
        }                            
               
    }

[XboxOne2019]

For anyone that needs help, I figured it out. I hadn't learned enough about linked lists.

    void sort()  //function to bubble sort by last name 
    {            //I have no idea what I am doing.
        Node current, bcurrent;
        current=ListHead;
        bcurrent=ListHead->linky;
        
        
        for(int i=0;i<27-1;i++)
        {
            current=ListHead;
            bcurrent=ListHead->linky;
            for(int j=0;j<27-1;j++)
            {
                if(current->LName>bcurrent->LName)
                {
                   swap(current->LName, bcurrent->LName);
                   swap(current->FName, bcurrent->FName);
                   swap(current->MName, bcurrent->MName);
                   swap(current->phone_num, bcurrent->phone_num);
                }
             current=bcurrent;
             bcurrent=bcurrent->linky; 
            } 
               
       }
   }

Tu Phinish Auf 382-8324
Stone Rock Brown 544-2372
Mack   Camp 284-9843
Jjust Abot Done 463-9002
Two N Finitee 724-8234
Eve N Ghigher 398-1453
Dirdy Toe Jam 555-2391
Ttow   Jammer 924-5231
Twosee Or Knocktosee 823-8321
Cant Never Kound 940-8324
Lee High Lea 266-8324
Michelle Tee Lewis 828-2148
Lue Knew Lotts 743-4594
Sherrly Swirly Macperlly 243-3453
John Mark Marshall 888-2891
Hasey Bo Moto 823-8000
Ah C Moto 849-3324
Knot Zo Much 824-3943
Too Bo Much 883-2923
Two B Orknot 394-8425
Stephens   Reynolds 696-9231
Mack Bo Russell 123-1234
Marie Denise Taylor 939-1512
James Wilis Thomas 261-8342
O E Vey 177-1423
Uh Nuther Won 432-4345
Al Dah Zame 632-7432

[dhayden]

Why do you insert at the end of the list? It's horribly inefficient. Insert at the head of the list.

I suspect they want you to swap pointers. Here is a program that creates a list of integers and sorts them via bubble sort.

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node *next;
};

Node *head = NULL;

void printList()
{
    for (Node *p=head; p; p=p->next) {
	cout << p->data << ' ';
    }
    cout << '\n';
}


void sortList()
{
    Node *cur, *next, *prev;
    bool swapped;

    // Keep making passes through the list until you swap nothing.
    do {
	swapped = false;
	prev = NULL;
	for (cur = head; cur && cur->next; prev = cur, cur = cur->next) {
	    next = cur->next;
	    if (cur->data > next->data) {
		if (prev) prev->next = next;
		else head = next;
		cur->next = next->next;
		next->next = cur;
		swapped = true;
	    }
	}
    } while (swapped);
}


int
main()
{
    int i;
    while (cin >> i) {
	Node *p = new Node;
	p->data = i;
	p->next = head;
	head = p;
    }
    printList();
    sortList();
    printList();
    return 0;
}