3. Внутренняя сортировка данных методом простых вставок. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:

эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
эффективен на наборах данных, которые уже частично отсортированы;
это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
может сортировать список по мере его получения;
использует O(1) временной памяти, включая стек.

Минусом же является высокая сложность алгоритма: O(n²).

Принцип действия:

Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные.

Пример

К 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

i=1 503

i=2 087 503

i=3 087 503 512

i=4 061 087 503 512

И.т.д.

Фрагмент программы:

for (int i = 0; i < size - 1; ++i) {

/* устанавливаем начальное значение минимального индекса */

int min_i = i;

/* находим минимальный индекс элемента */

for (int j = i + 1; j < size; ++j) {

if (array[j] < array[min_i]) {

min_i = j;

}

/* меняем значения местами */

int temp = array[i];

array[i] = array[min_i];

array[min_i] = temp;

}

4. Внутренняя сортировка данных методом Шелла. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм.

Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

отсутствие потребности в памяти под стек;
отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Принцип действия:

Сортировка Шелла также является модификацией сортировки вставками. Метод данной сортировки основан на группировке элементов массива на несколько групп, например, на 8 групп по 2 записи. При этом элементы каждой группы отстоят друг от друга «расстоянии» h. Элементы каждой группы упорядочиваются методом простой вставки. Далее элементы массива снова группируются: на 4 группы по 4 элемента. Далее группировка выполняется на 8 групп по 2 элемента, и процесс завершается сортировкой всех элементов массива. При такой группировке упорядоченность элементов осуществляется большими скачками, что значительно сокращает количество перестановок.

Выигрыш по сравнению с методом простых вставок составляет примерно 50%

Для больших N (скажем, N = 10000) преимущество метода Шелла станет ещё заметнее.

Алгоритм Шелла имеет сложность ~N^3/2. И хотя это несколько хуже, чем N*logN, все-таки эта сортировка относится к улучшенным.

Пример:

Пусть дан список и выполняется его сортировка методом Шелла, а в качестве значений выбраны .