title: How to sort an integer array on lexicological order using only adjacent swaps for a given max # of swaps(m)
body: <p>I was asked that one during a phone interview of course, the other questions where fine, but that one I'm still not sure of the <em>best</em> answer.</p>
  
  <p>At first i thought it smelled of a radix sort but since you can't only use adjacent swaps of course not.</p>
  
  <p>So I think it's more of a bubble sort type algo, which is what I tried to do but the "max number of swaps" bit makes it very tricky (along with he lexicological part but i guess that's just a comparaison side issue)</p>
  
  <p>I guess my algo would be something like (of course now i have better ideas than during the interview !)</p>
  
  <pre><code>int index = 0;
  while(swapsLeft&gt;0 &amp;&amp; index &lt; arrays.length)
  {
    int smallestIndex = index;
    for(int i=index; i &lt; index + swapsLeft)
    {
      // of course &lt; is not correct, we need to compare as string or "by radix" or something
      if(array[i]) &lt; array[smallestIndex]
         smallestIndex = i; 
    }
    // if found a smaller item within swap range then swap it to the front
    for(int i = smallestIndex; i &gt; index; i--)
    {
      temp = array[smallestIndex]; 
      array[smallestIndex] = array[index];
      array[index] = temp
      swapsLeft--;
    }
    // continue for next item in array
    index ++; // edit:could probably optimize to index = index + 1 + (smallestIndex - index) ?
  }
  </code></pre>
  
  <p>Does that seem about right ?</p>
  
  <p>Who as a better solution, I'm curious as to an efficient / proper way to do this.</p>