What is the running time of insertion sort?

Question

[Magzhan Sydykov]

Всем доброго дня!
Имеем массив размером N, хронящий 3 вида значений (например: 0, 1, 2). Значения распределены случайным образом.
Вопрос: Каким будет время выполнения сортировки (insertion sort), линейное, квадратичное или что-то между?

Comments

[Akina]

массив размером N, хронящий 3 вида значений (0, 1, 2)

Такие штуки надо сортировать подсчётом. За линейное время.

[Magzhan Sydykov]

Akina, спасибо за совет. Однако в данном случае рассматривется именно insertion sort. Желательно провести анализ работы алгоритма и доказать вывод.

Answer 1

[Wataru]

Квадратичное. При вставке каждого элемента в среднем отсортированная часть будет на треть состоять из 0, на треть и 1 и на треть и 2. Если текущий элемент 2, то вставка за O(1), если текущий элемент 1, то вы потратите i/3 операций. Если элемент 0, то 2/3i. В среднем i/3 операций на один элемент. Если просуммировать это от 1 до n, то получится n(n-1)/6. Значит общее количество операций O(n^2).

Comments

[Magzhan Sydykov]

Я правильно понимаю то,что i -- номер элемента начиная с еденицы, и 2/3i = 2/3(i)?

[Wataru]

Magzhan Sydykov, да