Linked List Bubble Sort

sparky (54)
Hello,

I am trying without success to sort last names stored in a single linked list alphabetically, using the bubble sort method and strcmp() function.

Any guidance will be much appreciated.

Here is the sort code snippet: 

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

for ( int i = 1; i < numberOfNodes; i++ ) 
{ 
    for ( int index = 0; index < numberOfNodes - i; index++ ) 
    { 

     // if last name in first node is greater than last name in second node 
     // swap the positions of the nodes 
     if ( strcmp ( newNode -> lName, newNode -> next -> lName ) == 1 )    
     { 
          
         temp1 = newNode; 
         newNode = newNode -> next; 
         newNode -> next = temp1; 
          
     }// end if 
              
    }// end for 
    
}// end for



And here is the entire code:


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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
// preprocessor directives 
# include <iostream> 
# include <string> 

using namespace std; 

// class nodeType 
class nodeType 
{ 
// class members  
public: 
         char fName[ 15 ]; 
         char lName[ 15 ];    
         nodeType *next; 
      
}; 

// main 
int main() 
{ 
   // declare pointers of type nodeType 
   nodeType *head, *first, *newNode, *last, *temp1, *temp2; 
    
    // set pointers to 0 
    head = NULL; 
    first = NULL; 
    newNode = NULL; 
    last = NULL; 
    temp1 = NULL; 
    temp2 = NULL; 
    
     char fn[ 15 ]; 
    int numberOfNodes = 0; 
    
    //============Input Names=========================== 
    
    cout << "Enter first name: "; 
    cin >> fn; 
    
    
    // loop for 3 times 
    for ( int a = 0; a < 3; a++ ) 
    { 
    // create new node 
    newNode = new nodeType; 
    
    // store first name in node 
    for ( int i = 0; i < 15; i++ ) 
        newNode -> fName[ i ] = fn[ i ]; 
    
    // count number of nodes in list              
    numberOfNodes++; 
    
    // input last name 
    cout << "Enter last name: "; 
    cin >> newNode -> lName; 
    
    // set end of node to 0 
    newNode -> next = NULL; 
    
   // if node is empty set pointers to 0 
     if ( first == NULL ) 
    { 
     head = newNode; 
     first = newNode;  
     last = newNode;  
          
    } 
    else 
    { 
     last -> next = newNode; 
     last = newNode;    
    } 
    
    
     cout << "Enter first name: "; 
     cin >> fn; 
      
      
    
} // end while    


//=================Print unsorted list======================== 



cout << endl << endl << "Unsorted" << endl << endl; 

newNode = head; 

while ( newNode != NULL ) 
{ 
cout << newNode -> fName << " " << newNode -> lName << endl; 
newNode = newNode -> next; 
} 



//==================Print sorted list============================ 



cout << endl << endl << "Sorted" << endl << endl; 

newNode = head; 

for ( int i = 1; i < numberOfNodes; i++ ) 
{ 
    for ( int index = 0; index < numberOfNodes - i; index++ ) 
    { 
     if ( strcmp ( newNode -> lName, newNode -> next -> lName ) == 1 ) 
    
     { 
          
         temp1 = newNode; 
         newNode = newNode -> next; 
         newNode -> next = temp1; 
          
     }// end if 
              
    }// end for 
    
}// end for 

newNode = head; 

while ( newNode != NULL ) 
{ 
      cout << newNode -> fName << " " << newNode -> lName << endl; 
      newNode = newNode -> next; 
            
      
}// end while 


    system ("pause"); 
}


satm2008 (148)
I am not sure to use the bubblesort in your assignmet, but I would not use any sort function when I create a linked list, if it needs to be listed in a sorted order.

Simple, when you store a node, keep it at right place, thats all.

In your code, you enter all first names first in a loop and enter the last names last, (no idea, if you are thinking, as their name say, to enter first names first and last names last, lol :))

For your example, I would do (if not told to use a sort function)

void main()
{
// all your declaration goes here


head = temp1 = temp2 = NULL;
do {

// prompt and input first name and last name

newNode = new NodeType;
strcpy(newNode->fname, fn) ;
strcpy(newNode->lname, ln);
newNode->next = NULL;

if (head == NULL) // list is empty
{
head = first = newNode;
}
else if (strcmp(newNode->lname, ln) < 0) // then insert before first one
{
newNode->next = head;
head = newNode;
}
else {
temp1 = head;
//start a search for right place, by checking the next one's last name
while ( strcmp(temp1->next->lname, ln) < 0) && temp10>next != NULL )
{
temp1 = temp1->next;
}

newNode->next = temp1->next;
temp1->next = newNode;
}

// here prompt for an input to enter more (ie, anyMore Y/N)
} while (anyMore == 'Y')


// now list the items
temp1 = head;

while ( temp1 != NULL )
{
cout << temp1->fname << temp1->lname << endl;
temp1 = temp1->next;
}


// all done;
}


Try it out. Good luck :)

satm2008 (148)
Sorry for the typo in:
else if (strcmp(newNode->lname, ln) < 0) // then insert before first one
{
newNode->next = head;
head = newNode;
}


it should be:
else if (strcmp(newNode->lname, head->lname) < 0) // then insert before first one
{
newNode->next = head;
head = newNode;
}

satm2008 (148)
Sorry for the typo in:
else if (strcmp(newNode->lname, ln) < 0) // then insert before first one
{
newNode->next = head;
head = newNode;
}


it should be:
else if (strcmp(newNode->lname, head->lname) < 0) // then insert before first one
{
newNode->next = head;
head = newNode;
}

closed account (z05DSL3A)
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
// bubbleSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"

// preprocessor directives 
# include <iostream> 
# include <string> 

using namespace std; 

// class nodeType 
class nodeType 
{ 
// class members  
public: 
         char fName[ 15 ]; 
         char lName[ 15 ];    
         nodeType *next;    
}; 

nodeType *bubblesort(nodeType *list);

// main 
int main() 
{ 
    // declare pointers of type nodeType 
    nodeType *head    = NULL;
    nodeType *first   = NULL;
    nodeType *newNode = NULL;
    nodeType *last    = NULL;
    nodeType *temp1   = NULL;
    nodeType *temp2   = NULL;
        
    char fn[15]; 
    int numberOfNodes = 0; 
    
    //============Input Names=========================== 
    
    // loop for 3 times 
    for ( int a = 0; a < 5; a++ ) 
    { 
        cout << "Enter first name: "; 
        cin >> fn; 
        
        // create new node 
        newNode = new nodeType; 
    
        // store first name in node 
        for ( int i = 0; i < 15; i++ ) 
            newNode -> fName[ i ] = fn[ i ]; 
    
        // count number of nodes in list              
        numberOfNodes++; 
    
        // input last name 
        cout << "Enter last name: "; 
        cin >> newNode -> lName; 
    
        // set end of node to 0 
        newNode -> next = NULL; 
    
        // if node is empty set pointers to 0 
        if ( first == NULL ) 
        { 
            head = newNode; 
            first = newNode;  
            last = newNode;        
        } 
        else 
        { 
            last -> next = newNode; 
            last = newNode;    
        } 

    } // end while    


    //=================Print unsorted list======================== 
    cout << endl << endl << "Unsorted" << endl << endl; 

    newNode = head; 

    while ( newNode != NULL ) 
    { 
        cout << newNode -> fName << " " << newNode -> lName << endl; 
        newNode = newNode -> next; 
    } 

    //==================Print sorted list============================ 
    cout << endl << endl << "Sorted" << endl << endl; 

    head = bubblesort(head);
    
    newNode = head; 

    while ( newNode != NULL ) 
    { 
        cout << newNode -> fName << " " << newNode -> lName << endl; 
        newNode = newNode -> next;   
    }// end while 

    system ("pause"); 
}

////////////////////////////////////////////////////////////////////////////

nodeType *bubblesort(nodeType *list)
{
    nodeType *lst, *tmp = list, *prev, *potentialprev = list;
    int idx, idx2, n = 0;
 
    //determine total number of nodes
    for (;tmp->next; tmp=tmp->next)
    {
        n++;
    }
 
    for (idx=0; idx<n-1; idx++) 
    {
        for (idx2=0,lst=list; lst && lst->next && (idx2<=n-1-idx); idx2++)
        {
            if (!idx2)
            {
                //we are at beginning, so treat start 
                //node as prev node
                prev = lst;
            }
 
            //compare the two neighbors
            if ( strcmp ( lst->lName, lst->next->lName ) == 1 ) 
            {  
                //swap the nodes
                tmp = (lst->next?lst->next->next:0);
 
                if (!idx2 && (prev == list))
                {
                    //we do not have any special sentinal nodes
                    //so change beginning of the list to point 
                    //to the smallest swapped node
                    list = lst->next;
                }
                potentialprev = lst->next;
                prev->next = lst->next;
                lst->next->next = lst;
                lst->next = tmp;
                prev = potentialprev;
            }
            else
            {
                lst = lst->next;
                if(idx2)
                {
                    //just keep track of previous node, 
                    //for swapping nodes this is required
                    prev = prev->next;
                }
            }     
        } 
    }
    return list;
}
sparky (54)
Hello satm2008
Thank you very much for your reply! I am totally new to linked lists and your reply was a great help.
I tried my best to incorporate your solution into the program and it works (sorts last names alphabetically). However, something I wrote (or left out) causes the program to stall sometimes. Still trying to figure it out.
Here is the new code and thanks again:

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
 
// preprocessor directives 
# include <iostream> 
# include <string> 

using namespace std; 

// class nodeType 
class nodeType 
{ 
// class members  
public: 
         char fName[ 15 ]; 
         char lName[ 15 ];    
         nodeType *next; 
      
}; 

int main()
{
// all your declaration goes here
nodeType *head, *first, *next, *newNode, *temp1, *temp2;
char fn[ 15 ];
char ln[ 15 ];
char anyMore;


head = first = next = newNode = temp1 = temp2 = NULL; 

do {
system ( "cls" );
// prompt and input first name and last name

cout << "\nEnter first name: ";
cin >> fn;

cout << "Enter last name: ";
cin >> ln;

newNode = new nodeType;

strcpy( newNode -> fName, fn );
strcpy( newNode -> lName, ln );

newNode -> next = NULL;

if ( head == NULL ) // list is empty
{
head = first = newNode;
}

else if ( strcmp( newNode -> lName, head -> lName ) < 0 ) // then insert before first one
{
newNode -> next = head;
head = newNode;
}
else 
{

temp1 = head;

//start a search for right place, by checking the next one's last name
while (( strcmp( temp1 -> next -> lName, ln ) < 0 ) && ( temp1 -> next != NULL ))
{

temp1 = temp1 -> next;

}

newNode -> next = temp1 -> next;
temp1 -> next = newNode;

}



// now list the items
temp1 = head;

while ( temp1 != NULL )
{

cout << temp1 -> fName << " " << temp1 -> lName << endl;
temp1 = temp1 -> next;

}

// here prompt for an input to enter more (ie, anyMore Y/N) 
cout << "\nEnter Y to input, or N to exit: ";
cin >> anyMore;

} while ( anyMore == 'Y' || anyMore == 'y' ); // end dowhile

system ( "pause" );

// all done;
}
sparky (54)
Hello Grey Wolf,
Thanks very much for your solution. It works!
I commented out the preprocessor directive: #include "stdafx.h" because I got the following error while using Dev C++: "stdafx.h: No such file or directory". Thanks again.
satm2008 (148)
The code looks fine, but as you say it stalls some times, does it stop responding or waiting for your keyboard input? Check it out.

When I posted the code first time, it was just a pseudo code and did not run it on my sytem.

However I took a cut&paste of your program with my suggested code, it works just find, not sure where it stalls as you said.

Can you tell the scenario where and when it stalls, so that I may be able to figure it out and correct it if any thing wrong.

Good luck :)
Topic archived. No new replies allowed.