количество сравнений, необходимых для сортировки n значений?

Question

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

Мой вопрос - Сколько сравнений необходимо для сортировки n значений?

Внормальный выбор сортировки это O (n) сравнений, поэтому я не уверен, что будет в этом случае?

Answer 1

Обычный выбор сортировки требует O(n^2) сравнений.

При каждом запуске он делает K сравнений, где K n-1, n-2, n-3...1, а сумма этой арифметической прогрессии (n*(n-1)/2)

Ваш подход (если вы используете оптимизированную схему выбора минимума / максимума) использует 3/2*K сравнений за цикл, где длина цикла K равна n, n-2, n-4...1

Сумма арифметической прогрессии с a (1) = 1, a (n / 2) = n, d = 2 вместе с множителем 3/2 равна

 3/2 * 1/2 * (n+1) * n/2 = 3/8 * n*(n+1) = O(n^2)

Таким образом, сложность остается квадратичной (и коэффициент очень близок к стандартному)

Answer 2

В вашей версии сортировки выбора сначала вам нужно будет выбрать два элемента как minimum и maximum, и все остальные элементы в несортированном массиве можно сравнить с обоими в худшем случае.

Скажем, если в несортированном массиве осталось k элементов, и предположим, что вы выбрали первые два элемента и соответственно присвоили их minimum и maximum (1 сравнение), затем выполните итерации по остальнымиз k-2 элементов, каждый из которых может привести к 2 сравнениям.

Таким образом, общее сравнение для этой итерации будет = 1 + 2*(k-2) = 2*k - 3 сравнений.

Здесь k примет значения как n, n-2, n-4, ..., так как в каждой итерации два элемента попадают в правильное положение.Суммирование приведет к приблизительно O(n^2) сравнениям.