DaniWeb Forum Index > Software Development > C++

C++ RSS

Link List Sorting Problem

•

Join Date: Jul 2004

Posts: 65

Reputation: koh is an unknown quantity at this point

Solved Threads: 0

koh

Offline

Junior Poster in Training

Link List Sorting Problem

Sep 2nd, 2005

i tried for sorting the link list for weeks already, and yet still couldnt get the output as what i want.

i search through the forum and i found the coding "algorithm" (in blue color) for sorting...but it seems tooo alit bit toooooooooooo long.

so far, i was trying to implement the same way as bubble sorting, but still...can not get answer

. i tried using the elements, just like in bubble sort,
for example:

Help with Code Tags

(Toggle Plain Text)

 
void abc::sorting()
{
Node *cur = head;
Node *pvr = head;
cur = cur->next;
int hold;
for( int pass = 0 ; pass < ( 8 - 1 ) ; pass++ )
 for( ; cur != NULL; pvr = pvr -> next , cur=cur->next) 
// in this case i put cur != NULL because it came to NULL first than pvr
 {
  if(pvr->num > cur->num)
  {
   hold = pvr->num;
   pvr->num = cur->num;
   cur->num = hold;
  }
 }
}

still can not also.. i hope that some experts out there could help me in this problem....giving me advice(s). i really headache already...couldn't figure out anything.... thanks

below here is my coding:

Help with Code Tags

(Toggle Plain Text)

#include <iostream>
using namespace std;
class abc
{
private:
 struct Node
 {
  int num;
  Node *next;
 };
 Node *head;
 Node *ptr;

public:
 abc() { head = NULL; }

 void display();
 void add( int );
 void sorting();
 void sort();
};


void abc::add( int a )
{
 if( head == NULL )
 {
  head = new Node;
  head->num = a;
  head->next = NULL;
  ptr = head;
 }

 else
 {
  ptr->next = new Node;
  ptr = ptr->next;
  ptr->num = a;
  ptr->next = NULL;
 }
}

void abc::display()
{
 for(Node *cur = head ; cur != NULL ; cur = cur->next)
  cout << cur->num << " ->";
 cout << endl;
}


void abc::sorting()
{
Node *cur = head;
Node *pvr = head;
cur = cur->next;
int hold;

for( ; pvr!= NULL  ; pvr=pvr->next )
 for( ; cur != NULL;  cur=cur->next)
 {
  if(pvr->num > cur->num)
  {
   hold = pvr->num;
   pvr->num = cur->num;
   cur->num = hold;
  }
 }
}


void main()
{
abc f;

f.add(9);
f.add(8);
f.add(7);
f.add(6);
f.add(5);
f.add(4);
f.add(3);
f.add(2);

cout << endl;
f.display();

//f.sorting();

f.sort();
cout << endl;
f.display();


}

/*****************************************************/
void abc::sort()
{
 Node *ptr1,*ptr2,*temp,*Imithead1,*Imithead2,*before;
 if (head != NULL) {
  ptr2 = head;
  ptr1 = head->next;
  //First Step Set the smallest value to head
  while(ptr1 != NULL ) {
   if (ptr2->num > ptr1->num ) {
    temp = ptr2;
    while(temp->next != ptr1) 
     temp = temp->next;
    temp->next = ptr1->next;
    ptr1->next = ptr2;
    head = ptr1;}
   ptr1 = ptr1->next;
   ptr2 = head;}
  
////////////////////////////////////////////
////////////////////////////////////////////
  before = head;
  Imithead1 = Imithead2 = head->next;
  while (Imithead1 != NULL) {
   
  while (Imithead2 != NULL ) {
   ptr1 = ptr2 =Imithead2;
   while(ptr1 != NULL ) {
    if (ptr2->num > ptr1->num ) {
     temp = ptr2;
     while(temp->next != ptr1) 
      temp = temp->next;
     before->next = ptr1;
     temp->next = ptr1->next;
     ptr1->next = ptr2;
     Imithead2 = ptr1;
   
    }
    ptr1 = ptr1->next;
    ptr2 = Imithead2;
   }
   before = Imithead2;
   Imithead2 = Imithead2->next;
   
  }
  
  Imithead1 = Imithead1->next;
  Imithead2 = Imithead1;
  }
 }
}
/*************************************************/

#include <iostream>
using namespace std;
class abc
{
private:
 struct Node
 {
  int num;
  Node *next;
 };
 Node *head;
 Node *ptr;

public:
 abc() { head = NULL; }

 void display();
 void add( int );
 void sorting();
 void sort();
};


void abc::add( int a )
{
 if( head == NULL )
 {
  head = new Node;
  head->num = a;
  head->next = NULL;
  ptr = head;
 }

 else
 {
  ptr->next = new Node;
  ptr = ptr->next;
  ptr->num = a;
  ptr->next = NULL;
 }
}

void abc::display()
{
 for(Node *cur = head ; cur != NULL ; cur = cur->next)
  cout << cur->num << " ->";
 cout << endl;
}


void abc::sorting()
{
Node *cur = head;
Node *pvr = head;
cur = cur->next;
int hold;

for( ; pvr!= NULL  ; pvr=pvr->next )
 for( ; cur != NULL;  cur=cur->next)
 {
  if(pvr->num > cur->num)
  {
   hold = pvr->num;
   pvr->num = cur->num;
   cur->num = hold;
  }
 }
}


void main()
{
abc f;

f.add(9);
f.add(8);
f.add(7);
f.add(6);
f.add(5);
f.add(4);
f.add(3);
f.add(2);

cout << endl;
f.display();

//f.sorting();

f.sort();
cout << endl;
f.display();


}

/*****************************************************/
void abc::sort()
{
 Node *ptr1,*ptr2,*temp,*Imithead1,*Imithead2,*before;
 if (head != NULL) {
  ptr2 = head;
  ptr1 = head->next;
  //First Step Set the smallest value to head
  while(ptr1 != NULL ) {
   if (ptr2->num > ptr1->num ) {
    temp = ptr2;
    while(temp->next != ptr1) 
     temp = temp->next;
    temp->next = ptr1->next;
    ptr1->next = ptr2;
    head = ptr1;}
   ptr1 = ptr1->next;
   ptr2 = head;}
  
////////////////////////////////////////////
////////////////////////////////////////////
  before = head;
  Imithead1 = Imithead2 = head->next;
  while (Imithead1 != NULL) {
   
  while (Imithead2 != NULL ) {
   ptr1 = ptr2 =Imithead2;
   while(ptr1 != NULL ) {
    if (ptr2->num > ptr1->num ) {
     temp = ptr2;
     while(temp->next != ptr1) 
      temp = temp->next;
     before->next = ptr1;
     temp->next = ptr1->next;
     ptr1->next = ptr2;
     Imithead2 = ptr1;
   
    }
    ptr1 = ptr1->next;
    ptr2 = Imithead2;
   }
   before = Imithead2;
   Imithead2 = Imithead2->next;
   
  }
  
  Imithead1 = Imithead1->next;
  Imithead2 = Imithead1;
  }
 }
}
/*************************************************/

<< moderator edit: added [code][/code] tags >>

•

Join Date: Sep 2004

Posts: 7,541

Reputation: Narue has a reputation beyond repute

Solved Threads: 704

Narue

Offline

Code Goddess

Re: Link List Sorting Problem

Sep 2nd, 2005

Don't try to bubble sort a linked list, it's bad enough for arrays. There are two sorting algorithms that lend themselves well to sorting linked lists: insertion sort and merge sort. However, selection sort is also easy to visualize and to implement.

I'm here to prove you wrong.

•

Join Date: Jul 2004

Posts: 65

Reputation: koh is an unknown quantity at this point

Solved Threads: 0

koh

Offline

Junior Poster in Training

Re: Link List Sorting Problem

Sep 2nd, 2005

well, actually i want to try to sort it out by using bubble sort...curious to know how it works...i tried many times already, yet no result...i hope that you could help me :-|

thanks

•

Join Date: Sep 2004

Posts: 7,541

Reputation: Narue has a reputation beyond repute

Solved Threads: 704

Narue

Offline

Code Goddess

Re: Link List Sorting Problem

Sep 2nd, 2005

>curious to know how it works
Just like bubble sort with an array except crappier.

>i hope that you could help me
The best way to bubble sort a linked list is to cheat by swapping the data instead of splicing the nodes:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void abc::sorting()
{
  Node *a, *b;
 
  a = b = head;
 
  while ( a->next->next != NULL ) {
    while ( b->next != NULL ) {
      if ( b->data > b->next->data ) {
        int save = b->data;
        b->data = b->next->data;
        b->next->data = save;
      }
 
      b = b->next;
    }
 
    a = a->next;
  }
}
void abc::sorting()
{
  Node *a, *b;

  a = b = head;

  while ( a->next->next != NULL ) {
    while ( b->next != NULL ) {
      if ( b->data > b->next->data ) {
        int save = b->data;
        b->data = b->next->data;
        b->next->data = save;
      }

      b = b->next;
    }

    a = a->next;
  }
}

Splicing nodes makes it ten times harder and less efficient, which is a feat for bubble sort since it sucks so much to begin with. Off the top of my head, it might look something like this:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void abc::sorting()
{
  Node *a, *b, *c, *e = NULL; 
  Node *save; 
 
  while ( e != head->next ) {
    c = a = head;
    b = a->next;
 
    while ( a != e ) {
      if ( a->data > b->data ) {
        if ( a == head ) {
          save = b -> next;
          b->next = a;
          a->next = save;
          head = b;
          c = b;
        }
        else {
          save = b->next;
          b->next = a;
          a->next = save;
          c->next = b;
          c = b;
        }
      }
      else {
        c = a;
        a = a->next;
      }
 
      b = a->next;
 
      if ( b == e )
        e = a;
    }
  }
}
void abc::sorting()
{
  Node *a, *b, *c, *e = NULL; 
  Node *save; 

  while ( e != head->next ) {
    c = a = head;
    b = a->next;

    while ( a != e ) {
      if ( a->data > b->data ) {
        if ( a == head ) {
          save = b -> next;
          b->next = a;
          a->next = save;
          head = b;
          c = b;
        }
        else {
          save = b->next;
          b->next = a;
          a->next = save;
          c->next = b;
          c = b;
        }
      }
      else {
        c = a;
        a = a->next;
      }

      b = a->next;

      if ( b == e )
        e = a;
    }
  }
}

I'm here to prove you wrong.

•

Join Date: Jul 2004

Posts: 65

Reputation: koh is an unknown quantity at this point

Solved Threads: 0

koh

Offline

Junior Poster in Training

Re: Link List Sorting Problem

Sep 3rd, 2005

thanks
but i found the way, yesterday..finally

, but from what u said, it is bad to use bubble sorting in linked list..

i tried to implement merge sorting, and insertion...but i find it..the codings were soooooo faaacinating...haha..(u know ..lazy for long typing..haha)

this is my coding using "bubble sort",
mind to give any comment(s) about my coding...thanks for the help. i'm glad to learn from you.

void abc::sorting()
{
Node *cur = head;
cur = cur->next;
int hold;
int i = 0;

for( ; i < SIZE ; i++)
{
for(Node *pvr = head; cur != NULL; cur=cur->next , pvr = pvr ->next)
{
if(pvr->num > cur->num)
{
hold = pvr->num;
pvr->num = cur->num;
cur->num = hold;
}
}
cur = head;
cur=cur->next;
pvr=head;
}
}