C++ Bubblesort using linked list and pointers

[nekoleon64]

//Bubble.h
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

struct nodeType
{
  int info;
  nodeType *link;
};

class Bubble
{
  public:
  Bubble(); //constructor
  //deconstructor
  //copy constructor
  //operator= (overloading the = operator)
  friend istream & operator>> (istream &infile, Bubble & mylist);
  friend ostream & operator<< (ostream &outfile, const Bubble & alist);
  int size()const;
  void bubblesort();   
  private:
  nodeType *head_ptr;
  int manynodes;
};

[nekoleon64]

I'm Leonard E. Norwood Jr. And I'm still doing Bubblesort, but this time I haven't specifially explained that I'm doing it not only using pointers but linked list as well. to those who helped me out so far. I apologize for that. Anyway I'm putting up my codes again one post at a time. I've already fixed the program so far so that still leaves one thing. the bubblesort code itself modified with pointers and linked list on that as well.

[nekoleon64]

//Bubble.cpp
#include <iostream>
#include <cstdlib>
#include <cassert>
using namespace std;

#include "Bubble.h"

Bubble::Bubble()
{
    head_ptr = NULL;
    manynodes = 0;
}

void list_clear(nodeType*& head_ptr)
{
    nodeType* removeptr;
    while (head_ptr != NULL)
    {
        removeptr = head_ptr;
        head_ptr = head_ptr->link;
        delete removeptr;
    }
}

void list_copy(const nodeType* source_ptr, nodeType* &head_ptr, nodeType* &tail_ptr)
{
    nodeType* temp;
    head_ptr = NULL;
    tail_ptr = NULL;

    if(source_ptr == NULL)
    return;

    head_ptr = new nodeType;
    head_ptr->link = NULL;
    head_ptr->info = source_ptr->info;
    tail_ptr = head_ptr;

    source_ptr = source_ptr->link;

    while(source_ptr != NULL)
    {
        temp = new nodeType;
        temp->link = NULL;
        temp->info = source_ptr->info;
        tail_ptr->link = temp;
        tail_ptr = tail_ptr->link;
        source_ptr = source_ptr->link;
    }
}

int Bubble::size() const
{
    return manynodes;
}

istream& operator>>(istream& infile, Bubble &mylist)
{
    cout <<"Unsorted: " << '\n';

    int buf;

    while((infile >> buf))
    {
         cout << buf << " ";
         nodeType *newNode = new nodeType;
         newNode->info = buf;
         newNode->link = mylist.head_ptr;
         mylist.head_ptr= newNode;
         mylist.manynodes++;
    }

    return infile;
}

ostream& operator<<(ostream& outfile, const Bubble& alist)
{

    nodeType* current;

    current = alist.head_ptr;

    //you dont know if the list is sorted or not
      outfile << "Unsorted: " <<'\n';
    //outfile << current << endl;  //displays a memory address

    while(current != NULL)
    {
        outfile << current->info << " ";
        current = current->link;
    }
    return outfile;
}


/*
void Bubble::bubblesort(int *mylist[], int numitems)
{
  int temp;
  int iteration;
  int index;
  bool noexchanges = false;
  iteration = 1;

  while(iteration < numitems && !! noexchanges)
  {

      noexchanges = true;
      for (index = 0; index < numitems - iteration; index++)
       {
          if(*mylist[index] > *mylist[index + 1])
          {
              temp = *mylist[index];
              *mylist[index] = *mylist[index + 1];
              *mylist[index + 1] = temp;
              noexchanges = false;

          }
          iteration++;
       }
       for(index = 0; index < numitems; index++)
       {
           cout << mylist[index] << " ";
       }
  }
}
*/

[nekoleon64]

//main.cpp

#include <iostream>
#include <fstream>

using namespace std;

#include "Bubble.h"

int main()
{
    ifstream infile;
    ofstream outfile;

    infile.open("sort.txt");
    outfile.open("sort.out");

    if(infile)
    {
        cout << "The file is open.";
    }

    Bubble mylist;

    infile >> mylist;

    cout <<"The data is now read.";

    outfile << mylist;
    cout << mylist;

    //inData.close(); //Close infile
    //outData.close(); //Close outfile
    system("pause");
    return 0;
}

[VernonDozier]

What exactly is the problem? Possibilities might include...

• Reading from file.
• Writing to file.
• Iterating through the list.
• Swapping elementss that are out of order.
• Not understanding the bubble sort itself.

I see no non-commented out attempt to do a bubble sort, so obviously things are not going to sort. More information is needed on where / how you are stuck. The input, the expected output, the ACTUAL output might also help.

[nekoleon64]

I've been given a completed version of the bubblesort by my teacher. And i had some help by a classmate that helped me print out the Unsorted list on my notepad out files. I understand that the bubblesort uses two index two compare and swap numbers unsorted and it iterates (iteration is doing the compare and swap numbers over again) each time until the entire list is sorted. so I understand the bubblesort. I just need help to change the data structure of the bubblesort so it still uses linked list, but not the entire data. Since I'm using linked list on my functions, the bubblesort part is no exception. I need to make sure that the member fuction uses thoses so they properly compare and swap the numbers through each iteration. And then write them out to the operator<<.

[nekoleon64]

//Bubble.cpp

void Bubble::bubblesort(int mylist[], int numitems)
{
  int temp;
  int iteration;
  int index;
  bool noexchanges = false;
  iteration = 1;

  while(iteration < numitems && !! noexchanges)
  {

      noexchanges = true;
      for (index = 0; index < numitems - iteration; index++)
      {
          if(mylist[index] > mylist[index + 1])
          {
              temp = mylist[index];
              mylist[index] = *mylist[index + 1];
              mylist[index + 1] = temp;
              noexchanges = false;

          }
          iteration++;
      }
       for(index = 0; index < numitems; index++)
       {
           cout << mylist[index] << " ";
       }
  }
}
*/

At this moment, this needs to be changed. I've removed the stars that are the pointers so I could show you to the completed version of Bubblesort that I was given. I need to change the data structure so that that it follows the linked list and pointers. At the time I tinkered with this function and didn't realize until a bit sooner that I needed to modify this code to that it uses linked list and pointers. I said that already.

Also I almost forgot, I need to construct two more a copy constructor and a destructor before I tinker with the bubblesort part.

[nekoleon64]

Anyway I can get the constructor and deconstructor figured out myself. I just need help figuring out to change the data structure, but not the data itself of the void bubblesort.
I do need a nodeType current and then uses that somehow to change the data structure. Sorry I'm not good with explaining at times so hopefully I have elaborated myself.

They only output that did print out is the unsorted list:
91 103 59 67 52 41 37 32 39 12 23 29

[VernonDozier]

OK, so the stumbling point at the moment is how to change from an array-based implementation of a Bubble Sort to one based on a linked list. So the goal is to change lines 9 to 29. First off, you have a double ! on line 9. That's confusing to look at, so let's simply change it to...

while(iteration < numitems && noexchanges)

Now we'll need to change it to a linked-list based test. In a linked-list, the end of list is delimited by the pointer to the next node being NULL. So we need a pointer to an element and we'll get rid of the index variable (unneeded for linked list). It also can't hurt to start with a test for the trivial case. If there are 0 or 1 elements total, there is nothing to sort. How about at the very top, we do the following.

nodeType* ptr = /* point to the head of the list */;
if(ptr == NULL || ptr->link == NULL)
{
    return;
}

You'll need to change the arguments that the function takes. Seems to me it doesn't need any arguments. The object itself contains everything we need. So let's change our test case on line 9 to what we need for a linked list.

while(ptr->link != NULL && noexchanges)

All this is testing is the same thing it was testing before. Have we reached the end of the list? And if so, have there been any exchanges? If we've reached the end of the list and there have been no exchanges, we are done. The logic should be identical to the array-based code.

But wait. Is this the right test? If we HAVE made exchanges, we want to go through everything again. Hence if there was a variable called exchanges that was true, we's want to go through everything again. However, here we have a variable called noexchanges. We would want that FALSE in order to go through again. Remember we have TWO, not one! operators, which cancelled each other out. That seems like a mistake. You probably wanted one, so let's stick it in.

while(ptr->link != NULL && !noexchanges)

There is still a problem here. This is the OUTER loop, not the inner loop. In the array based code, we have a nest for loop and we know how many items we have. For the linked list case, we don't know. Do we really need or want that first test in the OUTER loop? Does it make sense? Does it help? Here is where the linked list code and the array-based code is different. The second part of the test (the one where it tests whether there are any exchanges) should be sufficient. Just go until you've gone a full iteration through the list with no exchanges needed. Note that you could do this with the array based code too.

while(!noexchanges) // line 9 -- outer loop test

Now let's look at the inner loop. Keep in mind that we want to iterate fully through the list in the inner loop. Look at the line we have at the top...

nodeType* ptr = /* point to the head of the list */;

Place it right above line 13. This resets the pointer to the head. Now recall the test that I originally had as part of the OUTER loop.

while(ptr->link != NULL)

I took it out of the outer loop because I thought it did more harm than good. However, in the INNER loop, we want to iterate through the whole list, so it could be handy. Or rather, something close to it could be handy. We'll be replacing line 13 with something very similar to what is above. Get out your pencil and paper and consider the following scenario. Consider a linked list with four elements (5 2 7 9). An iteration of the bubble sort will involve THREE comparisons (one comparison less than the total number of elements). Consider the following iteration. See bold.

5 2 7 9 (is 2 < 5? Yes, swap 5 and 2.)
2 5 7 9 (is 7 < 5? No.)
2 5 7 9 (is 9 < 7? No.)

Now think of the pointers involved. At the start, we need to have the pointer start by pointing at 5. We are comparing 5 and 2. In other words, we are comparing ptr->info and ptr->link->info. What's the test for when we have reached the end of the list? Or to put it another way, when will we seg fault if we mess up? We cannot dereference a NULL pointer, plus a NULL pointer denotes the end of the list. Hence replace line 13 with what we had above. No need to change anything...

while(ptr->link != NULL)

Your job is to go through the code and change everything line by line from an array-based approach to a linked-list based approach. This is assuming everything else in the code works for an array-based Bubble sort. Get rid of any unneeded variables. get out pencil and paper. The algorithm will be the same. Hopefully this gives you a decent start.