Формула для определения количества сравнений в роде?

Question

Мне любопытно, есть ли формула / правило, чтобы найти общее количество сравнений, выполненных в алгоритме сортировки, в частности, сортировку слиянием, сортировку выбора и сортировку вставкой.Я почти уверен, что с сортировкой выбора правило n(n-1)/2, где n - количество сортируемых элементов.Я думал, что то же самое относится и к сортировке вставки, но, видимо, это не так в соответствии с практическим тестом Java, который я взял (со списком из 6 элементов сортировка вставки выполняет 14 сравнений в соответствии с ключом ответа и 15 сравнений с выборомСортировать).Так что теперь я в замешательстве.

Answer 1

Как правило, нет точных формул по нескольким причинам:

1. Существует достаточно возможностей для вариации в реализации различных алгоритмов сортировки, что могут быть небольшие расхождения между различными реализациямитот же алгоритм.

2. В некоторых алгоритмах число сравнений зависит от элементов и их начального порядка.

И, конечно, естьнет формулы «один размер подходит всем», которая охватывает все алгоритмы в (скажем) одном и том же классе сложности.

---

Одна подсказка: если алгоритм сортировки имеет лучший или худший случай, который отличается от его сложностисредняя сложность, то количество сравнений или количество ходов зависит от входных данных.