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

×

[closed] Problem TSORT : Time Exceeds

Somebody help me in curing 'Time Limit' for this program! As else the code seems correct....

#include<stdio.h>
int main()

{

long long n,i,j,small,loc,temp;

scanf("%lld",&n);

long long *arr=new long long[n];
for(i=0;i<=n-1;i++)

scanf("%lld",&arr[i]);

for(i=0;i<n-1;i++)

{

small=arr[i];

    loc=i;

    for(j=i+1;j<=n-1;j++)
    {
        if(arr[j]<small)
        {
            small=arr[j];
            loc=j;
        }
    }
    temp=arr[i];
    arr[i]=arr[loc];
    arr[loc]=temp;
}

for(i=0;i<=n-1;i++)

printf("\n%lld",arr[i]);

delete[] arr;

return 0;
}

asked 24 Oct '14, 01:31

wrangler00's gravatar image

3★wrangler00
0114
accept rate: 0%

closed 31 Oct '14, 21:42

kunal361's gravatar image

4★kunal361
6.0k133272

Please accept an answer so that we can close this question.

(31 Oct '14, 19:32) bipin23★

The question has been closed for the following reason "The question is answered" by kunal361 31 Oct '14, 21:42


@wrangler00: Hai man! The time complexity of bubble sort is O(n^2) in the worst case and the best case is O(n) if modified. But as a programmer we should always look at the worst case! See here O(n^2) means is that if there are n elements then there should be n^2 comparisons. As far as i know with my limited knowledge in competeive programming if the value of the worst case, here it is n^2 is more than 10^8 then it will surely will not run in 1 second. So here check the question N<=10^6. Taking the worst case if the value of N=10^6, then complexity of your bubble sort is O(n^2) is 10^12 where n=10^6. So going beyond 10^8 it will surely not run in 1 second. Approximately it will take around 30,000+ second. Hope you got the mistake. As pranjalranjan said either you can use Merge Sort or Heap Sort since both the algorithms complexities are O(N Log N). Check by substituting the value of n in the above said complexities. It will fit in 10^8. But for this question the best algorithm is Counting sort, as what kaushik_iiitd said, whose time complexity is linear i.e. O(N). You can google it! If you dont undertand it please do post it here. We will help you! I repeat , this question can be done with quick sort, merge sort, heap sort, i.e any sorting algorithm whose worst time complexity is N Log N or lesser! :)

link

answered 25 Oct '14, 19:05

bipin2's gravatar image

3★bipin2
3.1k254671
accept rate: 8%

bro! If you understood please do accept the answer so that we can close the question :)

(25 Oct '14, 20:38) bipin23★

How do we accept an answer??

(26 Oct '14, 02:42) wrangler003★

There will be a tick symbol down to the vote down symbol.

(26 Oct '14, 11:18) bipin23★

please view my quicksort code in the bottom......

(26 Oct '14, 11:48) wrangler003★

what should i do??

(26 Oct '14, 12:01) bipin23★

is still giving TLE in quicksort.

(26 Oct '14, 12:26) wrangler003★
1

this is the basic quick sort. I mean the naive one! Check for the case when the array is reversely sorted. The time complexity will be O(n^2). So use randomized quick sort. You can even use inbuilt sort function which is implemented using quick sort-sort(arr,arr+n) is the syntax of this inbuilt function. Include algorithm header file

(26 Oct '14, 12:32) bipin23★
showing 5 of 7 show all

Bubble sort will ofcourse give you an error as n is large. Try a fast sorting algorithm like quicksort or mergesort!

link

answered 24 Oct '14, 01:41

pranjalranjan's gravatar image

4★pranjalranjan
2.0k21432
accept rate: 20%

Its right that bubble sort uses too much time for execution.

BUT many have submitted using this sort technique successfully so whats the problem with my code.

(25 Oct '14, 17:31) wrangler003★

Even Quicksort and MergeSort would get TLE for this question. Count Sort is what you require :)

link

answered 24 Oct '14, 01:52

kaushik_iiitd's gravatar image

2★kaushik_iiitd
1.6k1818
accept rate: 36%

1

Nope. quicksort won't. Not mergesort as well, if implemented properly. I used the sort function from the algorithm library which uses the quicksort algorithm for large n and nope, it didn't give TLE. Dont worry it'll work!

(24 Oct '14, 03:48) pranjalranjan4★

and anyway the time limit of this function in 5 sec. One can blindly vouch for merge sort or quicksort for this case.

(24 Oct '14, 03:51) pranjalranjan4★

Weak test cases probably. I'm sure you won't get AC here with the above implementations :P http://www.spoj.com/problems/TSORT/

(24 Oct '14, 04:13) kaushik_iiitd2★

i have already done it on SPOj as well -- and FYI, i got an AC! It works --

(24 Oct '14, 04:53) pranjalranjan4★
2

Standard Sorting(C++) - 2.39 s Merge Sort - 3.11 s Heap Sort - 3.10 s Count Sort - 2.33 s Results posted by someone on comments of the same problem on SPOJ.

(24 Oct '14, 04:55) pranjalranjan4★

My bad :) Anyway can I see your implementation of Standard sort which was AC on Spoj? What's the point of solving the question then if you solve with any sorting algorithm (n log n).

(24 Oct '14, 18:14) kaushik_iiitd2★
1

Inbuilt Quick Sort in c can get you AC. Heap sort is also working . Counting sort is also one option with O(n). Happy coding.

(24 Oct '14, 18:20) ab131230025★

@kaushik_iitd i implemented it using mergesort and it got AC. As i told -__- http://www.codechef.com/viewsolution/5236275

(29 Oct '14, 17:41) pranjalranjan4★
showing 5 of 8 show all

The solution is to use Counting Sort, O(n) time complexity

link

answered 24 Oct '14, 18:31

ahmedtai's gravatar image

4★ahmedtai
1464
accept rate: 7%

merge sort will work as it takesO(nlogn)in worst casees............

link

answered 25 Oct '14, 13:36

s10ky18's gravatar image

2★s10ky18
3012
accept rate: 0%

inbuilt sort will work you can use merge or heap sort also

link

answered 30 Oct '14, 17:47

anichavan20's gravatar image

2★anichavan20
9314
accept rate: 0%

@wrangler00
Bro Check this discussion link..
http://discuss.codechef.com/questions/14768/turbo-sort?page=1#53514
User argonaut gave an amazing answer for tackling Turbo Sort problem.
You may refer to my solution too, I have implemented the same logic in c (including fast input and output) after reading that discussion page
Solution Link

link

answered 25 Oct '14, 10:32

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11243
accept rate: 14%

edited 26 Oct '14, 09:05

@pranjalranjan

Its right that bubble sort uses too much time for execution.

BUT many have submitted using this sort technique successfully so whats the problem with my code.

link

answered 25 Oct '14, 17:30

wrangler00's gravatar image

3★wrangler00
0114
accept rate: 0%

1

Nobody would have used bubble sort, i am sure! If u feel that someone has used bubble sort and still submitted successfully, please comment a link of the solution! Bubble sort can never solve this problem. You atleast require an O(nlogn) technique.

(25 Oct '14, 18:24) pranjalranjan4★

Hey! Now since i have used Quicksort technique why is it giving runtime error as "NULL POINTER ASSIGNMENT".

There dosn't seem anything wrong with this code.

#include<iostream>

using namespace std;

void Quicksort(int*,int,int);

int partition(int*,int,int);

void swap(int*,int*);

int main()

{

int n,i;

cin>>n;

int *arr=new int[n];

for(i=0;i<n;i++)

cin>>arr[i];

Quicksort(arr,0,n-1);

for(i=0;i<n;i++)

cout<<"\n"<<arr[i];

delete[] arr;

return 0;

}

void Quicksort(int *A,int beg,int end)

{

    int pindex;

    if(beg<end)

    {

                pindex=partition(A,beg,end);

                Quicksort(A,beg,pindex-1);

        Quicksort(A,pindex+1,end);

    }
}

int partition(int *A,int beg,int end)
{

               int pivot=A[end];

               int pindex=beg;
           for(int i=beg;i<end;i++)
          {

if(A[i]<=pivot)

        {

            swap(&A[i],&A[pindex]);

            pindex++;

        }
    }

    swap(&A[pindex],&A[end]);

    return pindex;

}

void swap(int *a,int *b)

{

    int temp;

    temp=*a;

    *a=*b;

    *b=temp;
}
link

answered 26 Oct '14, 11:47

wrangler00's gravatar image

3★wrangler00
0114
accept rate: 0%

edited 29 Oct '14, 19:25

topcoder_7's gravatar image

2★topcoder_7
2.9k3153

For people who think that mergesort and quicksort will give TLE for this question, it wont. Maybe u guys are getting tle because of a slow i/o method. Here's my implementation of mergesort for AC. http://www.codechef.com/viewsolution/5236275

link

answered 29 Oct '14, 17:42

pranjalranjan's gravatar image

4★pranjalranjan
2.0k21432
accept rate: 20%

edited 29 Oct '14, 17:45

You can view above quicksort submitted by me.....i dont think there is any slow i/o method and its still giving TLE.

(29 Oct '14, 17:55) wrangler003★

Fine.. let me check

(29 Oct '14, 17:58) pranjalranjan4★

hey google and read about counting sort. It executes sorting in O(n) complexity or else merge sort or quick sort is best! :)

link

answered 30 Oct '14, 19:48

mansigupta19's gravatar image

1★mansigupta19
431419
accept rate: 0%

use sort in stl and you are good to go

link

answered 31 Oct '14, 18:27

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

use sort in stl and you are good to go

link

answered 31 Oct '14, 18:27

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

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:

×6

question asked: 24 Oct '14, 01:31

question was seen: 1,148 times

last updated: 31 Oct '14, 21:42