title: Algorithm for sorting a two-dimensional array based on similarities of adjecent objects
body: <p>I'm writing a program that is supposed
  to sort a number of square tiles (of which
  each side is colored in one of five colors&mdash;red, orange,
  blue, green and yellow), that are laying next to each other
  (eg 8 rows and 12 columns) in a way that as many sides with
  the same color connect as possible.
  So, for instance, a tile with right side colored
  red should have a tile on the right that has a red left-side.)</p>
  
  <p>The result is evaluated by counting how many non-matching pairs
  of sides exist on the board. I'm pretty much done with the actual program;
  I just have some trouble with my sorting algorithm. Right now I'm using
  Bubble-sort based algorithm, that compares every piece on the board
  with every other piece, and if switching those two reduces the amount of
  non-matching pairs of sides on the board, it switches them. Here a
  abstracted version of the sorting function, as it is now:</p>
  
  <pre><code>for(int i = 0 ; i &lt; DimensionOfBoard.cx * DimensionOfBoard.cy ; i++)
      for(int j = 0 ; j &lt; DimensionOfBoard.cx * DiemsionOfBoard.cy ; j++)
      {
          // Comparing a piece with itself is useless
          if(i == j)
              continue;
  
          // v1 is the amount of the nonmatching sides of both pieces
          // (max is 8, since we have 2 pieces with 4 sides each (duh))
          int v1 = Board[i].GetNonmatchingSides() + Board[j].GetNonmatchingSides();
  
          // Switching the pieces, if this decreases the value of the board 
          // (increases the amount of nonmatching sides) we'll switch back)
          SwitchPieces(Board[i], Board[j]);
  
          // If switching worsened the situation ...
          if(v1 &lt; Board[i].GetNonmathcingSides() + Board[j].GetNonmatchingSides())
              // ... we switch back to the initial state
              SwitchPieces(Board[i], Board[j]);
      }
  </code></pre>
  
  <p>As an explanation: Board is a pointer to an array of Piece Object. Each Piece has
  four Piece-pointers that point to the four adjacent pieces (or NULL, if the Piece is
  a side/corner piece.) And switching actually doesn't switch the pieces itself, but
  rather switches the colors. (Instead of exchanging the pieces it scrapes off the color
  of both and switches that.)</p>
  
  <p>This algorithm doesn't work too bad, it significantly improves the value of the
  board, but it doesn't optimize it as it should. I assume it's because side and corner
  pieces can't have move than three/two wrong adjacent pieces, since one/two side(s)
  are empty. I tried to compensate for that (by multiplying Board[i].GetMatchingPieces()
  with Board[i].GetHowManyNonemptySides() before comparing), but that didn't help a bit.
  And that's where I need help. I don't know very many sorting algorithms, let alone
  those that work with two-dimensional arrays. So can anyone of you know about
  an algorithmic concept that might help me to improve my work? Or can anyone see a
  problem that I haven't found yet? Any help is appreciated. Thank you.</p>