This program reads in some numbers then outputs the numbers, low to high, by using a bubble sory. I need some help to start how to do the bubble sort on a linked list. Here is what i have so far.

.h file

#include<iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

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

class Bubble
{
    public:
        Bubble();
        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;
};
void list_clear(nodeType*& head_ptr);
void list_copy(const nodeType* source_ptr,
       nodeType*& head_ptr, nodeType*& tail_ptr);




#include "Bubble.h"

Bubble::Bubble()
{
    head_ptr = NULL;
    manynodes = 0;
}
int Bubble:: size() const
{
    return manynodes;
}
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;
    }
}
void Bubble::Bubblesort()
{
     nodeType *temp, *last, *prev, *curr;
     int iteration;
     int index;
     int numitems = size();
     bool noexchanges = false;

     iteration = 1;

     while(iteration < numitems and !noexchanges)
     {
            noexchanges = true;
            for(index = 0; index<numitems-iteration;index++)
            {

            }
            iteration++;
    }
}
istream &operator>>(istream &infile, Bubble &mylist)
{
    int num;
    nodeType *newNode, *tail;

    tail = NULL;
    mylist.head_ptr = NULL;
    mylist.manynodes = 0;

    infile>>num;

    while(infile)
    {

        newNode = new nodeType;
        newNode -> info = num;
        newNode -> link = NULL;

        if(mylist.head_ptr == NULL)
        {
            mylist.head_ptr= newNode;
            mylist.manynodes++;
        }
        else
        {
            tail->link = newNode;
            mylist.manynodes++;
        }
        tail = newNode;
        infile>>num;
    }
      return infile;
}
ostream &operator<<(ostream &outfile, const Bubble &alist)
{
    nodeType *newNode;
    newNode = new nodeType;
    newNode = alist.head_ptr;

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

Is there a specific requirement to use the bubblesort algorithm? With a linked list, an insertion sort would generally make more sense.

The main thing you'll want for bubblesort that you don't already have is some kind of swap() function. Since it is a singly-linked list, you'll want to pass it the nodes previous to the ones to be swapped.

I take back what I said; there's a much easier solution, one which avoids all this problematic mucking about with the previous nodes: simply swap the values, rather than the nodes themselves.

I'm going to talk to my teacher and ask him if it is ok to change the parameter for the Bubblesort.(he was the one who made the header file)

Oh? What would you need to change it for?

BTW, your operator>>() function may need work; while it will work correctly for a file, it will go into an infinite loop when reading from cin. I would recommend redesigning it to read one line of numbers at a time, and if necessary loop throough the input file explicitly. Also, it will fail silently if the input isn't numeric.

Edited 3 Years Ago by Schol-R-LEA

This question has already been answered. Start a new discussion instead.