131
правка
Изменения
→Модификации
В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известно, что их количество не меньше, чем количество обменов, и не больше, чем <tex> (n - 1)^2 </tex> {{---}} максимальное количество сравнений для данной сортировки. Следовательно, <tex> T_1 = O(n^2) </tex>.
odd-even_sort(a):
for (int i = 0; i < n; ++i)
{
if (i mod2 =0)
for (int j = 2; j < n; j+=2)
if (a[j] < a[j-1])
swap(a[j-1], a[j]);
else
for (int j = 1; j < n; j+=2)
if (a[j] < a[j-1])
swap(a[j-1], a[j]);
