Need a good sort algorithm

[Mr. Green]

I'm trying to sort a singly linked list and I can't get the algorithm right

I'm trying to sort an already full list. it seems like it would be a lot easier to sort a list as it's being filled, but I can't figure that algorithm out either. here's some of my code so you can see what I mean:



POLYNOMIAL.H
------------
//this is the header file for class Polynomial and struct term

using namespace std;

struct term
{
int co; //coefficient of the term
int exp; //exponent of the term
term* link;
};

typedef term* termptr;

class Polynomial
{
public:
Polynomial (const Polynomial& p1);
~Polynomial();
void operator = (Polynomial p1);
Polynomial() {head = NULL;}
void sort();
const termptr get_head() const {return head;}
void set_head(termptr t1) {head = t1;}
Polynomial operator + (Polynomial& p1);
friend istream& operator >> (istream& ins, Polynomial& p1);
friend ostream& operator << (ostream& outs, Polynomial& p1);
private:
termptr head;
};

POLYNOMIAL.cc
-------------
//definitions for class Polynomial

#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cctype>
#include "polynomial.h"

using namespace std;

Polynomial::Polynomial(const Polynomial& p1)
{
termptr temp, temp1;
temp = p1.get_head();

if (!p1.get_head())
return;

temp1 = new term;
temp1->co = temp->co;
temp1->exp = temp->exp;
temp1->link = NULL;
head = temp1;
temp = temp->link;

for (termptr ptr = temp; ptr != NULL; ptr = ptr->link)
{
temp1->link = new term;
temp1 = temp1->link;
temp1->co = ptr->co;
temp1->exp = ptr->exp;
}
}

istream& operator >> (istream& ins, Polynomial& p1)
{
char x;
string line;
termptr new_term, current;

new_term = new term;
new_term->link = NULL;
p1.set_head(new_term);
current = new term;

getline(ins,line);

if (ins)
{
line.erase(remove(line.begin(), line.end(),' '), line.end());
stringstream ss(line);

while (ss>>current->exp >> x >> current->exp)
{
new_term = new term;
new_term->link = NULL;
current->link = new_term;
current = current->link;
}
}
current->link = NULL;
return ins;
}

void Polynomial::sort()
{
Polynomial p1;
termptr cursor, new_term;
int largest = 0;

new_term = new term;
p1.set_head(new_term);
cursor = new_term;

for (termptr ptr = head; ptr != NULL; ptr = ptr->link)
{
for (termptr temp = ptr; temp != NULL; temp = temp->link)
{
if (temp->exp > largest)
{
largest = temp->exp;
cursor->co = temp->co;
cursor->exp = temp->exp;
cursor->link = new term;
}
}
}
head = p1.get_head();
}

ostream& operator << (ostream& outs, Polynomial& p1)
{
for (termptr ptr = p1.get_head(); ptr != NULL; ptr = ptr->link)
{
if (ptr == p1.get_head())
{
if (ptr->exp == 0)
{
outs << ptr->co;
}else if (ptr->exp > 0)
{
outs << ptr->co << "x" << ptr->exp;
}
}else
{
if (ptr->exp == 0)
{
outs.setf(ios::showpos);
outs << ptr->co;
outs.unsetf(ios::showpos);
}else if (ptr->exp > 0)
{
outs.setf(ios::showpos);
outs << ptr->co;
outs.unsetf(ios::showpos);
outs << "x" << ptr->exp;
}
}
}
return outs;
}

MAIN.cc
-------
//application file

#include <iostream>
#include "polynomial.h"

using namespace std;

int main()
{
Polynomial poly1, poly2, result;

cout << "Please enter a polynomial: ";
cin >> poly1;
cout << endl;
//poly1.sort(); --sort doesn't work at all so I commented it out
cout << "Please enter another one: ";
cin >> poly1;
cout << endl;
//poly2.sort();

cout << poly1 << endl << poly2 << endl;

return 0;
}



what I really want to know is how to sort the incoming list while it's still being input

[Paul McKenzie]

I'm trying to sort a singly linked list and I can't get the algorithm right
Why not just use std::list, which has a sort() function instead of doing this all yourself?

Regards,

Paul McKenzie

[Paul McKenzie]

Something like this:

#include <list>

struct term
{
int co; //coefficient of the term
int exp; //exponent of the term
};

bool SortTerms( const term &Term1, const term& Term2 )
{
if ( /* Term1 < Term2 */ ) // fill in with some code here
return true;
return false;
}

class Polynomial
{
public:
Polynomial() { }
Polynomial operator + (Polynomial& p1);
friend istream& operator >> (istream& ins, Polynomial& p1);
friend ostream& operator << (ostream& outs, Polynomial& p1);

void Sort( ) { head.sort( head.begin(), head.end(), SortTerms); }
void AddTerm( const term& t ) { head.push_back(t); }

private:
std::list<term> head;
};

Now all you need to do is to add to the linked list, and call Sort(). The sort criteria is in SortTerms. You will get two terms, and you have to decide whether the term1 is < term2. You should fill this in with whatever you see fits your description of term1 < term2.

Note that the linked list implementation is not embedded in the Polynomial class, instead an instance of a linked list class, head, is used. Also, copy constructor and assignment operator are no longer necessary, since std::list correctly copies items.

Regards,

Paul McKenzie

[Mr. Green]

this is a project for a class and we haven't learned about the list type yet. so I doubt my instructor would be happy with me

[Mr. Green]

okay, I tried a new algorithm, now the sort function looks like this:


void Polynomial::sort()
{
termptr current, cursor, prev;
int largest = 0;

current = head;
cursor = current->link;
prev = current;
for (termptr ptr = head; ptr != NULL; ptr = ptr->link)
{
largest = current->exp;
while (cursor)
{
if (cursor->exp > largest)
{
largest = cursor->exp;
prev->link = cursor->link;
ptr = cursor;
cursor->link = current;
prev = current;
current = cursor;
cursor = prev;
cursor = cursor->link;
}else
{
prev = prev->link;
cursor = cursor->link;
}
}
current = current->link;
prev = current;
cursor = current->link;
}
}



I drew it out on paper and it looks like it should work, but I keep getting a segmentation fault for some reason

[Paul McKenzie]

1) Instead of trying to think of an algorithm yourself, use the ones that are known. Which algorithm are you trying to implement? Bubble sort? Quicksort? Insertion Sort? Heap Sort?

2) Did you use a debugger to find where the problem is? This is just a matter of using a debugger.

3) The easiest way to solve your problem is to use a technique used by programmers who use the MFC CList, which does not have a "sort" function -- copy the linked list elements to an array, sort the array, and then recreate the list with the sorted elements of the array. Since the elements in the array are sorted, it is simple just to keep adding to the tail of the new linked list.

Regards,

Paul McKenzie