DaniWeb Forum Index > Software Development > C

C RSS

Implementing a Sorting Algorithm into a Linked List Insert Function

•

Join Date: Sep 2008

Posts: 12

Reputation: ahspats is an unknown quantity at this point

Solved Threads: 0

ahspats

Offline

Newbie Poster

Implementing a Sorting Algorithm into a Linked List Insert Function

Jan 16th, 2009

I'd like to implement a sorting algorithm(quicksort or bubblesort or mergesort... it doesn't matter. anything that sorts is ok) into my insert function, so that everytime i create a new element it'll be inserted into right position. The variable listptr is the pointer pointing to the address of the first element of the list, val is value according to which the sorting should be done and next is pointer pointing to position of next element of the list.

Could someone help me with this???

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
liste_t* Insert (liste_t *listptr, int val) {
 
    liste_t *lp = listptr;
 
    if (listptr != 0) {
		while (listptr->next != 0){
			listptr = listptr->next;
		}
		listptr->next = (struct liste_t *) malloc (sizeof(liste_t));
		listptr = listptr->next;
		listptr->next = 0;
		listptr->Zahl = val;
		printf("\n");
		return lp;
    }
    else {
		listptr = (struct liste_t *) malloc (sizeof(liste_t));
		listptr->next = 0;
		listptr->Zahl = val;
		printf("\n");
		return listptr;
    }
}
liste_t* Insert (liste_t *listptr, int val) {

    liste_t *lp = listptr;

    if (listptr != 0) {
		while (listptr->next != 0){
			listptr = listptr->next;
		}
		listptr->next = (struct liste_t *) malloc (sizeof(liste_t));
		listptr = listptr->next;
		listptr->next = 0;
		listptr->Zahl = val;
		printf("\n");
		return lp;
    }
    else {
		listptr = (struct liste_t *) malloc (sizeof(liste_t));
		listptr->next = 0;
		listptr->Zahl = val;
		printf("\n");
		return listptr;
    }
}

Last edited by ahspats; Jan 16th, 2009 at 9:11 pm.

•

Join Date: Sep 2008

Posts: 1,563

Reputation: BestJewSinceJC is a name known to all

Solved Threads: 196

BestJewSinceJC BestJewSinceJC is offline

Offline

Posting Virtuoso

Re: Implementing a Sorting Algorithm into a Linked List Insert Function

Jan 16th, 2009

That doesn't make sense. Maintain a sorted linked list by making sure that every time you do an insert, it is inserted in sorted order. No need for a sorting algorithm.

•

Join Date: Sep 2008

Posts: 146

Reputation: devnar will become famous soon enough

Solved Threads: 16

devnar

Offline

Junior Poster

Re: Implementing a Sorting Algorithm into a Linked List Insert Function

Jan 17th, 2009

As mentioned before, it makes more sense to make sure that the list is in order while inserting than to apply a sorting algorithm later.

You can try this:

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
liste_t* Insert (liste_t *listptr, int val) 
{
 
    liste_t *lp = listptr;
    liste_t *prev = NULL;
    liste_t *info = (struct liste_t *) malloc (sizeof(liste_t));
    info->Zahl = val;
    info->next = NULL;
 
    if (listptr != 0) 
    {
		while (listptr != 0 && listptr->Zahl < val)
		{
		    prev = listptr;
		    listptr = listptr->next;
		}
 
		prev->next = info;
		info->next = listptr;
liste_t* Insert (liste_t *listptr, int val) 
{

    liste_t *lp = listptr;
    liste_t *prev = NULL;
    liste_t *info = (struct liste_t *) malloc (sizeof(liste_t));
    info->Zahl = val;
    info->next = NULL;

    if (listptr != 0) 
    {
		while (listptr != 0 && listptr->Zahl < val)
		{
		    prev = listptr;
		    listptr = listptr->next;
		}
		
		prev->next = info;
		info->next = listptr;

•

Join Date: Aug 2006

Posts: 319

Reputation: Luckychap is on a distinguished road

Solved Threads: 42

Luckychap

Offline

Posting Whiz

Re: Implementing a Sorting Algorithm into a Linked List Insert Function

Jan 17th, 2009

In both the code above head of the list is changed, which is wrong!

Check this out:

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
liste_t* Insert (liste_t *listptr, int val)  {
	liste_t *tempHead =  listptr;
	liste_t *pre;
 
	liste_t *newNode =  (struct liste_t *) malloc (sizeof(liste_t));
	newNode->val = val;
	newNode->next = NULL;
 
	//if list is empty then make newNode as head
	if(tempHead == NULL) {
		listptr = newNode;
		return listptr;
	} else {
		pre = NULL;
		// if list is not empty loop through all the nodes
		while(tempHead != NULL && tempHead->val < val) {
			pre = tempHead;
			tempHead = tempHead->next;
		}
 
		// if only one node is there
		if(pre == NULL) {
			// insert new nofde on top making newNode as head
			newNode->next = tempNode;
			listptr = newNode; // now head points to newNode at top
		} else {
			// insert newNode between pre and tempHead (current)
			pre->next = newNode;
			newNode->next = tempHead;
		}	
		return listptr;
	}
}
liste_t* Insert (liste_t *listptr, int val)  {
	liste_t *tempHead =  listptr;
	liste_t *pre;
	
	liste_t *newNode =  (struct liste_t *) malloc (sizeof(liste_t));
	newNode->val = val;
	newNode->next = NULL;
	
	//if list is empty then make newNode as head
	if(tempHead == NULL) {
		listptr = newNode;
		return listptr;
	} else {
		pre = NULL;
		// if list is not empty loop through all the nodes
		while(tempHead != NULL && tempHead->val < val) {
			pre = tempHead;
			tempHead = tempHead->next;
		}
		
		// if only one node is there
		if(pre == NULL) {
			// insert new nofde on top making newNode as head
			newNode->next = tempNode;
			listptr = newNode; // now head points to newNode at top
		} else {
			// insert newNode between pre and tempHead (current)
			pre->next = newNode;
			newNode->next = tempHead;
		}	
		return listptr;
	}
}