Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

2.2.3.2. Шейкер-сортировка 
Предыдущий алгоритм сортировки можно попытаться усовершенство-
вать, используя следующие идеи: 
− условием завершения процесса сортировки считать отсутствие 
парных перестановок при очередном просмотре; 
− сравнение пар элементов производить только до места последней 
перестановки: раз не было перестановок, значит дальше элементы 
упорядочены; 
− чередовать направления просмотра, что позволит одновременно 
формировать две отсортированных области – в левой и правой 
частях массива. При прохождении массива слева направо (снизу 
вверх) При прохождении массива слева направо (снизу вверх) 
поднимается легкий пузырек. При прохождении массива справа 
налево (сверху вниз) опускается тяжелый пузырек
Основанный на этих идеях алгоритм сортировки получил название 
шейкер-сортировки (от англ. shake – трясти). Его текст приведен в листин-
ге 2.8. 
Листинг 2.8. Шейкер-сортировка 
public void SortShaker(int[] a) 
{ 
int left = 1, right = a.Length - 1, last = right; 
do 
{ 
for (int j = right; j >= left; j--) 
if (a[j - 1] > a[j]) 
{ 
int t = a[j - 1];
a[j - 1] = a[j];
a[j] = t; 
last = j; 
} 
left = last; 
for (int j = left; j <= right; j++) 
3 / 23

---

27 
if (a[j - 1] > a[j]) 
{ 
int t = a[j - 1];
a[j - 1] = a[j];
a[j] = t; 
last = j; 
} 
right = last - 1; 
} 
while (left < right); 
} 
Все усовершенствования сортировки обменом приводят только к 
уменьшению числа сравнений, тогда как основное время занимает переста-
новка элементов. Поэтому эти усовершенствования не приводят к значитель-
ному эффекту. Анализ показывает, что сортировка методом пузырька (и даже 
ее улучшенный вариант – шейкер-сортировка) менее эффективна, чем сорти-
ровка вставками и обменом.