insertion sort doubly linked list

Question

I'm trying to do an insertion sort on a doubly linked list in C. in this state, my code gets me stuck in an non-ending loop spitting out 8s and 9s.

can someone please be kind enough to explain how the "insertionSort" method is supposed to be designed?

my linked list is designed containing head, previous, next and some data.

Here is my code so far

My hope is NULL. please help.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

int data;
struct Node* next;
struct Node* previous;

}Node;

struct Node* head = NULL;
struct Node* current = NULL;
struct Node* headsorted = NULL;
int l = 0;
int empty = 1;
int length = 0;
int change = 0;

void InsertSort(){

Node* temp = (Node*)malloc(sizeof(struct Node));

temp = head;
current = head->next;

printf("\nInsert Sort begins...\n");

if (head != NULL && head->next != NULL)
{
   for (int i = 1; i < length; i++)
   {
        while(current->data > current->next->data && current->next != NULL && current != NULL)
        {
            temp = current;
            current = current->next;
            current->next = temp;
        }
   }
}
else
{
printf("\nList Error!\n");
}

temp = NULL;

}

void Insert(int x)
{
    Node* temp = (Node*)malloc(sizeof(struct Node));

    temp->data = x;
    temp->next = head;
    temp->previous = NULL;

   if (head != NULL)
   {
       head->previous = temp;
   }
    head = temp;
}

void Print(){

    struct Node* temp = head;
    printf("List is: ");
    while(temp != NULL)
    {
        printf(" %d", temp->data);
        temp = temp->next;
    }
}

int main()
{
    head = NULL;
    FILE * file = fopen("List.txt", "r");

    fscanf(file, "%d", &l);
    while (!feof (file))
    {
        Insert(l);
        fscanf(file, "%d", &l);
        length++;
    }
    fclose(file);

    Print();

    printf("\n\n\n");

    printf("data: %d next: %d   " , head->data, head->next->data);

    InsertSort();

    Print();

    return 0;
}

I don't think so, @purec. It looks like the malloc() in InsertionSort() is a red herring. That function just leaks memory. — John Bollinger
Oddly enough, @TuğberkKaanDuman, this use of while (!feof (file)) is the exception. Or at least, it doesn't match the always-wrong pattern. This is because the first read of the file is lifted out to just before the loop, resulting in the feof() test in the loop condition actually being sensible. For clarity, though, I would move the in-loop fscanf() call to be the loop's last statement. — John Bollinger

John Bollinger John Bollinger · Accepted Answer · 2018-05-25T15:43:04

can someone please be kind enough to explain how the "insertionSort" method is supposed to be designed?

In the first place, I suggest getting rid of the length variable, or at least not using it in your sort routine. It is not needed, and relying on it may be diverting your thinking too much toward array-style implementations. You know you've reached the end of the list when you discover a node whose next pointer is NULL.

Secondly, I reiterate my comment that you are not performing node swaps correctly for a doubly-linked list. A node swap on any linked list, whether singly- or doubly-linked, is equivalent to extracting the second node from the list altogether, then reinserting it before the first. In a singly-linked list that affects, in general, three nodes: in addition to the two being swapped, the predecessor to the first. In a doubly-linked list, it also affects the successor to the second. That's messy enough in the doubly-linked case that I suggest structuring it explicitly as an excision followed by an insertion.

But I also suggest that you take a step back and look at the algorithm from a high level. It works by considering each node in turn, starting with the second, and if necessary removing it and reinserting it at its correct position in the (sorted) sublist preceding it. So what, then, does pairwise swapping even have to do with it? Nothing. That's a detail convenient in implementing such a sort on an array, but it makes needless work when sorting a linked list.

For a linked list, especially a doubly-linked one, I suggest an implementation cleaving more directly to the abstract description of the algorithm:

Maintain a pointer, S, to the last node of the sorted leading sublist. Initially, this will point to the list head.
If S points to the last node (which you can judge by S->next) then stop.
Otherwise, check whether *N, the successor to *S, is correctly ordered relative to *S.
- If so, then set S (the pointer, not its referrent) equal to N.
- If not, then
  - cut the *N from the list (updating both its predecessor and its successor, if any, appropriately), and
  - step backward through the sorted sublist until you reach either the first node or one whose predecessor should precede *N, whichever is encountered first.
  - Insert *N before the node you've discovered.
  - If that makes *N the list head (which you can judge by the new value of its previous pointer), then set the head pointer (not its referrent) equal to N.
repeat from point 2

The actual code is left as the exercise it is intended to be.

insertion sort doubly linked list

1 Answers