sorting linked lists with bubble sort

Question

Why doesn't this bubble sort implementation of sorting linked lists work?

It doesn't sort at all.The main problem area of the code is int the sort function. I have verified that the main works well and the last pointer(next) of the linked list is set to null before calling the sort function. The chain that links the lists should be linked within the if statement that is within the string comparison block and it should return the first link on the list, which would be called by the while statement to access all the members that would have been sorted out, but , it doesn't seem to be working.

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define NAME_SIZE 20

typedef struct record rec;
struct record
{
    char name[NAME_SIZE];
    int age;
    rec* next;
};

void getname(char* name);
rec* sort(rec**First,int i);/*we need to change the addresses they refer to */

int main(void)
{
    rec* Current = NULL;
    rec* Previous = NULL;
    rec* First = NULL;
    char check = '\0';
    int i = 0;

    for(; ;)
    {
        fflush(stdin);
        printf("\nDo you want to enter a%s record?(y/n): ", (check=='\0')?"":"nother");
        scanf("%c", &check);
        if(check == 'n')
            break;

        Current = (rec*)malloc(sizeof(rec));
        if(First == NULL)
        {
            First = Current;
        }
        if(Previous != NULL)
        {
            Previous->next = Current;
        }
        printf("\n");
        printf("\nPlease enter your name: ");
        getname(Current->name);
        printf("\nPlease enter your age: ");
        scanf("%d", &Current->age);
        Previous = Current;
        Current->next = NULL;
        i++;
    }

    Current = sort(&First, i);


    while(Current != NULL)
    {
        printf("\n%s is %d years old ", Current->name, Current->age);
        Current = Current->next;
    }

    return 0;
}

void getname(char *name)
{
    fflush(stdin);
    fgets(name, NAME_SIZE, stdin);
    int length = strlen(name);
    if(name[length - 1] == '\n')
        name[length -1 ] = '\0';
    return;
}


rec* sort(rec** first, int numbers)
{
    rec* pTemp1 = NULL;
    rec* pTemp2 = NULL;
    rec* Temp_first = *first;

    for(int j = 0; j < numbers; j++)
    {
        pTemp1 = *first;
        if(((*first) = (*first)->next)==NULL)
        {/*if end is reached, then break;*/
            break;
        }

        if(strcmp((*first)->name, ((*first)->next->name)) > 0)
        {


            if(((*first)->next) != NULL)
            {
                printf("\n***XXX***Entered***XXX");
                pTemp2 = (*first)->next;
                (*first)->next = pTemp1;
                pTemp1->next = pTemp2;
            }
        }

    }

    return Temp_first;

}

(Omitted freeing up memory for concise). Input

atest  
aatest  
btest  
abtest

and the output isn't sorted:

atest  
aatest  
abtest

I strongly suspect your bubble sort code is wrong. Where is the inner loop for list passes? — Rohan Kumar, Apr 30 '17 at 06:51
@AjayBrahmakshatriya, It seems to be ok on my system. I did check out the doc though it says undefined behaviour, it's working quite ok on my system. — lind, Apr 30 '17 at 06:56
why not just swap `name` and `age` instead of the whole node? If you are changing the positions of nodes, the whole structure gets changed. — Cherubim, Apr 30 '17 at 06:59
1) Your `sort` function doesn't implement bubble sort. See https://en.wikipedia.org/wiki/Bubble_sort 2) Your `sort` function may destroy your list as you don't handle the first element as a special case — Support Ukraine, Apr 30 '17 at 07:09
@Cherubim, I'm just trying to swap the pointers that points to each node, that would appear to sort them when accessed from the first node, and their position remain unchanged. — lind, Apr 30 '17 at 07:09
@4386427, it does compare adjacent members and swaps their position, what is different from bubble sort? — lind, Apr 30 '17 at 07:11
@lind You need to keep on doing that until no swap was need in a whole loop. — Support Ukraine, Apr 30 '17 at 07:28
@4386427, that's why I'm using the for, and checking if it reaches the last block — lind, Apr 30 '17 at 08:05

score 0 · Accepted Answer · answered Apr 30 '17 at 07:13

I think you're doing it wrong in the bubble sort function, You seem to be doing repeating the adjacent comparison of the list N times, which is okay but you're only doing comparison for the first two elements of the list. Recall that bubble sort is an O(N^2) algorithm. You need to put that adjacent elements checking into another loop.

Moreover, you can optimize it a bit by changing the outer loop to be dependent on a bubble sort variant which continues the passes till there are no inversions in the list anymore. I changed your bubble sort method according to my style and i was able to see the desired output:

rec* sort(rec** first, int numbers)
{
    int bSwap = 0;
    if(*first == NULL || (*first)->next == NULL)
      return;

    // outer loop for iterating till list is sorted
    while(!bSwap) {
      // iterating over the list comparing and
      // swapping adjacent elements
      rec *curNode = *first;
      rec *prev = *first;
      rec *fwd = (*first)->next;
      bSwap = 1;

      while(fwd) {
        int cmp = strcmp(curNode->name, fwd->name);

        if(cmp > 0) { // inversion found, swap and proceed forward
          if(curNode == *first)
            *first = fwd;
          else
            prev->next = fwd;

          curNode->next = fwd->next;
          fwd->next = curNode;
          prev = fwd;
          fwd = curNode->next;
          bSwap = 0;
        }
        else { // proceed forward
          curNode = prev->next;
          prev = fwd;
          fwd = fwd->next;
        }
      }

    }
    return *first;
}

Here's what i get when i run it:

~/Documents/src : $ ./a.out 

Do you want to enter a record?(y/n): y


Please enter your name: Rohan

Please enter your age: 22

Do you want to enter another record?(y/n): y


Please enter your name: Hema

Please enter your age: 20

Do you want to enter another record?(y/n): y


Please enter your name: Asanala

Please enter your age: 31

Do you want to enter another record?(y/n): n

Asanala is 31 years old 
Hema is 20 years old 
Rohan is 22 years old

I hope this helps.

What is this mathematical statement you've mentioned above: "0(N^2) algorithm"? — lind, Apr 30 '17 at 08:08
Read http://stackoverflow.com/questions/11477743/why-is-bubble-sort-on2 — Rohan Kumar, Apr 30 '17 at 08:09
there must be some mistake in your code, it does not sort long lists, ex. I entered 7 entries in here, but only gave me three(: http://pasteboard.co/4pPrbGaP2.png) — lind, May 10 '17 at 02:03

sorting linked lists with bubble sort

1 Answers1