Cортировка Шелла (ShellSort)

Билет №11 Сортировка. Классификация алгоритмов сортировки.

Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …).

Сортировки бывают следующих видов:

1) Обменные: Пузырьком, перемешиванием, гномья, быстрая. Расческой, сортировка чет-нечет

2) Выбором: выбором, пирамидальная, плавная

3) Вставками: вставками, Шелла, деревом

4) Слиянием

5) Без сравнений: подсчетом, поразрядная, блочная

6) Гибридные: Introsort, Timsort

Алгоритмы:

1) простые и понятные, но неэффективные для больших массивов(сложность O(N²))

· метод пузырька

· метод выбора

2) сложные, но эффективные(сложность O(N· log N))

· " быстрая сортировка" (Quick Sort)

· сортировка " кучей" (Heap Sort)

· сортировка слиянием

· пирамидальная сортировка

Квадратичные и субквадратичные алгоритмы

Сортировка выбором(SelectSort)

Найти минимальный элемент и поставить на первое место (поменять местами с A[0]). Из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[1]), и т.д.

Пример:

for (i = 0; i< N-2; i++)

{nMin = i;

for (j= i+1; j< N; j++)

if (A[j] < A[nMin]) nMin: =j;

if (nMin! = i)

{

c=A[i];

A[i]=A[nMin];

A[nMin]=c;

}

}

Сортировка пузырьком(BubbleSort)

Самый маленький (" легкий") элемент перемещается вверх (" всплывает"). Начиная снизу, сравниваем два соседних элемента; если они стоят " неправильно", меняем их местами. За 1 проход по массиву один элемент (самый маленький) становится на свое место.

Для сортировки массива из N элементов нужен
N-1 проход (достаточно поставить на свои места N-1 элементов).

Пример:

for (i=0; i< N-1; i++)

for (j=N-2; j< = i; j--)

if (A[j] > A[j+1])

{с: = A[j];

A[j]: = A[j+1];

A[j+1]: = с;

}

Условие Айверсона(Флаг): Идея– если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны.

Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход. Пример:

i = 0;

do

{flag = 0; // сбросить флаг

for (j=N-1; j > = 0; j--)

if (A[j] > A[j+1])

{ с = A[j];

A[j] = A[j+1];

A[j+1] = с;

flag = 1; // поднять флаг

}

i = i + 1;

}

while flag; //продолжать пока флаг поднят

3) Сортировка простыми вставками (InsertSort) (в презентации примера нет)

Cортировка Шелла (ShellSort)

Работает с элементами отстоящими друг от друга на расстоянии d

Сначала d=[n/2]. На следующих проходах d меняется по закону d=[d/2].