шейкер-сортировкой (shaker sort). Его работа показана в табл. 2.4, где он применяется к той же последовательности из восьми ключей, что и в табл. 2.3.
// ShakerSort;
int j, k, L, R, x;
L = 1; R = n–1; k = R;
do
{ for (j = R; j>= L; j--)
{ if (a[j–1] > a[j])
{ x = a[j–1]; a[j–1] = a[j]; a[j] = x; k := j;
}
}
L = k+1;
for (j = L; j>= R; j++)
{ if (a[j–1] > a[j])
{ x = a[j–1]; a[j–1] = a[j]; a[j] = x; k = j;
}
}
R = k–1;
} while ( L > R);
Анализ пузырьковой и шейкер-сортировки. Число сравнений в простой сортировке обменами равно C = (n2 – n)/2, а минимальное, среднее и максимальное числа пересылок (присваиваний элементов) равны.
