CareerCup

Look like that we can map the linklist to an arrary, then use bubble sort for array.

The point of the question seems to be to judge how well you write linked list manipulation code.

If we are dumping to an array, we might as well QuickSort or something better than bubble sort.

// preprocessor directives
# include <iostream>
# include <string>

using namespace std;

// class nodeType
class nodeType
{
// class members
public:
char fName[ 15 ];
char lName[ 15 ];
nodeType *next;

};

int main()
{
// all your declaration goes here
nodeType *head, *first, *next, *newNode, *temp1, *temp2;
char fn[ 15 ];
char ln[ 15 ];
char anyMore;


head = first = next = newNode = temp1 = temp2 = NULL;

do {
system ( "cls" );
// prompt and input first name and last name

cout << "\nEnter first name: ";
cin >> fn;

cout << "Enter last name: ";
cin >> ln;

newNode = new nodeType;

strcpy( newNode -> fName, fn );
strcpy( newNode -> lName, ln );

newNode -> next = NULL;

if ( head == NULL ) // list is empty
{
head = first = newNode;
}

else if ( strcmp( newNode -> lName, head -> lName ) < 0 ) // then insert before first one
{
newNode -> next = head;
head = newNode;
}
else
{

temp1 = head;

//start a search for right place, by checking the next one's last name
while (( strcmp( temp1 -> next -> lName, ln ) < 0 ) && ( temp1 -> next != NULL ))
{

temp1 = temp1 -> next;

}

newNode -> next = temp1 -> next;
temp1 -> next = newNode;

}



// now list the items
temp1 = head;

while ( temp1 != NULL )
{

cout << temp1 -> fName << " " << temp1 -> lName << endl;
temp1 = temp1 -> next;

}

// here prompt for an input to enter more (ie, anyMore Y/N)
cout << "\nEnter Y to input, or N to exit: ";
cin >> anyMore;

} while ( anyMore == 'Y' || anyMore == 'y' ); // end dowhile

system ( "pause" );

// all done;
}

// Sort list by swapping data around. 
List *BubbleSort(List *head)
{
   
  if (head == null) return;
  
  List *A = head->next;
  
  if (A == null) return;
  // Make head the minimum.
  while( A != null)
  {
    if (head->Data > A->Data)
    {
      Data tmp = head->Data;
      head->Data = A->Data;
      A->Data = tmp;  
    }
  }
  // Recurse on the rest of the list.
  BubbleSort(head->next);
}

void BubbleSort(LL * head)
{
	if (!head)
	{
		return;
	}
    
	LL *end = NULL;
	while (end != head->next)
	{
		LL *p = head;
		LL *q = head->next;
		LL *tmpend = NULL;
    
		while (q != end)
		{
			if (p->data > q->data)
			{
				int tmpData = p->data;
				p->data = q->data;
				q->data = tmpData;
			}
			tmpend = q;
			p = p->next;
			q = q->next;
		}
		end = tmpend;
	}
}

You idiot Ganga Narayana .. go and drown yourself in Ganga.. Is this Bubble Sort Idiot!!

This is not Bubble sort. In bubble sort you compare consecutive elements. LOLer has made that clear in above posts. Why do you have to do it again and again. Felt like killing you !!

bubblesort(node) {
if(node==null) return;
bubble(node);
bubblesort(node->next);
}

bubble(node) {
if(node==null) return;
if(node->next == null) return;
bubblecheck(node->next);
if(node->data > node->next->data) {
temp = node->data;
node->data = node->next->data;
node->next->data = temp;
}

Please ignore the previous post as the recursive call in "bubble" is typed wrongly as "bubblecheck"

bubblesort(node) {
  if(node==null) return;
  bubble(node);
  bubblesort(node->next);
}

bubble(node) {
  if(node==null) return;
  if(node->next == null) return;
  bubble(node->next);
  if(node->data > node->next->data) swapdata(node, node->next);
}

swapdata(node, node1) {
  temp = node->data;
  node->data = node1->data;
  node1->data = temp;
}

Sorting a link list by swapping the data around isn't a good idea as there may be other pointers currently point to the nodes. It's slightly more difficult to swap the actual nodes. Here's a try:

node * bubble_sort(node *list)
{
	node *sorted_list = list;
	node *temp;
	for (node *i=sorted_list; i!=NULL; i=i->next)
	{
		node *prev = NULL;
		for (node *j=sorted_list; j->next!=NULL; j=j->next)
		{
			if (j->data > j->next->data)
			{
				//swap
				temp = j->next;
				if (prev)
					prev->next = temp;
				else
				{
					//There is a new head of list
					sorted_list = temp;
					i = temp;
				}

				j->next = temp->next;
				temp->next=j;

				j=temp; //set back j iterator since a swap was done;
			}
			prev = j; //advance the prev ptr
		}
	}
	return sorted_list;
}

Bubble Sort on linked list is O(n3)

bubble(Node ** head){
Node *prevPos,*curPos,*nextPos;
bool SWITCHED = true;
if(SWITCHED){
SWITCHED = false;
curPos=prevPos=*head;
while(cur->next != NULL){
nextPos = curPos->next;
if(curPos->data > nextPos->data){
SWITCHED = true;
curPos->next = nextPos->next;
nextPos->next=curPos;
prevPos = other;
if(curPos==*head){
*head = nextPos;
}
}
else{
curPos = curPos->next;
prevPos = prevPos->next;
}
}


}
}

/* getLength() returns the length of list */

node *BubbleSort(node *start)
{
        node *prev, *orig = start, *temp;
        int i,len = getLength(start), swaps;
        while (len--)
        {
                swaps = 0; start = orig; prev = NULL;
                for (i=0;i<len;i++)
                {
                        if (start->data > start->next->data)
                        {
                                temp = start->next;
                                start->next = start->next->next;
                                temp->next = start;
                                if (prev)
                                        prev->next = temp;
                                else
                                        orig = temp;
                                start = temp;
                                swaps++;
                        }
                        prev = start;
                        start = start->next;
                }
                if (!swaps)
                        break;
        }
        return orig;
}

// Its bubble sort.... where you compare two values at the time and every pass you will push large data to the end of the list. and small data keeps coming up.

void BubbleSort(node *head) {
bool swapped = true;
node *cur;

while(swapped) {
swapped = false;
cur = head;

while(cur->next != NULL) {
if(cur->next->value > cur->value ) {
//swap values of cur and cur->next
swapped = true;
}
cur = cur->next;
}
}
}

Element *Bubblesort(Element **head)
{
	Element *curInner = *head; // current.
	Element *pre = null; // previous
	Element *end = null; //end of loop
	Element *newHead = *head; // new head to be returned.
	while(true)
	{
		curInner = newHead;
		if(curInner->next == end) //break when all outer loops are done.
		{
			break;
		}
		while(curInner->next != end)
		{
			if(curInner->data > curInner->next->data)
			{
				Element *temp1 = curInner->next;
				Element *temp2 = curInner->next->next;
				curInner->next = temp2;
				temp1->next = curInner;
				if(pre != null)
				{
					pre->next = temp1;	
				}
				if(curInner == newHead)
				{
					newHead = temp1;
				}
				pre = temp1;
			}
			else
			{
				pre = curInner;
				curInner = curInner->next;			
			}
		}
		end = curInner;
	}

	return newHead;
}

example 
round 1
p,e  c  
null 3->1->4->null
     h

e    p  c  
null 1->3->4->null
     n


   p  c  
1->3->4->null
n     e

round 2
p     c  
null  1->3->4->null
      n     e

p  c  
1->3->4->null
n     e