Create Bubble Sort Function For Linked List

[fallnwrld]

That's my entired code to rand up several numbers, now I need a bubble sort to organize the list... the trick is I cant use NO arrays... Hmmm... any help?

[CornedBee]

off topic: since you're already using C++, why don't you put that into a class?

[fallnwrld]

I'm new to C++, I'm having complications with this as it is, to put it in class would just make it more trouble some for me.

I understand the concept. It's like an array... you can remove and add elements using the function i can see that... and if used the ++ command instead of skipping to the next integer number in an array type situation it skips every 4 bytes being that an interger is 4 bytes so I know how to navigate through the code, I just can't come up with it functioning and i've trade for 4 days. This bothers me, and was hoping someone on here can help. Thanks.

[kedaman]

you could use the list in STL

#include <list>
using namespace std;

...

list<int> mylist;

...

mylist.sort(); 

btw if you're new to C++ then you should learn the basics first, check out the Faq for tutorials.

[fallnwrld]

I am required to create a bubbleSort Function
::Sighs:: VB is so much more fun!

i get a error for if (pList => pList + 1){..... I want to see if the variable in pList is greater then or equal too the next number on the list then put higher one in a temp file, then put lower one in its place, then put the number in the temp file into where the lower number is.

void bubbleSort(const LinkedList *const pList){
if (pList != NULL){
Node *pTemp = pList->pHead;
if (pList => pList + 1){



}


}

[fallnwrld]

I also want to be VB programmer. Yet my degree requires me to take this c++ class. The class is once a week and was kind of tough for him to go over pointers in one day. Now take home assignments are 50% of grade... i need to get a C or higher in this class or im screwed.

[fallnwrld]

What I'm trying to do is put first number in list in pTemp1 and second number in list in pTemp2... then compare and switch.. i get 3 compile errors with this code

C:\LinkedList\LinkList.cpp(131) : error C2166: l-value specifies const object
C:\LinkedList\LinkList.cpp(133) : error C2059: syntax error : '>'
C:\LinkedList\LinkList.cpp(133) : error C2143: syntax error : missing ';' before '{'
Error executing cl.exe.
If you know the problem, help me out....

LinkList.obj - 3 error(s), 0 warning(s)


void bubbleSort(const LinkedList *const pList){
if (pList != NULL){
Node *pTemp1 = pList->pHead;
Node *pTemp2 = pList->pHead++;

if (pTemp1 => pTemp2 + 1){


}
}


}

[fallnwrld]

fixed one of errors

void bubbleSort(const LinkedList *const pList){
if (pList != NULL){
Node *pTemp1 = pList->pHead;
Node *pTemp2 = pTemp1->pNext;

if (pTemp1 => pTemp2 + 1){


}
}


}

[fallnwrld]

-> is the same as => correct?

if (pTemp1 -> pTemp2 + 1){

and i get this error C:\LinkedList\LinkList.cpp(133) : error C2039: 'pTemp2' : is not a member of 'Node'

i see why its giving me that error, but how are they able to write give pTemp2..NEVERMIND they can because they are making it NULL and i'm trying to assign it a value...

[kedaman]

-> is dereferencing your pointer and selecting the member
A->B
is the same as
(*A).B
if B is not a member of A then it gives you that error, brb

[kedaman]

if (pTemp1 -> pTemp2 + 1){

means that

if pTemp2 member of pTemp1 is not -1

since if expects a boolean and the aritmetical 0 is false, otherways true.

bubblesort iterates the list and switches the next element with the current if it is larger (or smaller), this continues until no switches are performed.

sorry, if you put your code within code tags and indent, i might also have look at it.

[fallnwrld]

..

[fallnwrld]

void bubbleSort(const LinkedList *const pList){
    if (pList != NULL){
      Node *pTemp1 = pList->pHead;     
      Node *pTemp2 = NULL;
      pTemp2 = pTemp1->pNext;
      int Temp3 = 0;    
          if (pTemp1 -> pTemp2 + 1){ 
            pTemp3 = pTemp1;
            pTemp1 = pTemp2 + 1;
            pTemp2 = pTemp3;
    
          }
    }


} 

[fallnwrld]

For those who are helping I keep changing the bubbleSort function instead of creating a reply to save load time when trying to help me.

#include <iostream> 

using std::cout; 
using std::endl; 

#include <assert.h> 
#include <ctime> 

//LIST NODE 
struct Node
{ 
    int data; 
    Node *pNext; 
}; 

//SINGLY LINKED LIST STRUCTURE 
struct LinkedList
{ 
    Node *pHead; 
    int size; 
}; 

//RETURNS A NEW LINKED LIST 
// 
// Returns 
// Returns a pointer to an empty linked list 
LinkedList *createLinkedList(); 


// INSERTS A NEW NODE AT THE HEAD OF THE LINKED LIST 
// 
// Input parameters: 
// pList pointer to the linked list to receive the new element 
// element data value to be assigned to the new node 
void insertAtHead(LinkedList *const pList, const int element); 


// PRINTS DATA VALUES OF A LINKED LIST TO THE SCREEN 
// 
// Example output: 
// 12 34 56 69 24 2 15 
// 
// Input Parameters: 
// pList pointer to the linked list to be printed 
void print(const LinkedList *const pList); 

void bubbleSort(const LinkedList *const pList);
// REMOVES THE LINKED LIST FROM MEMORY 
// 
// Input Parameters: 
// pList pointer to the linked list to be removed 
void destroy(LinkedList *pList); 


// DRIVER 
int main(){ 
//Create linked list 
LinkedList *pList = createLinkedList(); 
int size = 10; 

srand(time(0)); 

//Insert elements onto list 
int value, i; 
for(i=0;i<size;i++)
{ 
     value = rand()%100; 
     cout << value << " "; 

     insertAtHead(pList, value); 
} 
cout << endl; 

print(pList); 

//IMPLEMENT BUBBLE SORT 
bubbleSort(pList); 

print(pList); 

//clean up 
destroy(pList); 
pList = NULL; 

return 0; 
} 


//RETURNS A NEW LINKED LIST 
LinkedList *createLinkedList(){ 
LinkedList *pList = new LinkedList; // allocated memory 
assert(pList); // test for memory error 

//initalize list members 
pList->pHead = NULL; 
pList->size = 0; 

return pList; 
} 


// INSERTS A NEW NODE AT THE HEAD OF THE LINKED LIST 
void insertAtHead(LinkedList *const pList, const int element)
{ 
     if(pList != NULL) // test pointer is non-null 
     {     
          Node *pNode = new Node; // allocate memory 
          assert(pNode); // test for memory error 

          //initalize node members 
          pNode->data = element; 
          pNode->pNext = pList->pHead; 

          pList->pHead = pNode; // insert at head of list 
          pList->size++; 
     } 
} 


// PRINTS DATA VALUES OF A LINKED LIST TO THE SCREEN 
void print(const LinkedList *const pList)
{ 
     if(pList != NULL)
     { 
          Node *pTemp = pList->pHead; 
          while(pTemp != NULL)
          { 
               cout << pTemp->data << " "; 
               pTemp = pTemp->pNext; 
          } 
      cout << endl; 
     } 
} 


void bubbleSort(const LinkedList *const pList)
{
    if (pList != NULL)
    {
      Node *pTemp1 = pList->pHead;     
      Node *pTemp2 = pTemp1->pNext;
      Node *pTemp3 = NULL;
      int intCounter = 0;          
          
          while (intCounter <= 30)
          {
               if (pTemp1 -> pTemp2 + 1)
               { 
                   pTemp3 = pTemp1;
                   pTemp1 = pTemp2 + 1;
                   pTemp2 + 1 = pTemp3;
               }
          intCounter++;
          }
    }


}

// REMOVES THE LINKED LIST FROM MEMORY 
void destroy(LinkedList *pList)
{ 
     if(pList != NULL)
     { 
          Node *pTemp1 = pList->pHead; 
          Node *pTemp2 = NULL; 

          // Remove nodes from memory starting from the head of the list 
          while(pTemp1 != NULL) // test for non-null 
          {
              pTemp2 = pTemp1->pNext; 
              delete(pTemp1); // deallocate memory 
              pTemp1 = pTemp2; 
          } 

      // Remove list from memory 
      delete(pList); 
     } 
} 

[fallnwrld]

got it down to two errors

Compiling...
LinkList.cpp
C:\LinkedList\LinkList.cpp(144) : error C2039: 'pTemp2' : is not a member of 'Node'
C:\LinkedList\LinkList.cpp(11) : see declaration of 'Node'
C:\LinkedList\LinkList.cpp(148) : error C2106: '=' : left operand must be l-value
Error executing cl.exe.


im thinking I don't have to have a pNext if I have pTemp2 + 1;

see what I mean? Both where design to do the same thing if anything its going to skip to the 3rd one.

[kedaman]

void bubbleSort(const LinkedList *const pList){
    if (pList != NULL){
        bool f;
        do{
            f=false;
            Node *pTemp1 = pList->pHead;     
            Node *pTemp2 = pTemp1->pNext;
            if (pTemp1->data < pTemp2->data){
                pList->pHead = pTemp2;
                pTemp1->pNext=pTemp2->pNext;
                pTemp2->pNext =pTemp1;
                }
            Node *pTemp3 = pTemp1;
            while (pTemp2->pNext){
                pTemp2=pTemp2->pNext;
                pTemp1=pTemp1->pNext;
                if (pTemp1<pTemp2){
                    pTemp3->pNext = pTemp2;
                    pTemp1->pNext = pTemp2->pNext;
                    pTemp2->pNext =pTemp1;
                    f=true;
                    }
                pTemp3=pTemp3->pNext;
                }
            }while(f);
        }
    } 

There you go, I haven't tested it yet though, have fun

[CornedBee]

doesn't he want to test the values behind the pointers, not the pointers themselves?
if (*pTemp1 < *pTemp2){

[kedaman]

Originally posted by CornedBee
doesn't he want to test the values behind the pointers, not the pointers themselves?
if (*pTemp1 < *pTemp2){

actually the member data of of the dereferenced value (in node)

[fallnwrld]

Got this error, I'm sure I'll figure it out though. Thanks for all your help!
Compiling...
LinkList.cpp
C:\LinkedList\LinkList.cpp(148) : error C2166: l-value specifies const object
Error executing cl.exe.

[kedaman]

which line is that?

[fallnwrld]

pList -> pHead = pTemp2; (Marked in code)

JUST THE FUNCTION, FULL CODE BELOW
_________________________________________

void bubbleSort(const LinkedList *const pList)
{
    if (pList != NULL)
    {
        bool f;
        do
        {
            f=false;
            Node *pTemp1 = pList -> pHead;     
            Node *pTemp2 = pTemp1 -> pNext;
            if (pTemp1 -> data < pTemp2->data)
            {
                pList -> pHead = pTemp2; //I am line 148
                pTemp1 -> pNext = pTemp2 -> pNext;
                pTemp2 -> pNext = pTemp1;
            }
            Node *pTemp3 = pTemp1;
            while (pTemp2 -> pNext)
            {
                pTemp2 = pTemp2 -> pNext;
                pTemp1= pTemp1 -> pNext;
                if (pTemp1 < pTemp2)
                {
                    pTemp3 -> pNext = pTemp2;
                    pTemp1 -> pNext = pTemp2 -> pNext;
                    pTemp2 -> pNext = pTemp1;
                    f=true;
                }
             pTemp3=pTemp3->pNext;
             }
        }while(f);
    }  
} 

ALL THE CODE
______________________________________________

#include <iostream> 

using std::cout; 
using std::endl; 

#include <assert.h> 
#include <ctime> 

//LIST NODE 
struct Node
{ 
    int data; 
    Node *pNext; 
}; 

//SINGLY LINKED LIST STRUCTURE 
struct LinkedList
{ 
    Node *pHead; 
    int size; 
}; 

//RETURNS A NEW LINKED LIST 
// 
// Returns 
// Returns a pointer to an empty linked list 
LinkedList *createLinkedList(); 


// INSERTS A NEW NODE AT THE HEAD OF THE LINKED LIST 
// 
// Input parameters: 
// pList pointer to the linked list to receive the new element 
// element data value to be assigned to the new node 
void insertAtHead(LinkedList *const pList, const int element); 


// PRINTS DATA VALUES OF A LINKED LIST TO THE SCREEN 
// 
// Example output: 
// 12 34 56 69 24 2 15 
// 
// Input Parameters: 
// pList pointer to the linked list to be printed 
void print(const LinkedList *const pList); 

void bubbleSort(const LinkedList *const pList);
// REMOVES THE LINKED LIST FROM MEMORY 
// 
// Input Parameters: 
// pList pointer to the linked list to be removed 
void destroy(LinkedList *pList); 


// DRIVER 
int main(){ 
//Create linked list 
LinkedList *pList = createLinkedList(); 
int size = 10; 

srand(time(0)); 

//Insert elements onto list 
int value, i; 
for(i=0;i<size;i++)
{ 
     value = rand()%100; 
     cout << value << " "; 

     insertAtHead(pList, value); 
} 
cout << endl; 

print(pList); 

//IMPLEMENT BUBBLE SORT 
bubbleSort(pList); 

print(pList); 

//clean up 
destroy(pList); 
pList = NULL; 

return 0; 
} 


//RETURNS A NEW LINKED LIST 
LinkedList *createLinkedList(){ 
LinkedList *pList = new LinkedList; // allocated memory 
assert(pList); // test for memory error 

//initalize list members 
pList->pHead = NULL; 
pList->size = 0; 

return pList; 
} 


// INSERTS A NEW NODE AT THE HEAD OF THE LINKED LIST 
void insertAtHead(LinkedList *const pList, const int element)
{ 
     if(pList != NULL) // test pointer is non-null 
     {     
          Node *pNode = new Node; // allocate memory 
          assert(pNode); // test for memory error 

          //initalize node members 
          pNode->data = element; 
          pNode->pNext = pList->pHead; 

          pList->pHead = pNode; // insert at head of list 
          pList->size++; 
     } 
} 


// PRINTS DATA VALUES OF A LINKED LIST TO THE SCREEN 
void print(const LinkedList *const pList)
{ 
     if(pList != NULL)
     { 
          Node *pTemp = pList->pHead; 
          while(pTemp != NULL)
          { 
               cout << pTemp->data << " "; 
               pTemp = pTemp->pNext; 
          } 
      cout << endl; 
     } 
} 


void bubbleSort(const LinkedList *const pList)
{
    if (pList != NULL)
    {
        bool f;
        do
        {
            f=false;
            Node *pTemp1 = pList -> pHead;     
            Node *pTemp2 = pTemp1 -> pNext;
            if (pTemp1 -> data < pTemp2->data)
            {
                pList -> pHead = pTemp2; //I am line 148
                pTemp1 -> pNext = pTemp2 -> pNext;
                pTemp2 -> pNext = pTemp1;
            }
            Node *pTemp3 = pTemp1;
            while (pTemp2 -> pNext)
            {
                pTemp2 = pTemp2 -> pNext;
                pTemp1= pTemp1 -> pNext;
                if (pTemp1 < pTemp2)
                {
                    pTemp3 -> pNext = pTemp2;
                    pTemp1 -> pNext = pTemp2 -> pNext;
                    pTemp2 -> pNext = pTemp1;
                    f=true;
                }
             pTemp3=pTemp3->pNext;
             }
        }while(f);
    }  
}


// REMOVES THE LINKED LIST FROM MEMORY 
void destroy(LinkedList *pList)
{ 
     if(pList != NULL)
     { 
          Node *pTemp1 = pList->pHead; 
          Node *pTemp2 = NULL; 

          // Remove nodes from memory starting from the head of the list 
          while(pTemp1 != NULL) // test for non-null 
          {
              pTemp2 = pTemp1->pNext; 
              delete(pTemp1); // deallocate memory 
              pTemp1 = pTemp2; 
          } 

      // Remove list from memory 
      delete(pList); 
     } 
} 

[kedaman]

remove the const before LinkedList*const, dereferencing that pointer will still leave the Linkedlist immutable (thats why you can't assign a member)

[fallnwrld]

I moved it out of the function, and I moved it out of the prototype for the function. It compiles! lol, thanks a lot for your help. It doesn't sort the list though for some reason. I'm tinkering with the algor. now, and it's helping me learn. If it's something you can spot off back let me know, I appreciate it.

[kedaman]

         if (pTemp1 -> data < pTemp2->data)
            {
                pList -> pHead = pTemp2; //I am line 148
                pTemp1 -> pNext = pTemp2 -> pNext;
                pTemp2 -> pNext = pTemp1;
            }
            Node *pTemp3 = pTemp1;
            while (pTemp2 -> pNext)
            {
                pTemp2 = pTemp2 -> pNext;
                pTemp1= pTemp1 -> pNext;
                if (pTemp1 < pTemp2)
*snip*

That last line should be as the abovemost (note how terrifying this design model is when you need to locate the mistyped bug)

[fallnwrld]

Not sure what you meant by that. From the snippet you show me the only difference in code I saw was indentation. That shouldn't matter because the {} tell you when that statement starts or ends. I kept looking at code, and then you said last line must be top most... the last line in snippet you showed me was the if statement, so maye you where saying that if statement should come first.... that didn't help as well. Hopefully Bork will be a little easier to understand ;oP lol. Don't give up on me yet, I will get this!

[kedaman]

BORK will definitely be easier to get the hang of

I meant that you need to dereference and get the member data, becase whats the point in comparing two pointers, it even differs each time you run it!

replace

if (pTemp1 < pTemp2)

with

if (pTemp1 -> data < pTemp2->data)

[fallnwrld]

Yeah I actually tried that... this is function... (OFF TOPIC: is Bork going to be a visual language such as VB?) None of the numbers are being sorted, not even partially. ;o\

void bubbleSort(LinkedList *const pList)
{
    if (pList != NULL) // if Null skip bubbleSort 
    {
        bool f; //Create boolean to exit while loop
        do
        {
            f=false; //set boolean value to false
            Node *pTemp1 = pList -> pHead;     
            Node *pTemp2 = pTemp1 -> pNext;
            if ( pTemp1 -> data < pTemp2 -> data ) //if < then enter if statement
            {
                pList -> pHead = pTemp2; 
                pTemp1 -> pNext = pTemp2 -> pNext;
                pTemp2 -> pNext = pTemp1;
            }
            Node *pTemp3 = pTemp1;
            while ( pTemp2 -> pNext)
            {
                pTemp2 = pTemp2 -> pNext;
                pTemp1 = pTemp1 -> pNext;
                if ( pTemp1 -> data < pTemp2 -> data )
                {
                    pTemp3 -> pNext = pTemp2;
                    pTemp1 -> pNext = pTemp2 -> pNext;
                    pTemp2 -> pNext = pTemp1;
                    f = true; //to exit while loop
                }
             pTemp3 = pTemp3 -> pNext;
             }
        }while(f);
    }  
} 

[kedaman]

What a nice idea Bork could actually take streamed data directly from an IDE, which would allow designing visual concepts a lot easier.

btw, put "f = true;" in the first if with the head, it's probably why it's not sorting, in case it finds the first then it might just exit the whole thing

[fallnwrld]

I put f=true; up and down that bad boy, no luck what so ever. ;o\


I try to put debug statements to print when it reaches a statement... It appears to be stuck in a endless loop somewhere.

It says
Gets to first while statement
Gets to first while statement
Gets to 2nd if statement
KEEPS DOING THAT OVER AND OVER!

void bubbleSort(LinkedList *const pList)
{
    if (pList != NULL) // if Null skip bubbleSort 
    {
        cout << "its not null" << endl;
        bool f; //Create boolean to exit while loop
        do
        {
            cout << "gets to the do statement." << endl;
            f=false; //set boolean value to false
            Node *pTemp1 = pList -> pHead;     
            Node *pTemp2 = pTemp1 -> pNext;
            if ( pTemp1 -> data < pTemp2 -> data ) //if < then enter if statement
            {
                cout << "gets to 1st if statement" << endl;
                pList -> pHead = pTemp2; 
                pTemp1 -> pNext = pTemp2 -> pNext;
                pTemp2 -> pNext = pTemp1;
            }
            Node *pTemp3 = pTemp1;
            while ( pTemp2 -> pNext)
            {
                cout << "gets to 1st while statement." << endl;
                pTemp2 = pTemp2 -> pNext;
                pTemp1 = pTemp1 -> pNext;
                if ( pTemp1 -> data < pTemp2 -> data )
                {
                    cout << "gets to 2nd if statement." << endl;
                    pTemp3 -> pNext = pTemp2;
                    pTemp1 -> pNext = pTemp2 -> pNext;
                    pTemp2 -> pNext = pTemp1;
                    f = true; //to exit while loop
                }
             pTemp3 = pTemp3 -> pNext;
             }
        }while(f);
    }  
} 

[CornedBee]

It just might be that the list is not correctly intialized, that it does not end with a NULL pNext pointer?
You could also output the pointer values (the addresses they point to) to find this out. If the same pointer value comes out over and over you have a problem.
Have you tried to live debug it?