Самая дорогостоящая операция сортировки

Question

Какова самая дорогостоящая операция любого алгоритма сортировки? Это операция обмена или операция сравнения?

Я думал, что это меняет, но мой друг считает, что это сравнение. Единственным способом, которым я могу оправдать это сравнение, является более дорогостоящая операция, так это то, что каждый элемент нужно сравнивать, но не каждый элемент необходимо поменять местами (т. Е. Если элемент уже находится в правильном положении, его не нужно менять). Поэтому, в целом, в более широкой картине, есть более дешевые сравнения, чем несколько дорогостоящих свопов. Но я не уверен в ответе. Есть предположения?

Answer 1

Предполагая, что все сделано в ОЗУ, операция подкачки является атомарно быстрее, чем операция сравнения. (это довольно очевидно, 2 читает тогда операцию cpu против 2-х прочитанных, 2 записи и все между ними, включая операции реестра).

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

Возьмите quicksort, который будет делать несколько сравнений, тогда поменяйте почти все и более простой алгоритм, подобный пузырьковой сортировке, чтобы сравнить все элементы друг с другом, а затем обмениваться реже. Это также зависит от базового массива, если все уже почти отсортировано. Сорт пузыря не будет меняться, но все равно сравнивать все, в то время как у heapsort (например) все равно придется «обменивать» все.

Наконец (среднее число операций подкачки) (время стоимость операции своп)/(среднее число операций оценочного) (время стоимость эксплуатации оценочного) довольно трудно оценить для алгоритма, и это очень много больше, чтобы экстраполировать все алгоритмы.

Я лично считаю, что все затраты на свопинг любого алгоритма сортировки всегда выше, чем стоимость сравнения, но я не могу поддержать это требование с любыми доказательствами (это просто личное понимание).