Custom sorting by array of strings

Question

Given an array of strings containing seven rainbow colors, but placed in random order, I somehow have to sort this array to output Red, Orange, Green, ...., Violet in that order. The order of the rainbow colors. How can I sort this array?

Answer 1

OK, please do not vote immediately. I know this is a bad example. I wrote that it was the OP that specifically requested the no-STL solution, and imagine how (bad) it would look.

Well that's all. The code is not complete. But you should get a general idea. One thing I missed is sorting integers. Since it should be trivial. As you can see, the mapping is a little PIA and looks pretty bad. But since you forbid using STL, there is no std::map . Moreover, I meant the static size N for all tables. It could be distributed dynamically, without problems, and not std::vector .

I used else if for map* functions to map* functionality of std::map . You can probably use switch ... case , but it should work similarly on a decent compiler.

The code I wrote below is practically no different from the functionality provided to Armen. I would recommend his solution. I missed the same parts. So you can see it more ugly and more typical. It almost looks like a pure C. Perhaps with one modification, if you really dream of speed in very large cases. This will use a temporary data structure that will contain the displayed values, sort it and then display it back. That is why I would advise avoiding calling map::operator[](const &T) (or any accessor) on std::string in accordance with high performance limitations in order to avoid hash calculations. But that is just it.

There are a few more discussions. For example, if you want two colors to have the same value or use non-integer weights. The STL-based solution is more flexible.

Greetings.

Code:

 /* 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 (ie 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); } 

Answer 2

You must write your own comparator. Here is how I would do 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); } 

Answer 3

The first thing I would like to do is create a mapping. You can do this either using a map, or by linear repetition over a predefined array of strings and taking into account the index of the corresponding record. A very simple way (for demonstration purposes) may simply be 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 integer number of orders 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 the strings together, returning negative values ​​if lhs < rhs and positive if lhs > rhs

Now it can be used in STL - either as a comparison in an associative container, or directly in the sorting algorithm - with relative ease. Alternatively, if using STL is out of the question, or the point of view is to understand how sorting works, you can implement your own view, for example, a simple and (very) inefficient algorithm:

  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--; }