Как отсортировать список с помощью вставки сортировки с использованием этого кода в C?

Question

У меня небольшие проблемы с упорядочением указанных значений.Прямо сейчас, входной файл:

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

Но я получаю:

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

Как бы я отсортировал их, используя мой код в Insert () в порядке возрастания?

#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;
}

Любая помощь будет оценена.Спасибо!

Answer 1

вставка сортировки

и вот пример с той же веб-страницы:

/* 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; 
   } 

}

Answer 2

Вы вставляете каждый элемент в начало списка, поэтому они располагаются в обратном порядке, в котором вы их читали.Это не то, что является сортировкой вставки.

Когда вы вставляете в список, вам нужно расположить новый элемент в правильном порядке.Когда вы находите такой узел, что новое значение больше значения текущего узла, но меньше значения следующего узла, вы вставляете новый узел между текущим узлом и следующим узлом.

Если он меньше, чем головной узел, сделайте его новой головой.Если он больше, чем конечный узел, поместите его в конец.