Подсчет сравнений с использованием вставки Сортировка

Question

Мне поручено подсчитывать общие сравнения при сортировке массива. Учитывая целочисленный массив {8, 2, 1, 4, 3, 5}, я начинаю со второго элемента слева, сравнивая его с первым, переключая их, а затем сравнивая третий элемент с предыдущими двумя, и и так далее, чтобы определить, где должен располагаться каждый элемент.

Я вычисляю в общей сложности 15 сравнений, но правильный счет сравнения равен 10. Я знаю, что сортировка этого массива по типу сортировки составляет 15 сравнений, поэтому как и почему количество сравнения отличается при использовании сортировки Insertion в этом пример?

Answer 1

Ваше понимание того, как работает сортировка вставки, неверно.

Используя этот псевдокод для вставки рода:

mark first element as sorted 
for each unsorted element 
    'extract' the element 
    for i = lastSortedIndex to 0 
    if currentSortedElement > extractedElement 
     move sorted element to the right by 1 
    else: insert extracted element 

исходного массива: [8, 2, 1, 4, 3, 5]

Сравнение 1: 2 < 8 Массив: [2, 8, 1, 4, 3, 5]

Сравнение 2: 1 < 8 Массив: [2, 1, 8, 4, 3, 5]

Сравнение 3: 1 < 2 Массив: [1, 2, 8, 4, 3, 5]

Сравнение 4: 4 < 8 Массив: [1, 2, 4, 8, 3, 5]

Сравнение 5: 4 > 2 Массив: [1, 2, 4, 8, 3, 5]

Сравнение 6: 3 < 8 Массив: [1, 2, 4, 3, 8, 5]

Сравнение 7: 3 < 4 Массив: [1, 2, 3, 4, 8, 5]

Сравнение 8: 3 > 2 Массив: [1, 2, 3, 4, 8, 5]

Сравнение 9: 5 < 8 Массив: [1, 2, 3, 4, 5, 8]

Сравнение 10: 5 > 4 Массив: [1, 2, 3, 4, 5, 8]

Рассортировано!