You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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&lt;t;i++)" {="" for(j="0;j&lt;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;

}

asked 30 Jun '14, 23:06

harry_potter's gravatar image

2★harry_potter
131222
accept rate: 0%


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

link

answered 30 Jun '14, 23:15

pratku123's gravatar image

4★pratku123
1.8k4933
accept rate: 14%

edited 30 Jun '14, 23:35

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.

link

answered 01 Jul '14, 00:35

kunaaljain's gravatar image

5★kunaaljain
151137
accept rate: 20%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×205
×40
×38

question asked: 30 Jun '14, 23:06

question was seen: 2,326 times

last updated: 01 Jul '14, 00:35