Интересная тема!

Я пока не догадался, как убрать перестановку из QuickSort'а, но обязательно подумаю.

Вообще, с этими алгоритмами не всё так очевидно, как кажется. У меня был случай, когда мой собственный алгоритм сортировки стабильно обгонял QuickSort на случайных входных данных. Дело было в стандартной дельфийской демо-программе, показывающей параллельную работу нитей. Там три нити одновременно сортируют массивы, а для наглядности после каждой перестановки элементов выводят содержимое массива на экран, но не в виде чисел, а графически: стопка чёрточек, в которой большое число - длинная чёрточка, малое - короткая. Можно, таким образом, видеть, как три стопки сортируются: одна пузырьком, другая quicksort'ом, третья ещё чем-то.

Мой алгоритм выигрывал на том, что у него было меньшее число перестановок и, соответственно, он меньше тратил времени на перерисовку. Я этот алгоритм ещё когда в школе учился придумал, а потом узнал, что он называетсясортировка выбором.