linked lists

bubble sort of the nodes in a linked list

Page 1 of 1

10 Replies - 1565 Views - Last Post: 31 March 2009 - 04:12 PM Rate Topic: -----

#1 moe_3_moe   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 12-March 09

linked lists

Post icon  Posted 29 March 2009 - 09:30 AM

I am trying to write a function that sort the nodes in a link list in an ascending order according to the ID number. I thought about the bubble sort function and i tried to write it, but it looks likethe compiler doesn't go into the for loop.
void bubble_sort(Node *&Front,Node *&Rear, int L_size){		// bubble sort  method to order integers in ascending order
	 
	 Node *temp_node= Front;
				
	 for(int i=0;i<L_size;i++){
			 for(int y=1; y<L_size-1; y++){
					 if(temp_node->ID > temp_node->next->ID)
					 {
								long temp =temp_node->next->ID;
								temp_node->next->ID = temp_node->ID;
								temp_node->ID = temp;
								
								}
								}
								}   
							   for(int j=0; j<L_size; j++){												 
							   
							   cout<<temp_node->ID<<endl;
							   
							   temp_node = temp_node->next;
							   }							  
							   
			 }




Is This A Good Question/Topic? 0
  • +

Replies To: linked lists

#2 alien_programmer   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 28-March 09

Re: linked lists

Posted 30 March 2009 - 06:17 AM

brother...your indentation is confused, please repair it and then we can help you =D
Was This Post Helpful? 0
  • +
  • -

#3 moe_3_moe   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 12-March 09

Re: linked lists

Posted 30 March 2009 - 09:16 AM

It is a function, with argument, in it there is 2 for loops to sort the list in an ascending order and at the end it prints out the ID number by order.
Was This Post Helpful? 0
  • +
  • -

#4 moe_3_moe   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 12-March 09

Re: linked lists

Posted 30 March 2009 - 09:21 AM

#include <iostream>						//standard C++ IO operations using streams
#include <cstdlib>						 //standard General Purpose functions (atoi, memalloc, ...)
#include <math.h>
#include <fstream>
#include <string>

using namespace std;

struct Node{
	string Name;
	long ID;
	float costs;

	Node *next;	 //next pointer to next struct
	Node();		 //Constructor

};

//Constructor: Node
Node::Node(){
	next = NULL;
}


void Insert(Node *&Front,Node *&Rear, int &L_size, string n_name, long n_Id, float n_costs){
	Node *n_Info = new Node();		  //Create new object for n_name
	
	//Added info
	n_Info->Name = n_name;
	n_Info->costs = n_costs; 
	n_Info->ID = n_Id;


	if(L_size ==0){		 //When empty list
		Front = Rear = n_Info;
	}

	else if(L_size > 0){
		Rear->next = n_Info;		//create the link to the n_Info
		Rear = n_Info;			  //now move the pointer
	}
	L_size++;

}

void Print (Node *&Front,Node *&Rear, int &L_size){
	Node *temp_node = Front;

	for(int i =0; i<L_size; i++){
		cout<<temp_node->Name<<endl;
		cout<<temp_node->ID<<endl;
		cout<<temp_node->costs<<endl;
		temp_node = temp_node->next;
	}
}

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;
	}

}

void MaxMinAvg(Node *&Front,Node *&Rear, int L_size){
	 Node *temp_node= Front;	 //a copy of Front is stored in temp_node
	 double max, min , avg, sum=0;
	 sum = max = min = temp_node->costs;
	 for ( int i=1; i<L_size; i++){
		 sum +=temp_node->next->costs;
		 if( temp_node->next->costs > max)
		 {
			 max=temp_node->next->costs;
			 }   
		 if(temp_node->next->costs<min){
			 min=temp_node->next->costs;
			 }
		 temp_node=temp_node->next;
		 }
		 cout<< "The maximum cost is: "<<max<<endl;
		 cout<< "The minimum cost is: "<<min<<endl;
		 cout<< "The average cost is: "<<sum/L_size<<endl;
		 }


//all programs start here in main function
int main(){

	Node *Front = NULL;
	Node *Rear = NULL;					  //Creates our Front and Rear of the list	
	int L_size = 0;						 //Initialize Linked List size to 0
 
	ifstream in("a7.txt");
	char temp[100];
	string temp_name;
	long temp_ID;
	float temp_costs;

	while(in.peek() != EOF){
		in.getline(temp, 100);
		temp_name = temp;

		in.getline(temp, 100);
		temp_ID = atol(temp);
		
		in.getline(temp, 100);
		temp_costs = atof(temp);

		in.getline(temp, 100);

		Insert(Front, Rear, L_size, temp_name, temp_ID, temp_costs);	 //Insert each 

	}

	Print(Front, Rear, L_size);	//Print entire list
	
	MaxMinAvg( Front, Rear, L_size);

	Flush(Front, Rear, L_size);	 //Flush out the list
	
	

	system("pause");				//causes the system to pause when executing, to view print outs
									//not needed in Visual C++ 2008
	return 0;					   //return 0 to terminate the main function because its data type is int
}





HEre is my code, i would like to add the bubble sort function to sort the list in ascending order based on the ID number. Is it clear now?
Was This Post Helpful? 0
  • +
  • -

#5 BlakeJustBlake   User is offline

  • D.I.C Regular
  • member icon

Reputation: 26
  • View blog
  • Posts: 441
  • Joined: 15-February 09

Re: linked lists

Posted 30 March 2009 - 09:50 AM

I put that in and compile (without the bubble sort function) and I get a Segmentation Fault. Might want to check that out.
Was This Post Helpful? 0
  • +
  • -

#6 moe_3_moe   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 12-March 09

Re: linked lists

Posted 30 March 2009 - 11:03 AM

what do you mean by segmentation? i will attahc the file from which the code reads.

Here is the file i read from in my code

Attached File(s)

  • Attached File  a7.txt (220bytes)
    Number of downloads: 90

Was This Post Helpful? 0
  • +
  • -

#7 moe_3_moe   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 12-March 09

Re: linked lists

Posted 31 March 2009 - 12:57 AM

Alright, i got the bubblesort to work, but the problem is that it starts from the second node.

void bubblesort( Node *&Front, Node *&Rear, int L_size){ //here i am using

Node *temp_node = Front;
Node *pvr = Front;
temp_node = temp_node->next;
int temp;
string temp1;
long temp2;
for( int i = 0 ; i < L_size ; i++ ){
for( ; temp_node != NULL; pvr = pvr -> next , temp_node=temp_node->next)

{
if(pvr->ID > temp_node->ID)
{
temp1 = pvr->Name;
pvr->Name = temp_node->Name;
temp_node->Name = temp1;

temp = pvr->ID;
pvr->ID = temp_node->ID;
temp_node->ID = temp;

temp2 = pvr->costs;
pvr->costs = temp_node->costs;
temp_node->costs = temp2;


}
}
}
Print( Front, Rear, L_size);
}
Was This Post Helpful? 0
  • +
  • -

#8 janotte   User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: linked lists

Posted 31 March 2009 - 02:17 AM

1 - Please post your code like this :code:
Failure to do so reduces you chance of help hugely.

2 - Have a look here:
temp_node = temp_node->next;


Was This Post Helpful? 0
  • +
  • -

#9 moe_3_moe   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 12-March 09

Re: linked lists

Posted 31 March 2009 - 03:13 PM

I know that i should let it point at the first ID in the first node, but when i write temp_node = temp_node -> ID; it doesn't work...
void bubblesort( Node *&Front, Node *&Rear, int L_size){  //here i am using 
	 
Node *temp_node = Front;
Node *pvr = Front;
temp_node = temp_node->next;
long temp;
string temp1;
float temp2;
for( int i = 0; i < L_size; i++ ){
 for( temp_node->ID; temp_node != NULL; pvr = pvr ->next , temp_node=temp_node->next) 

 {
  if(pvr->ID > temp_node->ID)
  {
   temp1 = pvr->Name;
   pvr->Name = temp_node->Name;
   temp_node->Name = temp1;
   
   temp = pvr->ID;
   pvr->ID = temp_node->ID;
   temp_node->ID = temp;
   
   temp2 = pvr->costs;
   pvr->costs = temp_node->costs;
   temp_node->costs = temp2;
   
   
  }
 }
 
} 
Print( Front, Rear, L_size);
}


Was This Post Helpful? 0
  • +
  • -

#10 Notorion   User is offline

  • D.I.C Regular

Reputation: 35
  • View blog
  • Posts: 378
  • Joined: 17-February 09

Re: linked lists

Posted 31 March 2009 - 03:52 PM

Ok, first of all create a swap function, it makes much more sense

See this bubble sort snippet for example (to get an idea of how the function operates, not the syntax for your specific example)

http://www.dreaminco.../snippet951.htm

That page, describes how to construct your function to complete the swap

I am unable to debug your program currently (no compiler access), however it looks to me like your pointers get very confusing, because you don't pass the nodes off to a function to get swapped rather you use your pointers that you are also using to search the algorithm to identify what needs to be swapped.

See I would just use your pointers to comb through the data, then pass them to a swap function (with those pointers values passed by reference, to make this problem much more clear.)

Because after your first swap, it's very hard to know exactly where your pointers are at that point.
Was This Post Helpful? 0
  • +
  • -

#11 moe_3_moe   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 37
  • Joined: 12-March 09

Re: linked lists

Posted 31 March 2009 - 04:12 PM

the function is doing the job by listeng the nodes in ascending order of ID but it skips the forst node since the first pointer is pointing at the next.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1