C - Problem Bubble sorting linked list

[Nature1]

Hello,

I'm having problems sorting a linked list alphabetically. The link list is being correctly populated but it seems that the bubblesort() function is implemented incorrectly. When I read the following textfile:
apple tree house.
the output after bubblesort() is:
apple --> house --> tree --> NULL
No problems there. But when I try the following text:
house dog tree friend.
the output is:
house --> tree --> NULL

After trying dozens of different wordcombinations I can't seem to find a pattern in why it would sort incorrectly. Again the linked list is printed correctly before sorting.

The main function and 'd' is left out as it's not used in bubblesort().

Any thoughts?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Linkedlist.h"
#include "prototypes.h"

struct Nodes {
   char *data;
   struct Nodes *nextPtr; /* pointer to next structure */
};

typedef struct Nodes NODES;
typedef NODES *NODESPTR;

void insert(NODESPTR *, char *);
void printList(NODESPTR);
NODESPTR bubblesort(NODESPTR);
int isChar(char);
void linkedList();

void linkedList(){

    d.count = 0;
    NODESPTR startPtr = NULL;

    d.c = fgetc(d.fileDocument);
    printf("processing file...\n\n");

    while ((d.d = fgetc(d.fileDocument)) != EOF) {

          /*If two lines in a row*/
          if ((d.c == '\n') && (d.d == '\n')) {
			}

          /* if not two non-characters in a row */
		  else if ((isChar(d.c) == 0) && (isChar(d.d) == 0)) {
		       d.c = d.d;
		  }

          /* if c and d are both characters */
		  else if ((isChar(d.c) == 1) && (isChar(d.d) == 1)) {
		      d.word[d.count] = tolower(d.c);
			  d.c = d.d;
			  d.count++;
          }

            /* if c is character and d is space, return, tab, or new line */
          else if ((isChar(d.c) == 1) && (isChar(d.d) == 0)) {
		      d.word[d.count] = d.c;
		      d.word[++d.count] = '\0';

			  char *newword = malloc(strlen(d.word)+1);
			  strcpy(newword, d.word);
			  insert(&startPtr, newword);

			  d.c = d.d;
			  d.count = 0;
          }

          /* if d is start of new word */
		  else if ((isChar(d.d) == 1) && (isChar(d.c) == 0)) {
		      d.c = d.d;
          }
    }
  fclose(d.fileDocument);
  printList(startPtr);
  bubblesort(startPtr);
  printList(startPtr);

}

void insert(NODESPTR *sPtr, char *value)
{
   NODESPTR newPtr, previousPtr, currentPtr;

   newPtr = malloc(sizeof(NODES));


   if (newPtr != NULL) {    /* is space available */
   	  newPtr->data = malloc(sizeof(value));
   	  newPtr->data = value;
      newPtr->nextPtr = NULL;

      previousPtr = NULL;
      currentPtr = *sPtr;

      while (currentPtr != NULL && value > currentPtr->data) {
         previousPtr = currentPtr;
         currentPtr = currentPtr->nextPtr;  /* walk to next node */
      }

      if (previousPtr == NULL) {    /* if the list is empty, create the first node */
         newPtr->nextPtr = *sPtr;
         *sPtr = newPtr;
      }
      else {
         previousPtr->nextPtr = newPtr;
         newPtr->nextPtr = currentPtr;
      }
   }
   else
      printf("%s not inserted. No memory available.\n", value);
}

NODESPTR bubblesort(NODESPTR list)
{
    NODESPTR lst, tmp = list, prev, potentialprev = list;
    int idx, idx2, n = 0;

    /*nr of nodes*/
    for (;tmp->nextPtr; tmp=tmp->nextPtr)
    {
        n++;
    }

    for (idx=0; idx<n-1; idx++)
    {
        for (idx2=0,lst=list; lst && lst->nextPtr && (idx2<=n-1-idx); idx2++)
        {
            if (!idx2)
            {
                /*at beginning, treat start
                node as prev node*/
                prev = lst;
            }

            /*compare two nodes*/
            if ( strcmp ( lst->data, lst->nextPtr->data ) == 1 )
            {
                /*swap nodes*/
                tmp = (lst->nextPtr?lst->nextPtr->nextPtr:0);

                if (!idx2 && (prev == list))
                {
                    /*do not have any special sentinal nodes
                    so change beginning of the list to point
                    to the smallest swapped node*/
                    list = lst->nextPtr;
                }
                potentialprev = lst->nextPtr;
                prev->nextPtr = lst->nextPtr;
                lst->nextPtr->nextPtr = lst;
                lst->nextPtr = tmp;
                prev = potentialprev;
            }
            else
            {
                lst = lst->nextPtr;
                if(idx2)
                {
                    /*just keep track of previous node, for swapping nodes this is required*/
                    prev = prev->nextPtr;
                }
            }
        }
    }
    return list;
}

/* Print the list */
void printList(NODESPTR currentPtr)
{
   if (currentPtr == NULL)
      printf("List is empty.\n\n");
   else {
      printf("The list is:\n");

      while (currentPtr != NULL) {
         printf("%s --> ", currentPtr->data);
         currentPtr = currentPtr->nextPtr;
      }

      printf("NULL\n\n");
   }
}

[Nature1]

ok... found the pattern. It seems that the first two chars of the first word are set as some kind of limit. If one of the following words begins with two chars =< then the first two chars of the first word the output gets scrambled. Example:
appel tree pie
works out fine:
appel --> pie --> tree --> NULL
But with this:
appel aapel tree pie.
I get:
appel --> pie --> tree --> NULL
If corrected:
appel aqpel tree pie. (Notice the 'q' in 'aqpel' is higher than the 'ap' in 'appel')
It's ok again:
appel --> aqpel --> pie --> tree --> NULL

My brains hurt -_-

[Nature1]

Still can't fix it though... does anyone have an idea on how to solve this?

[ioctl]

First of all: to me your function looks overly complicated and has some redundant variables. A more simplistic approach along the lines of:

/* Quick'n dirty pseudo code */
bubblesort()
{
  while(swapped) {
    swapped = false;
    for(list; list != end; list++) {
      if(firstIsLower) {
        swap;
        swapped = true;
      }
    }
  }
}

would do IMO.

That beeing said your problem seems to be that you are not updating startPtr with the returnvalue of bubblesort(). Your just printing the initial list root.

- Andreas

[Nature1]

Aw crap, I feel like a retard... Thx man you helped me out big time. I'll take a look at simplifying the function, it will be good practice because I still suck at linked lists.