-
Sorting a Linked List
Hi I'm trying to sort a linked list I created using a function but I have no idea how to sort it. Can anyone help me?
Here's my Code:
Code:
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;
struct Node{
string parts;
int ID;
int date;
float price;
Node *next;
Node();
};
Node::Node()
{
next=NULL;
}
void Insert(Node *&Front,Node *&Rear, string n_parts, int date, int n_Id, float n_price, int count)
{
Node *n_Info = new Node();
n_Info->parts = n_parts;
n_Info->date = date;
n_Info->price = n_price;
n_Info->ID = n_Id;
if(count ==0)
{
Front = Rear = n_Info;
}
else if(count > 0)
{
Rear->next = n_Info;
Rear = Rear -> next;
}
do
{
if (n_Info == NULL)
cout << "End of list" << endl;
else
{
cout<< n_Info->parts<<endl;
cout<< n_Info->ID<<endl;
cout<< n_Info->date<<endl;
cout<< n_Info->price<<endl;
cout << endl;
n_Info = n_Info->next;
}
}
while (n_Info != NULL);
}
void Flush(Node *&Front,Node *&Rear, int L_size)
{
Node *temp_node = Front;
for(int i =0; i<L_size; i++)
{
Front = Front->next;
delete temp_node;
temp_node=Front;
}
}
float Avg(float n_price)
{
static float sum = 0, i = 0;
sum += n_price;
i++;
return (sum/i);
}
float Highest(float n_price)
{
static float max = 0;
if(n_price > max)
max = n_price;
return max;
}
float Lowest(float n_price)
{
static float min = n_price;
if(n_price < min)
min = n_price;
return min;
}
int main()
{
Node *Front = NULL;
Node *Rear = NULL;
int L_size = 0;
ifstream myfile1("a7.txt");
char temp[100];
string temp_parts;
int temp_ID;
int temp_date;
float temp_price;
float average, high, low;
while(myfile1.peek() != EOF)
{
myfile1.getline(temp, 100);
temp_parts = temp;
myfile1.getline(temp, 100);
temp_ID = atoi(temp);
myfile1.getline(temp, 100);
temp_date = atoi(temp);
myfile1.getline(temp, 100);
temp_price = atof(temp);
myfile1.getline(temp, 100);
Insert(Front, Rear, temp_parts, temp_date, temp_ID, temp_price, L_size);
average = Avg(temp_price);
high = Highest(temp_price);
low = Lowest(temp_price);
L_size++;
}
cout<<fixed<<setprecision(2)<<"Average Price: "<<average<<endl;
cout<<fixed<<setprecision(2)<<"Most Expensive: "<<high<<endl;
cout<<fixed<<setprecision(2)<<"Most Inexpensive: "<<low<<endl;
Flush(Front, Rear, L_size);
return 0;
}
Would it be any similar to this?
Code:
void bubbleSort(int *array, int length)
{
for(int i = 0; i < length; i++)
{
int s = i;
for(int c = i+1; c < length; c++)
{
if(array[c]<array[s])
{
s = c;
}
}
swap(array[i], array[s]);
cout<<array[i]<<endl;
}
}
-
You could do it via the bubble sort algorthm. Just create an iterator which iterates through your linked list for you and have a swap method that swaps the two nodes depending on a conditional which you have set.
However, have you considered sorting them during insertion? If your project requirements allow you to sort during insertion I suggest you take that approach.
cs_student
EDIT: You might even want to have a class LinkedList which manages inserting and retrieving data.
-
The assignment requires me to do it this way. I haven't found any good tutorials on how to do the std::list method.
I found a way to sort it with singly list but it doesn't seen to work for me
Code:
void sortNodes(Node * ptr) {
int temp = 0;
Node * curr;
curr->parts = parts;
curr->date = date;
curr->price = price;
curr->ID = Id;
for(bool didSwap = true; didSwap; ) {
didSwap = false;
for(curr = ptr; curr->next != NULL; curr = curr->next) {
if(curr->date > curr->next->date) {
temp = curr->date;
curr->date = curr->next->date;
curr->next->date = temp;
didSwap = true;
}
}
}
do
{
if (curr == NULL)
cout << "End of list" << endl;
else
{
cout<< curr->parts<<endl;
cout<< curr->ID<<endl;
cout<< curr->date<<endl;
cout<< curr->price<<endl;
cout << endl;
curr = curr->next;
}
}
while (curr != NULL);
}
-
Create a singly linked list class which handles the nodes for you.
Try implementing something along the lines of
Code:
class SList
{
private:
Node* head;
public:
SList(Node* head); // constructs SList
Node* get(int pos); // return the node in x position
int getData(int pos); // return data in x position
void insert(Node* node); // insert node or data
void swap(int a, int b); // swap positions a and b
};
~
This would allow you to use the SList class as a front end for the Nodes while implementing the bubble sort.
For example when you find that you need to switch two nodes you don't have to reset their tail nodes they point to and which head nodes point to them (etc...). You just call list.swap(a, b). This would also give you an easy way to go back and reimplement it so that it can be sorted during insertion.
Also I'm assuming the data your going to be comparing is an integer. You can always use a template so that you are not constrained to an integer when using your SList class. This way you can have a singly linked list of any type of object you wish.
cs_student
-
See that rocket launcher in your Avatar cs_student? If you ever try to implement BubbleSort for a linked list by re-linking nodes, you could save yourself some time and shoot yourself in the foot with it! :D It'll probably be less pain.
Okay for arrays, not so good for linked-lists!
Sherina: Thank goodness your teachers require you to do it via re-linking pointers. Treating a linked-list like an array only gives you the worst of both worlds! Don't swap the data, re-link the pointers.
I strongly advise you to implement Insertion Sort. It is the shortest linked-list sorting algorithm there is, out of all 30 linked-list sorting algorithm I know of.