Penso basti spostare l'elemento che è stato scelto al posto dell'ultimo e ripetere cercando tra il primo e (l'ultimo-1).
Dopo scambi quello scelto con il penultimo e cerchi tra il primo e (l'ultimo-2) ... chiaro?