Bubble sort a linked list with one pointer

Question

I'm trying to bubble sort a linked list with one pointer, p_previous. The pointer is supposed to look ahead one node and also look ahead two nodes, and if the first is greater than the second, they are to be switched using a temporary variable while p_previous stays out of the swap. p_previous should also check down two nodes to see if the list trailer is there, stopping the sort. I honestly have no clue what I am doing when it comes to bubble sorts, and the linked list implementation isn't helping.

Here is some code:

int sort_list(ID_NUMBER *p_list, int list_count)
{
    ID_NUMBER *p_previous = p_list; /* Previous node, use to swap next */
    ID_NUMBER *p_temp;              /* Temporary variable              */
    int count;                      /* Counts number of nodes passed   */

    for(count = 0; count < list_count; count++)
    {
        while(p_previous->p_next_student->p_next_student != NULL)
        {
        if(p_previous->p_next_student->student_id >
                p_previous->p_next_student->p_next_student->student_id)
        {
            p_temp = p_previous->p_next_student->p_next_student;
            p_previous->p_next_student = p_temp->p_next_student;
            p_temp = p_previous->p_next_student;
            p_previous->p_next_student = p_temp;
        }
        p_previous = p_previous->p_next_student;
        }

    }
    return 0;
}

Here is what I know.

If this is my list as entered.

H-->1-->3-->2-->4-->T

1 and 3 are already in order, move p_previous down.

3 and 2 are out of order, make the temp variable point to 2.

Make 3 point to the number 4.

Make 2 point to the number 3.

Make 1 point to the number 2.

I think thats how I'm supposed to do it, I just don't know how to put it into code. I am pretty sure a while loop inside a for loop inside is all that is necessary.

If someone could help, that would be great.

Also, if you need more information, just ask.

This will seg fault if your list is size 1. "p_previous->p_next_student->p_next_student" — 75inchpianist
– 75inchpianist, Commented Dec 5, 2013 at 17:50
@75inchpianist I have an if statement in main that checks for that by getting the length of the linked list from another function. — Jesse Upchurch
– Jesse Upchurch, Commented Dec 5, 2013 at 18:09
Probably is more elegant to put that if statement in the function itself. Your sort function should be able to take a list of any length so that it is portable. Something like : if(list_count < 2) return 0; — 75inchpianist
– 75inchpianist, Commented Dec 5, 2013 at 19:44

woolstar · Accepted Answer · 2013-12-05 22:43:28Z

There's several fundamental problems here ( like you can't change the first item in the list), but the most basic one is your swap:

        p_temp = p_previous->p_next_student->p_next_student;
        p_previous->p_next_student = p_temp->p_next_student;
        p_temp = p_previous->p_next_student;
        p_previous->p_next_student = p_temp;

So lets say we have three items, we'll call them A B C. And we want A C B. Right now you start off doing:

p_previous = A
p_temp = A->next->next = C

This is going the wrong way. We're going to point A->next at C. The problem is, when we do that we'll lose B. p_temp should store B.

p_temp = A->next = B
p_previous->next= p_previous->next->next = C
p_temp->next= p_previous->next->next = {whatever came after}
p_previous->next->next= p_temp = B

Then you just have to deal with the other issues, like crashing when your list has only one item.

Also you may want to do this:

for(count = 0; count < list_count; count++)
{
  p_previous = p_list;

So that you go through the list bubbling values N times, instead of just once.

Collectives™ on Stack Overflow

Bubble sort a linked list with one pointer

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related