sorting a linked list using another list

Question

So i'm attempting to sort a linked list of integers but cant seem to figure out the right way to do it, my idea was to take the unordered list, find the largest value from it, and put it into another list. Since I don't believe I could delete the node from the original list without it being doubly linked I had planned to give the node from list 1 a zero value, thereby removing its status as the largest value. Because of this I intended to run it a set number of times, each time finding the next largest value until list 1 is all 0's and list 2 is an ordered version of what list 1 once was. I have created a function to do this but it doesn't seem to be working, although I cannot find a problem.

Functions

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

struct num_node *create(struct num_node *list, int x){
    struct num_node *current;

    if (list == NULL){
        list = (struct num_node*)malloc(sizeof(struct num_node));
        list->num = x;
        list->next = NULL;
        return(list);
    }
    else{
        current = (struct num_node *)malloc(sizeof(struct num_node));
        current->num = x;
        current->next = list;
        return(current);
    }
} 

void print_nums(struct num_node *list) {

    struct num_node *current;
    for (current = list; current != NULL; current = current->next)
        printf("%d\t", current->num);

}

struct num_node *sort_nums(struct num_node *list1, struct num_node *list2){
    struct num_node *current;
    struct num_node *large = list1;

    for (int i = 0; i < 25; i++){
        for (current = list1; current != NULL; current = current->next){
            if (current->num > large->num){
                large = current;
            }
        }
        create(list2, large->num);
        large->num = 0;
        return(list2);
    }
}

int sum(struct num_node *list){
    int total = 0;
    struct num_node *current;
    for (current = list; current != NULL; current = current->next){
        total = total + current->num;
    }

    return total;
}

float average(struct num_node *list){
    float total = 0;
    float count = 0;
    struct num_node *current;
    for (current = list; current != NULL; current = current->next){
        total = total + current->num;
        count++;
    }
    return total / count;
}

MAIN

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

#include "functions.h"

int main(){
    struct num_node *head = NULL;
    struct num_node *new_head = NULL;

    srand(time(NULL));

        for (int i = 1; i <= 25; i++){
            int x = rand() % 100;
            head = create(head, x);
        }

        print_nums(head);

        sort_nums(head, new_head);

        printf("\n");
        printf("\n");
        print_nums(new_head);

        printf("\n");
        printf("\n");
        printf("The total of all numbers is: ");
        printf("\t%d\n", sum(new_head));

        printf("The average of the numbers is: ");
        printf("\t%.3f\n", average(new_head));


}

Answer 1

Going back to the original idea, example code for sorting a linked list by finding the largest node, then removing it from the original list (what's left of the original list) and inserting that node into the front of a new list. Note that a merge oriented algorithm would be much faster.

NODE * SortList(NODE * pList)
{
NODE * pNew = NULL;                     /* sorted list */
NODE **ppNode;                          /* ptr to ptr to node */
NODE **ppLargest;                       /* ptr to ptr to largest node */
NODE * pLargest;                        /* ptr to largest node */
    while(pList != NULL){               /* while list not empty */
        ppLargest = &pList;             /*  find largest node */
        ppNode = &((*ppLargest)->next);
        while(NULL != *ppNode){
            if((*ppNode)->data > (*ppLargest)->data)
                ppLargest = ppNode;
            ppNode = &((*ppNode)->next);
        }
        pLargest = *ppLargest;          /* move node to new */
        *ppLargest = pLargest->next;
        pLargest->next = pNew;
        pNew = pLargest;
    }    
    return(pNew);
}

Answer 2

You are returning prematurely from sort_nums:

struct num_node *sort_nums(struct num_node *list1, struct num_node *list2){
    struct num_node *current;
    struct num_node *large = list1;

    for (int i = 0; i < 25; i++){
        for (current = list1; current != NULL; current = current->next){
            if (current->num > large->num){
                large = current;
            }
        }
        create(list2, large->num);
        large->num = 0;
        return(list2);   // This just adds the largest item to list2
    }
}

You need:

struct num_node *sort_nums(struct num_node *list1, struct num_node *list2){
    struct num_node *current;
    struct num_node *large = list1;

    for (int i = 0; i < 25; i++){
        for (current = list1; current != NULL; current = current->next){
            if (current->num > large->num){
                large = current;
            }
        }
        list2 = create(list2, large->num);
        large->num = 0;
    }
    return(list2);
}

Also, you are not using the return value of sort_nums in main. You have:

sort_nums(head, new_head);

You need:

new_head = sort_nums(head, new_head);

Simplify create

Since you are prepending items to your list in create, it can be simplified to:

struct num_node *create(struct num_node *list, int x){
   struct num_node *current = malloc(sizeof(struct num_node));
   current->num = x;
   current->next = list;
   return(current);
} 

Simplify sort_nums

You can also simplify sort_nums. You don't need the second argument. You can use:

struct num_node *sort_nums(struct num_node *list1){
   struct num_node *list2 = NULL;
   struct num_node *current;
   struct num_node *large = list1;
   int i;

   for (i = 0; i < 25; i++){
      for (current = list1; current != NULL; current = current->next){
         if (current->num > large->num){
            large = current;
         }
      }
      list2 = create(list2, large->num);
      large->num = 0;
   }
   return(list2);
}

Of course, you'll have to change the way use it in main.

new_head = sort_nums(head);