Я работаю над сортировкой целочисленной последовательности без идентичных чисел (без потери общности, давайте предположим, что последовательность является перестановкой1,2,...,n) в его естественном порядке возрастания (т.е.1,2,...,n). Я думал о прямой замене элементов (независимо от положения элементов; другими словами, подкачка действительна для любых двух элементов) с минимальным числом перестановок (следующее может быть возможным решением):

Поменяйте местами два элемента с тем условием, что один или оба из них должны быть заменены на правильные позиции. Пока каждый элемент не будет поставлен в правильное положение.

Но я не знаю, как математически доказать, является ли указанное решение оптимальным. Кто-нибудь может помочь?