Лекція 6. Керуючі структури

Швидке сортування Шела (1959)

Масив розбивається на групи, кожна з яких складається із двох елементів. Відстань між парами елементів d=n/2, де n - кількість елементів масиву. Елементи- Пари рівняються між собою і якщо потрібно, то міняються місцями. Потім групи попарно зливаються. Кожна нова група має 4 елемента, відстань між елементами d=d/2. У середині групи виконується сортування, потім групи зливаються. Процес триває доти , поки відстань між елементами не стане 1. На цьому етапі масив сортується методом вставки (пухирця).

Конструкції gap/=2 і j/=gap значить відповідно gap=gap/2 і j=j-gap. Зовнішній цикл змінює зрушення між парою елементів, які рівняються, від n/2, n/4 до 1. Наступний внутрішній цикл забезпечує перегляд масиву, починаючи з n/2, n/4 і 1- го до кінця.

Третій цикл (по j) до деякої міри є фіктивним: у ньому для певної пари для випадку, коли перший елемент більше другого, вони переставляються. Після цього j-=gap, тобто стає менше нуля й відбувається вихід із циклу.

Іноді в циклі for можна відразу використовувати два індекси. У цьому випадку одне вираз поєднує два за допомогою оператора ",": вираз 1, вираз 2. Кома розділяє два вирази, які виконуються зліва направо. Значення й тип операнду визначається правим виразом. Лівий вираз є ніби другорядним.