turbo sort. I am getting a time limit exceeded for my code. how should i correct it ??

general
, ,
1

#include<stdio.h>
int main()
{
int t,i,j,temp=0;
scanf("%d",&t);
int a[t];
for(i=0;i<t;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<t;i++)
{
for(j=0;j<t-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}

}
for(i=0;i<t;i++)
{
	printf("%d\n",a[i]);
}	
return 0;

}

2

You are using bubble sort.

It has a time complexity of O(n^2)

It won’t work because of the time limit.

Try to use a O(n log(n)) complexity algorithm like merge sort.

Here’s my solution using merge sort, http://www.codechef.com/viewsolution/3306706

There are predefined functions in almost all the languages that perform sorting in O(n log(n)).

For example, sort() function in C++ (Header: < algorithm >)

I would suggest that you also use these functions for the sake of knowledge.

But it is very important that you understand merge sort, quick sort and many more sorting algorithms and their complexities. Knowledge of sorting algorithms is important.
Here are a few sorting algorithms:

  1. Merge sort

  2. Quick sort

  3. Insertion sort.

  4. Selection sort

  5. Bubble sort

And many more

3 Likes
3

Adding to @pratku123 answer’s, Here is a nice website : http://www.sorting-algorithms.com/ to fundamentally understand how different sorting algorithms works and it clears show no algorithm is best. In some cases insertion sort is more optimal than merge sort, and in some scenarios, though other sorts may take more time, but merge sort is avoided due to overhead and memory needs.

1 Like