Given an array of strings containing the seven colors of the rainbow but placed in random order, I am somehow supposed to sort this array to output Red, Orange, Green,....,Violet in that order. The order of rainbow colors. How can I sort this array?
-
Since there are only seven values and these have a fixed order, why bother sorting?Fred Foo– Fred Foo2012-10-01 12:25:15 +00:00Commented Oct 1, 2012 at 12:25
-
@lars, I believe this is just a simple test example to learn the concept of such sorting?SingerOfTheFall– SingerOfTheFall2012-10-01 12:25:52 +00:00Commented Oct 1, 2012 at 12:25
-
Since first letter is not repeated, you can sort them based on that only.Shashwat– Shashwat2012-10-01 12:28:09 +00:00Commented Oct 1, 2012 at 12:28
-
@larsmans, Lars correctly said it. The idea is actually to create a custom sort. The issue here is how to tell the compiler Red > Orange >....> Violet.Hussein– Hussein2012-10-01 12:29:32 +00:00Commented Oct 1, 2012 at 12:29
Add a comment
|
3 Answers
You should write a custom comparator. Here's how I would go about it.
//somewhere in initalization code;
std::map<string, int> mapOrder;
mapOrder["red"] = 1;
mapOrder["orange"] = 2;
...
mapOrder["violet"] = 7;
bool isRainbowLess(const std::string& a, const std::string& b)
{
return mapOrder[a] < mapOrder[b];
}
int main()
{
std::vector<std::string> myVector;
....
std::sort(myVector.begin(), myVector.end(), &isRainbowLess);
}
6 Comments
Hussein
Thanks for the suggestion. Can you please suggest a way to do this without using the STL. Someone mentioned that i can use Enum to initialize the rainbow colors in terms of preference.
luk32
@Hussein, I am not a guru ... though I think this is the cleanest way in c++ to do it. It would like to skip STL, you would need to implement your own mapping in place of
std::map and sorting in place of std::sort ... and some array-like container in place of std::vector. enum would let you map literals not std::strings to values. You could use it to map initial data into some array of integers, then sort it, and then decode it back for output. It would probably be a little bit faster. I can write a proposed concept-answer, though I think Armen's code is good c++.Hussein
@luk32, thanks for the explanation. I have accepted this as the answer. A quick question, i have an array of strings, How do i pass it to my myVector in the main function?
Hussein
@luk32 Thanks, that helped. Just need to fix some issue. Did the alternative solution you are working on successful. Maybe you can send the solution too?
|
This code is not completed. But you should get the general idea. One thing I did skip is the sorting of integers itself. Since it should be trivial. As you can see, the mapping, is a little bit of PIA and looks quite bad. But since you forbid to use STL there is no std::map. Moreover, I implied static size of N for all the tables. It could be allocated dynamically, no problem, and no std::vector.
I used else ifs for map* functions to mimick std::map functionality. Probably switch ... case could be used, but it should work pretty much the same on a decent compiler.
The code I wrote below is pretty much the same in terms of functionality provided as Armen's does. I would recommend his solution. I skipped same parts. So you can see it's uglier and more typing. It looks almost like pure C. Maybe with one modification if you really yearn for speed at very large cases. That would be using a temporary data structure that would hold mapped values, to sort it, and then map it back. Precisely I would advise to avoid calling map::operator[](const &T) (or any accessor) on std::string under high performance constraints to avoid hash computations. But that's only it.
There is also some more to discuss. Like what if you wanted two colors to have the same value, or use non-integer weights. STL based solution is way more adaptable.
/* This will map color literals (color names) to integers, which will associate them with
a numerical value, than can be used for comparison */
enum Colors { Red, Orange, Green, /*...*/ Violet };
/* this should read colors as std::string instances from the input array and assing
the the appropriate color codes into output array at corresponding indexes */
void mapString2Color( const std::string* input, int* output, size_t N ){
for(size_t i = 0; i < N; i++){
if ( input[i] == std::string("red") ) output[i] = Colors::Red;
else if ( input[i] == std::string("orange") ) { output[i] = Colors::Orange; }
else if ( input[i] == std::string("green") ) { output[i] = Colors::Green; }
/*...*/
else if ( input[i] == std::string("violet") ) { output[i] = Colors::Violet; }
else {/*unspecified color code */}
}
}
/* this is supposed to do the opposite to mapString (i.e. put appropriate
string at output[i] based on input[i]) */
void mapColor2String( const int* input, std::string* output, size_t N ){
for(size_t i = 0; i < N; i++){
if ( input[i] == Colors::Red ) output[i] = std::string("red");
else if ( input[i] == Colors::Orange ) { output[i] = std::string("orange"); }
else if ( input[i] == Colors::Green ) { output[i] = std::string("green"); }
/*...*/
else if ( input[i] == Colors::Violet ) { output[i] = std::string("violet"); }
else {/*unspecified color index*/}
}
}
void sort(int* array, size_t N){
/* any in-place sort of your liking for table of (unsigned) integers */
}
main(){
std::string[N] input_array;
std::string[N] output_array;
int[N] temp_array;
//map (translate) colors to their numerical values
mapString2Color(input_array, temp_array, N);
//sort it
sort(temp_array, N);
//map (translate) the values back to color names
mapColor2String(temp_array, output_array, N);
}
1 Comment
Hussein
Thank you very much and now i will accept this as the correct answer since in as much as it might not be as elegant as the one before, it solved the task as required. So, thanks alot luk32. Your reply was what i was looking for.
First thing I would do is to create a mapping. You could do this either via a map or by linearly iterating over a presorted array of strings and taking the index of the matching entry. A very simple way (for demonstration purposes really) might be simply to encode the logic into an encapsulated function as follows:
int intForCol( const string& col )
{
if ( col == "red" ) return 0;
else if ( col == "orange" ) return 1;
else if ( col == "yellow" ) return 2;
else if ( col == "green" ) return 3;
else if ( col == "blue" ) return 4;
else if ( col == "indigo" ) return 5;
else if ( col == "violet" ) return 6;
throw "Invalid colour";
}
This will provide an ordering integer based on the input string. The next step is to create a comparator:
int colComp( const string& lhs, const string& rhs )
{
return intForCol( lhs ) - intForCol( rhs );
}
This will allow us to compare strings together returning negative if lhs < rhs and positive if lhs > rhs
This can now be used within the STL - either as the comparitor within an associative container or directly in a sort algorithm - with relative ease. Alternatively, if using STL is out of the question or the point of this is to understand how sorting works, you could implement your own sort like the simple and (very) inefficient algorithm below:
const int col_size = 7;
string input[col_size];
input[0] = "indigo";
input[1] = "green";
input[2] = "red";
input[3] = "blue";
input[4] = "yellow";
input[5] = "violet";
input[6] = "orange";
// simple bubble sort
int passes = col_size;
int last = col_size;
while ( passes-- )
{
for ( int i = 0; i < last - 1; ++i )
if ( colComp( input[i], input[i+1] ) > 0 )
{
string temp = input[i]; input[i] = input[i+1]; input[i+1] = temp;
}
last--;
}
2 Comments
luk32
Quite nice noSTL wrap-up. However I think it is worth of noting that the comparator will impose 2*
else if ladder which is ... quite performance breaking (and should be considered not cool =). It could even end up being slower than standard hash function for string. <-Just a side note.
Component 10
Well as a general rule I'd agree, but given the size of the collection and the disparate nature of the strings (the first letter of each colour is different so comparison will never go beyond the first character) I would say that in practice performance shouldn't be that bad. Generally, I wouldn't go for this approach but would use a map or set instead, but given that it had to avoid STL, i gave it for demonstration purposes only.