Menu
A sorting algorithm is “stable” if, for two equivalent elements, it preserves their original order relative to each other. It might be useful to know a concrete example of input for which your library's std::sort is unstable.
The std::sort is a sorting function that uses the Introsort algorithm and have the complexity of O(N log(N)) where N= std::distance(first, last) since C++11 and the order of equal elements is not guaranteed to be preserved[3]. The gcc-libstdc++ also uses Introsort algorithm.
The function std::sort requires 2 parameters which are 2 random access iterators pointing to the initial and final positions of the sequence in your container which will be sorted. All the elements in such sequence will be sorted, but the final one.
std::sort requires random access iterators and so cannot be used with list .
This is something that I've been considering for a while. I've done some research and can't find anything on it, but I haven't found anything to the contrary either.
Consider the std::sort function in <algorithm>. It takes two iterators and a function pointer as arguments. So if I wanted to sort a vector of strings alphabetically, I would do something like this:
bool ascending(std::string lhs, std::string rhs) { return lhs < rhs; }
std::sort(my_vector.begin(), my_vector.end(), ascending);
The thing is that this type of sort function is case-sensitive, so would place a string beginning with lowercase 'a' after strings beginning with uppercase 'Z'. The only visible solution I see to this is creating an additional function along the lines of bool ascending_case_insensitive(). However, it would be nice if I could have a function bool ascending() with an additional bool is_case_sensitive parameter to use in sort. Is this possible?
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With