CODEWITHSUNDEEP
csortinglinked-list
Ryan
Ryan

Reputation: 311

Bubble sorting in double-linked list leading to trying to read from NULL

I am trying to code bubble sort to order a linked list by comparison. The problem is that, at some point, the bubble sort function sends a NULL pointer to the comparison function, which leads to a runtime error. Specifically, the last item of the list points to NULL.

The idea is to do the first iteration seperately. This way I can get the number of times the list is compared at the first time; then, I can use this number to continue sorting in a different loop.

Here is the code. Thanks for the help.

void SortItemList(Item* ptrFirstItem, 
                  int(*compare)(const Item*,const Item*))
{
  Item* currentItem=ptrFirstItem;
  Item* nextItem;
  int itemSize=0;
  int i,j;

  //in case no items or just one
  if (currentItem==NULL || currentItem->nextItem==NULL)
    return;
  else
    {
      //first iteration also checking how many items to compare
      nextItem=currentItem->nextItem;
      while(nextItem!=NULL)
        {
          itemSize++;

          if(compare(currentItem, nextItem)>0)
            swapItems(currentItem, nextItem);

          currentItem=nextItem;
          nextItem=nextItem->nextItem;
        }
      itemSize--;

      for(i=0;i<itemSize;i++)
        {
          currentItem=ptrFirstItem;
          nextItem=currentItem->nextItem;

          for(j=0;j<itemSize-i;j++)
            {
              if(compare(currentItem, nextItem)>0)
                swapItems(currentItem, nextItem);

              currentItem=nextItem;
              nextItem=nextItem->nextItem;
            }
        }
    }
return;
}

Upvotes: 2

Views: 54

Answers (3)

Jasen
Jasen

Reputation: 12432

the first problem is the function:

void SortItemList(Item* ptrFirstItem, 
                  int(*compare)(const Item*,const Item*))

that's not going to work. you need to be able to write to ptrFirstItem

void SortItemList(Item** ptrptrFirstItem, 
                  int(*compare)(const Item*,const Item*))

and swap needs that ability too.

Upvotes: 2

Jigar
Jigar

Reputation: 300

Clarification for the NPE problem @Ryan Suppose if we have a sorted list and itemsize is 4 i.e index from 0 to 3. So 'i' will loop from 0 to 3. So for i = 0, 'j' will loop from 0 to 4 - 0 = 4. So when 'i' = 0 currItem is pointing to 0th element and nextItem points to 1st element. Now j will loop from 0 to 3. for j = 0 as list is sorted so there is no swapping. so now currentItem will point to 1st element and nextItem will point to 2nd element. For j = 1 at the end currentItem will point to 2nd element and nextItem will point to 3rd element. For j = 2 at the end currentItem will point to 3rd element and nextItem will point to 4th element. As 4th is null element so now nextItem has null value.for for j = 3 at the end currentItem will point to 4th element and nextItem will result into NPE as null.nextItem will result into NPE

Upvotes: 0

chux
chux

Reputation: 154127

Certainly the following is a problem. Although the DL list is updated, the local values of currentItem and nextItem are not. This needs to change when a swap occurs. 

if(compare(currentItem, nextItem) > 0) 
  swapItems(currentItem, nextItem);

currentItem = nextItem;
nextItem = nextItem->nextItem;

Maybe

if(compare(currentItem, nextItem) > 0)  {
  swapItems(currentItem, nextItem);
  // No need to update currentItem, it is all ready the next item.
} else {
  currentItem = nextItem;
}

nextItem = nextItem->nextItem;

Upvotes: 3

Related Questions