285
правок
Изменения
→Анализ алгоритма
== Анализ алгоритма ==
<wikitex>Число сравнений ключей на i-ом просеивании ключей ($C_i$) самое большее равно $i-1$, самое меньшее — 1; если предположить, что все перестановки из $n$ ключей равновероятны, то среднее число сравнений $i/2$. Число же обменов элементов $M_i$ равно равно $C_i+2$. Поэтому общее число сравнений и число обменов таковы:
{| border="0"
!style="background-color:#FFF"| $C_{best} = n-1$
|width=5%|
!style="background-color:#FFF"| $M_{best} = 3(n-1)$
|-
!style="background-color:#FFF"| $C_{average} = (n^2+n-2)/4$
|
!style="background-color:#FFF"| $M_{average} = (n^2+9n-10)/4$
|-
!style="background-color:#FFF"| $C_{worst} = (n^2+n-4)/4$
|
!style="background-color:#FFF"| $M_{worst} = (n^2+3n-4)/2$
|}
Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.</wikitex>
==Пример работы==
