I am working on a problem and continuously getting TLE. I want to know if there’s another way to sort a vector.
Currently I am using
sort(v.begin(),v.end());
Remember I want to avoid the TLE so please suggest me a better method to sort a vector or an array.
EDIT: The goal of the problem is to sort a string in alphabetical order. I am currently using a vector of .
The sort() function has asymptotic time complexity of O(N*log N). For randomly generated numbers this is the best that we can do (due to the lower bound for any comparison based sorting algorithms).
Note :: The functions/methods implemented in STL are generic and optimised.
For your question, if it is giving TLE, there might be some other better approach to solve it.
More specifically you can post the link to your question so that one could tell if it is needed or there is some better way of doing it
Please give your problem link…
You can use quicksort or insertion sort. As your problem is not specified. I can only give you suggestions.
#include <cmath>
#include <complex>
bool euler_flip(bool value)
{
return std::pow
(
std::complex<float>(std::exp(1.0)),
std::complex<float>(0, 1)
* std::complex<float>(std::atan(1.0)
*(1 << (value + 2)))
).real() < 0;
}
If you are sorting a string here’s another way, it’s same as yours but I think it’s more time efficient.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
void print ( const string& s )
{
cout<< s <<endl;
}
int main()
{
string list[] = {
"This",
"is",
"a",
"test",
"of",
"C++'s",
"string",
"sorting",
"capability"
};
sort ( list, list + 9 );
for_each ( list, list + 9, print );
}
If you need to sort a string in alphabatically you can use the following approach.
void sort(string s)
{
int l=s.length();
int k=0;
string g;
for(int i=65;i<=90;i++)
{
for(int j=0;j<=l;j++)
{
if(s[j]==i)
{
g[k]=i;
k++;
}
}
}
return g;
}What is the use of euler_flip() function here?
use bucket sort as you will encounter with only 26 letters, its will be a lot faster.
Why do you think your code is more time efficient? It’s using std::sort too, so both are O(n log n). And do explain the purpose of euler_flip() function.
There’s always a possibility in any problem we need not sort the whole array or string, So instead of sorting whole you can sort to a particular indices.it’s more time efficient. Please read the full answer I wrote clearly “I can give only suggestions as I don’t know about your problem.” Now please tell me how it’s misleading.
@meoow Did I misuse this community platform. I don’t think so. Please avoid reporting directly any answers. Instead a down vote is enough. I am not abusing anyone. I have followed the codechef code of conduct every time. Reporting can cause suspension of my codechef account, Ok I understand you are not satisfied with this answer but It’s still accepted answer.
There’s another way I have posted please take a look at that.
Here is my simple C++ sort function which works in O(Len) time!
I just use the concept of hashing which which is generally most popular in string handling subjects!
So as compare to sort() function which sort all in O(Len log (Len) ) ! This one is best!
void sorts(string str){`int len=str.length();
int save[26]={0},i;
for(i=0;i<len;++i)
{
++save[str[i]-'a'];
}
for(i=0;i<26;++i)
{
while(save[i]--)
{
printf("%c",i+'a');
}
}
}@only4 your answer being accepted is precisely what bothers me. You literally claim that your std::sort() is faster than someone else’s std::sort(). It is misleading and I have reported it to be so. Besides, this is not the first time you have given such an answer and I have politely asked you not to before.
Before answering a question I would suggest you consider whether your answer will actually help the person who asked the question or make him more confused.