Time limit exceeded

For Turbo Sort question I have written the below code.

I am getting time limit exceeded error for it.

I have tried the output for the same input given in the question and also for other input and the output is in ascending order.

I was using Scanner object earlier to take input but later changed it to bufferedreader and the earlier one is slower.

Kindly advise any changes in the solution to get AC.

package codechef_flow001;

import java.io.*;

class CodeChef_TurboSort
{

public static void main(String[] args) throws IOException
{
    int temp;
    
    BufferedReader kin = new BufferedReader(
            new InputStreamReader(
                    System.in
            )
    );
    int a = Integer.parseInt(
                kin.readLine());
    
    int array[] = new int[a];
    
    for(int i = 0; i < array.length; i++)
    {
        int b = Integer.parseInt(
                kin.readLine());
        array[i] = b;      
    }
    
  for (int i = 0; i < array.length; i++)
    {
        for (int j = i+1; j < array.length; j++)
        {
            if (array[i] > array[j])
            {
               temp = array[i];
               array[i] = array[j];
               array[j] = temp;
            }
        }    
    }
    
    for (int a1 : array)
    {
        System.out.println(a1);
    } 
}    

}

 for (int i = 0; i < array.length; i++)
    {
        for (int j = i+1; j < array.length; j++)
        {
            if (array[i] > array[j])
            {
               temp = array[i];
               array[i] = array[j];
               array[j] = temp;
            }
        }    
    }

Your code is O(N^2), which is too slow. Either you should go and learn about in-built sort function in your language, or some other sorting algorithms which take O(NLogN) time. The high school bubble/selection sort get TLE here.

1 Like

Hey @krrishy,

(Easiest approach!)
Instead of using bubble sort you can exploit the constraints as the range of A[i] is given to be 10^6 since we can make an haspmap of array where we can store the count/frequency of every element in the array and then traversing the array from 1 to 10^6 and output the specific number to its frequency times.

(Sorting Algo’s)
There are quite a few sorting algo’s which performs provide the output in O(n*log(n)) you can use anyone of them to get AC. (Sorting Algo’s Information)

Hope this helps!

Sandeep

you can see my code in C. https://www.codechef.com/viewsolution/10522063

Thats impressive.

not better than you, _/_ can you help me out figuring out how this discuss actually work… where I can see the comments where I have been tagged or comment on my answers or if I have to put in simple terms how to get the notification.

Lol, Idk, never used that. Usually they send notifications via email.

Most of the times I am able to reply is cause people send me a mail as well requesting to look there XD (I check mails freq.).

//