Точное количество сравнений в Вставка Сортировка

Question

Я хочу получить число перестановок {1, ..., n}, для которых Sorting Sorting выполняет точно n (n-1)/2 сравнения. Например, для {1, 2, 3, 4} мы получили (4, 3, 2, 1), (3, 4, 2, 1), (4, 2, 3, 1) и т. Д. - для всех из них InsertionSort выполняет 4 * 3/2 = 6 сравнений. Кто-нибудь знает какую-то точную формулу для этого? Я думаю о чем-то вроде (n-1) + 1 = n, где 1 означает обратную последовательность, а затем мы можем поменять все пары (n-1) в обратной последовательности.

Answer 1

Это подсказка. Полный список для (1, 2, 3, 4):

(4, 3, 2, 1) 
(3, 4, 2, 1) 
(4, 2, 3, 1) 
(2, 4, 3, 1) 
(4, 3, 1, 2) 
(3, 4, 1, 2) 
(4, 1, 3, 2) 
(1, 4, 3, 2) 

Посмотрите на это от последней колонки до первой.

Пройдите шаг за шагом через вставку. Посмотрите, где они сливаются. Вы видите там образец?

Свернув его, вы можете понять, как я сгенерировал этот список? Можете ли вы доказать, что список завершен?

Почему здесь важно. Просто сказать 2n-1 бесполезно.

Answer 2

n(n-1)/2 - сумма всех элементов в диапазоне (1, n - 1). Поскольку ваша последовательность имеет длину n, вы можете расширить этот диапазон до (0, n - 1).

Количество свопов для каждой вставки будет:

run # list  value swaps 
1  []   a  0 (no swaps possible) 
2  [a]  b  1 
3  [b, a]  c  2 
... 
10  [i,...,a] j  9 
... 
n  [...]  ?  n - 1 

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

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