Link List Sorting Problem

[kohkohkoh]

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 :sad: . i tried using the elements, just like in bubble sort,
for example:

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:

#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 >>

[Narue]

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.

[kohkohkoh]

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

[Narue]

>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:

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:

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

[kohkohkoh]

thanks
but i found the way, yesterday..finally :cool: , 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;
}
}