Sort and display input numbers

Question

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",&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",&list->num); 
 if(i==tot_num-1)
 {
 list->next=0;
 //break;
 }
 else
 {
 list->next=(node*)malloc(sizeof(node)); 
 list=list->next;
 }
 i++;
 }
 }
 void print(node *list)
 {
 int i=0;
 while(list->next!=0)
 {
 printf("%d\n",list->num);
 list=list->next;
 i++;
 }
 if(list->next==0)
 {
 printf("%d\n",list->num);
 }
 }
 void sort(node *list,int tot_num)
 {
 node *new=list;
 int i,j,t;
 for(i=0;i<tot_num;i++)
 {
 for(j=i+1;j<tot_num;j++)
 { 
 if(list->num > list->next->num)
 {
 t=list->num;
 list->num=list->next->num;
 list->next->num=t;
 }
 list=list->next;
 }
 list=new;
 }
 }

• Brythan: Are you required to use a linked list?
• Shubham Sharma: no it is not compulsory to use linked list.

Answer 1

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->next)
 printf("%d\n",list->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->next && list->next->num < newnode->num; list = list->next);
 newnode->next = list->next;
 list->next = newnode;
}
void print(const node *list)
{
 if (list == NULL)
 return;
 for ( ; list->next; list = list->next)
 printf("%d\n",list->next->num);
}
int main()
{
 int tot_num;
 scanf("%d",&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 <= tot_num; ++i) {
 scanf("%d",&(head[i].num)); 
 enter(head,&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.

Answer 2

If you don't have to use a linked list, then I wouldn't. You could use a balanced binary tree, which does a nice insertion sort. However, the balancing code requires some attention to get right. The simplest solution is just an array. If you have enough memory to hold a linked list, you should have enough for an array.

int main() {
 int *numbers;
 int number_count;
 scanf("%d", &number_count); //asking for entering total numbers
 numbers = (int *)malloc(number_count * sizeof(int));
 if ( NULL == numbers ) {
 return EXIT_FAILURE;
 }
 enter(numbers, number_count);
 qsort(numbers, number_count, sizeof(int), int_compare);
 print(numbers, number_count);
}

This changes from a linked list to an array.

I added some vertical spacing to make it easier to see what goes with what.

I changed the name of tot_num to number_count as being clearer.

I continued to use malloc in this case because we know that the number of bytes in a million int values will fit within a size_t variable. If we didn't know that, we should prefer calloc, which doesn't force you to do the math yourself. Also, since we are writing every number, I don't care about zero initializing values, which calloc does but malloc doesn't.

I changed from a custom sort function to the built-in qsort. The expected case for qsort is \$O(n\log n)\,ドル which is better than the \$O(n^2)\$ for most algorithms that sort a linked list. For our purposes, \$n\$ is equal to number_count.

The return 0 at the end of main is unnecessary. The compiler will do it for you if you leave it off. I return EXIT_FAILURE if the malloc fails. I believe that EXIT_FAILURE is defined in stdlib.h as is qsort.

We need to define a custom compare function for qsort:

int int_compare(const void *a, const void *b) {
 return ( *(int *)a - *(int *)b );
}

This is the standard one for integers.

void enter(int *numbers, int number_count) {
 int i = 0;
 while ( i < number_count ) {
 scanf("%d", numbers + i); 
 ++i;
 }
}

See how much simpler the enter function is for an array? You could also replace the while loop with a for here. I only stuck with the while as it was what you had. The for loop can be easier to read though. The while spreads the loop definition across multiple lines.

Some compilers can do ++i faster than i++, so it can be advantageous to get in the habit of writing ++i unless you need the behavior of i++. This won't affect performance much generally, but it also doesn't hurt anything to prefer ++i.

The numbers + i is equivalent to &numbers[i]. Use whichever you find easier to understand.

void print(const int *numbers, int number_count) {
 int i=0;
 while ( i < number_count ) {
 printf("%d\n", numbers[i]);
 ++i;
 }
}

Again, the logic for an array is simpler.

I don't have a C compiler installed at the moment, so apologies if I missed something.

There's nothing magical about qsort (which is an abbreviation of quicksort). There are other algorithms that will give the same sort time on an array. It's just the algorithm that's already implemented in standard C.

Note that one reason why this works is that an int is about the same size as a pointer. As a result, it's just as easy to swap two integers in an array as it is to swap around pointers in a linked list. If we were sorting larger structures, we might want to find a different way. I already mentioned balanced binary trees, which are good for maintaining a sorted list of structures. Another possibility would be an array of pointers to structures, which we could sort with qsort again. We'd just need a different comparison function.