CODEWITHSUNDEEP
cpointerslinked-listsegmentation-faultinsertion-sort
Cody
Cody

Reputation: 3

Insertion Sort with Linked List Pointers in C

Disclaimer: I am a very novice programmer so if this question is stupid I do apologize. With the recent shutdown of universities I can no longer ask my TA's for help so the internet is the next best thing.

I've been having some issues working with linked lists - mainly sorting the values with a secondary pointer using insertion sort.

The list is generated with numbers using the 'next' pointer indicating direction, I'm attempting to sort the list by the randomly generated value held in each element, with the 'sort1' pointer indicating the sorted lists order.

The problem area in the code seems to be this while loop: 

while(new->value >= current->value && current != NULL){
    current = current->sort1;
}

its used to go through the elements that are already sorted and find where the 'new' element should be placed, but I'm getting a segmentation fault error here, I believe when it reaches the end of the list, and the new element should be placed at the end of the list so the 'current' pointer points to null.

Any insight? TIA!

The test code, for reference: 

int main(){

    int i, length;
    Node *head, *current, *new, *sorthead;

    head = NULL;
    sorthead = NULL;
    length = 5;

    //create linked list
    for(i=0;i<length; i++){

        new = (Node*) malloc(sizeof(Node));

        new->value = (int)rand_double(0,10);
        new->sort1 = NULL;

        new->next = head;
        head = new;
    }   

    //print list
    current = head;
    while(current != NULL){
        printf("<  %d  >\n", current->value);
        current = current->next;
    }

    //sort with sort 1
    new = head;
    while(new!=NULL){

        if(sorthead == NULL || new->value < sorthead->value){
            new->sort1 = sorthead;
            sorthead = new;
        }
        else{
            current = sorthead;

            while(new->value >= current->value && current != NULL){
                current = current->sort1;
            }
            new->sort1 = current;
            current->sort1 = new;

        }
       new=new->next;
    }

    //print sorted
    current = sorthead;
    while(current != NULL){
        printf("<  %d  >\n", current->value);
        current = current->sort1;
    }

    return 0;
}

Upvotes: 0

Views: 157

Answers (1)

Beta
Beta

Reputation: 99094

Consider this loop:

while(new->key1 < current->key1 || current->sort1 == NULL){
    current = current->sort1;
}

If the first comparison is always true (i.e if the "new" node's key is less than any value already in the sorted list), then the loop will reach a node whose sort1 is null, set current equal to NULL, and then dereference it in the next pass -- Undefined Behavior, seg-fault if you're lucky.

The correction to the conditional is straightforward, but I think it's important that you work it out for yourself.

Upvotes: 1

Related Questions