Custom Sort on an array of Strings

Question

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?

Answer 1

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

Answer 2

OK, please do not down vote it right away. I know this is a bad example. I wrote it be cause OP specifically asked for a no-STL solution, and to present how (bad) would/could it look like.

Well, there you go. The 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.

Cheers.

The 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 (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);
}