Turbo Sort Time Time Limit Exceeded

general
1

This program runs in under 5 seconds on Xcode. Could somebody please give me some advice as to why code chef might giving me this time limit error.

#include

using namespace std;
int main()
{

int i, j;
int temp = 0;
int dat = 0 ;
int size = 0;

//fill array
cin >> size;
int myArray[size];
for(int i = 0; i < size; i++)
{
    cout << "enter data: ";
    cin >> dat;
    myArray[i] = dat;
}

//bubble sort array
for(i = 0; i < size; i++)
{
    
	for (j = 0; j < size-1; j++)
    {
        if (myArray[j] > myArray[j+1])
		{
			temp = myArray[j];
			myArray[j] = myArray[j+1];
			myArray[j+1] = temp;
		}
    }
}

//print array
for (i = 0; i < size; i++)
{
	cout << myArray[i] << endl;
}

return 0;

}

2

Hello,

Bubblesort is a great theoretical algorithm, but very bad in practice :smiley:

I suggest that you explore STL and use std::sort to solve this easily! (and this is the way its meant to be solved I’d dare to say)

If you really want to code an efficient algorithm yourself, you can always try Heapsort :smiley:

Best,

Bruno

3

I tried using std::sort with vectors and i’m still getting the same error.

#include
#include
#include

int main(int argc, const char * argv[])
{
std::vector array;
int size = 0;
int temp = 0;

std::cin >> size;
for(int i = 0; i<array.size(); i++){
    std::cout << "Enter data: ";
    std::cin >> temp;
    array.push_back(temp);
  
}

std::sort(array.begin(), array.end());

for(int j = 0; j<array.size(); j++){
    std::cout << array[j] << std::endl;
}
return 0;

}

4

you have to use fast IO methods (like in this code http://www.codechef.com/viewsolution/3448589) in order to avoid TLE in turbo sort with a nlog(n) complexity algorithm(like qsort,heap sort,merge sort).

5

Best option is to use hashing . Running time O(n)

6

Even using scanf and printf can help you to get accepted.
Have a look at this link: http://www.codechef.com/viewsolution/3797203