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));


}

"Since I don't believe I could delete the node from the original list without it being doubly linked" Actually you can delete a node in a singly linked list too, you just have to have a reference to its predecessor. — Niklas B.
– Niklas B., Commented Feb 5, 2015 at 22:23

R Sahu · Accepted Answer · 2015-02-05 22:44:51Z

1

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);

edited Feb 5, 2015 at 22:44

answered Feb 5, 2015 at 22:20

R Sahu

207k15 gold badges168 silver badges291 bronze badges

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

2 Comments

Hunter Tipton Over a year ago

I had it like that previously and it gave me the exact same result, I just now copied and pasted your code and still it was the same.

user3386109 Over a year ago

@HunterTipton You forgot to mark this answer as correct :) That's important to the rest of us since we'd rather not waste time reading a question that's already fully answered.

rcgldr · Accepted Answer · 2015-02-06 06:53:58Z

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

Collectives™ on Stack Overflow

sorting a linked list using another list

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related