How to sort a list using insertion sort using this code in C?

Question

I am having a little trouble ordering the given values. Right now, the input file is:

347 490 950 779 911 825 215 584 355 266 301 458 381 13 577 835

But I am getting:

835 577 13 381 458 301 266 355 584 215 825 911 779 950 490 347

How would I sort these using my code in Insert() in ascending order?

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

// Node for building our linked list.
struct NodeTag {
  int value;
  struct NodeTag *next;
};

typedef struct NodeTag Node;

Node *insert( Node *head, int val )
{
  Node *n = (Node *)malloc(sizeof(Node)); 
  n->value = val;
    n->next = head;
      return n;
}

int main()
{
  Node *head = NULL;

  int x;
  while ( scanf( "%d", &x ) == 1 ){
    head = insert( head, x );
  }

  for(Node *n = head; n; n = n->next) {
     printf("%d ", n->value);
  }

  printf("\n");

  while(head) {

   Node *next = head->next;
     free(head);
        head = next;
   }
   return 0;
}

Any help would be appreciated. Thank you!

Notice that you never used the value of the nodes in any way except for printing them out. Think about it. How could you possibly sort a list without reading the values? — user9254539
– user9254539, Commented Mar 2, 2019 at 6:17

dbush · Accepted Answer · 2019-03-02 05:32:21Z

4

You're inserting every element at the head of the list, so they're ordered in the reverse order you read them. That's not what an insertion sort is.

When you insert into the list, you need to put the new element in the correct order. When you find a node such that the new value is greater than the current node's value but less than the next node's value, you insert the new node between the current node and the next node.

If it's less than the head node, make it the new head. If it's greater than the end node, put it at the end.

answered Mar 2, 2019 at 5:32

dbush

233k27 gold badges261 silver badges334 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

AHunt Over a year ago

Yes, I know about the logic behind it, but the trouble I am having is how to do it in code. That is the part that is really confusing me. Any help would be appreciated for that part.

dbush Over a year ago

@AHunt You already know how to walk the list since you're already doing that when you print it. You just need to check the values along the way. Then when you find the right spot, point the new node to the next node and point the current node to the new node.

AHunt Over a year ago

Shouldn't the sorting be in the Insert() function?

dbush Over a year ago

@AHunt yes, exactly

user3629249 · Accepted Answer · 2019-03-03 01:46:53Z

0

insertion sort

and here is the example from that same web page:

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n) 
{ 
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = arr[i]; 
       j = i-1; 

       /* Move elements of arr[0..i-1], that are 
          greater than key, to one position ahead 
          of their current position */
       while (j >= 0 && arr[j] > key) 
       { 
           arr[j+1] = arr[j]; 
           j = j-1; 
       } 
       arr[j+1] = key; 
   }

}

answered Mar 3, 2019 at 1:46

user3629249

16.6k1 gold badge18 silver badges17 bronze badges

Collectives™ on Stack Overflow

How to sort a list using insertion sort using this code in C?

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related