Ad:

C Discussion Thread
Unsolved
Views: 3145

Jan 16th, 2009

Implementing a Sorting Algorithm into a Linked List Insert Function

Expand Post »

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

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.

ahspats

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

17 posts
since Sep 2008

Permalink

Jan 16th, 2009

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

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.

BestJewSinceJC

Reputation Points: 874

Solved Threads: 352

Posting Maven

Offline

2,758 posts
since Sep 2008

Permalink

Jan 17th, 2009

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

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:

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;

devnar

Reputation Points: 124

Solved Threads: 18

Junior Poster

Offline

148 posts
since Sep 2008

Permalink

Jan 17th, 2009

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

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

Check this out:

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

Luckychap

Reputation Points: 83

Solved Threads: 61

Posting Pro in Training

Offline

442 posts
since Aug 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: help to write a function

Next Thread in C Forum Timeline: exchange 2 variables values without using 3rd variable.

DaniWeb Message

Cancel Changes

User Name
Password