Sort and display input numbers How do I decrease time, especially in sorting?


  Given a list of numbers, you are to sort them in non-decreasing order.
  
  Input
  
  t – the number of numbers in list, then t lines follow [\$t \le 10^6\$]. 
  
  Each line contains one integer: N [\$0 \le N \le 10^6\$]
  
  Output
  
  Given numbers in non-decreasing order.
  
  Example
  
  Input:

5
5
3
6
7
1

  
  Output:

1
3
5
6
7



struct sort_list{
int num;
struct sort_list *next;
};
typedef struct sort_list node;
void enter();
void sort();
void print();
int main()
{

        node *head;
        int tot_num;
        scanf("%d",&amp;tot_num);  //asking for entering total numbers
        head=(node*)malloc(sizeof(node));
        enter(head,tot_num);
        sort(head,tot_num);
        print(head);
    return 0;
    }
    void enter(node *list,int tot_num)
    {
        int i=0;
        while(i!=tot_num)
        {
            scanf("%d",&amp;list-&gt;num);  
            if(i==tot_num-1)
            {
                list-&gt;next=0;
                //break;
            }
            else
            {
                list-&gt;next=(node*)malloc(sizeof(node));  
                list=list-&gt;next;
            }
            i++;
        }
    }
    void print(node *list)
    {
        int i=0;
        while(list-&gt;next!=0)
        {
            printf("%d\n",list-&gt;num);
            list=list-&gt;next;
            i++;
        }
        if(list-&gt;next==0)
        {
            printf("%d\n",list-&gt;num);
        }
    }
    void sort(node *list,int tot_num)
    {
        node *new=list;
        int i,j,t;
        for(i=0;i&lt;tot_num;i++)
        {
            for(j=i+1;j&lt;tot_num;j++)
            {   
                if(list-&gt;num &gt; list-&gt;next-&gt;num)
                {
                    t=list-&gt;num;
                    list-&gt;num=list-&gt;next-&gt;num;
                    list-&gt;next-&gt;num=t;
                }
                list=list-&gt;next;
            }
            list=new;
        }
    }
There are a number of things you can do to improve this code.

Use const where possible

The print routine does not (and should not) alter the linked list, and so it should be declared as taking const node *list as an argument.

Check the return value of malloc before dereferencing

The primary way that the operating system uses to tell your program that it's running out of memory is to return NULL when the program requests a memory allocation.  For that reason, you must check the return value before dereferencing it to make sure it's not NULL.

Eliminate memory leak

There are calls to malloc but no calls to free so this code certainly leaks memory.

Separate I/O from core routines

It's often better to have input and output operation in a single place (or a few select places) rather than having them scattered in several places.  For this reason, I'd recommend having the enter routine simply be responsible for putting the new data into the linked list rather than having it also get the new number.

Use for loops rather than while loops where practical

Your print routine can be considerably simplified by using a for loop rather than a while loop and eliminating useless variable i:

void print(const node *list)
{
    for ( ; list; list = list-&gt;next)
        printf("%d\n",list-&gt;num);
}


Reduce memory allocations

The first number read is a count of the following numbers.  This tells you exactly how many nodes need to be allocated, so there really isn't any need to have multiple calls to malloc.  You can simply call it once, allocate an array of nodes that is large enough to hold all of the numbers and use that memory area for all of your linked list nodes.

Eliminate the need to sort

Rather than having separate enter and sort routines, you may find that peformance is better if you sort as you enter each number.

Putting it all together

Putting all of these suggestions (and more) into practice might look like this:

void enter(node *list, node *newnode)
{
    for ( ; list-&gt;next &amp;&amp; list-&gt;next-&gt;num &lt; newnode-&gt;num; list = list-&gt;next);
    newnode-&gt;next = list-&gt;next;
    list-&gt;next = newnode;
}

void print(const node *list)
{
    if (list == NULL)
        return;
    for ( ; list-&gt;next; list = list-&gt;next)
        printf("%d\n",list-&gt;next-&gt;num);
}

int main()
{
    int tot_num;
    scanf("%d",&amp;tot_num);  //asking for entering total numbers
    node *head = calloc(tot_num+1, sizeof(node));
    if (head == NULL) {
        printf("ERROR: could not allocate space for %d numbers\n", tot_num);
        return 1;
    }
    for (int i=1; i &lt;= tot_num; ++i) {
        scanf("%d",&amp;(head[i].num));  
        enter(head,&amp;head[i]);
    }
    print(head);
    free(head);
}


Results

Even this very simple program runs approximately 3x faster on my machine (64-bit Linux machine) than the original, operating on a file of 10,000 random numbers.  It is still quite slow, however, because the enter routine only does a simple linear search.  There are better ways to do this, and I would encourage you to look into better sorting algorithms and to try to implement some to see how they work.