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

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

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

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

§ отсутствие потребности в памяти под стек;

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

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

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

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

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

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

Пример:

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

На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , , .

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.

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

/* Пример из книги Герберта Шилдта */

void shell(char *items, int count)

{

register int i, j, gap, k;

char x, a[5];

a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

for(k=0; k < 5; k++) {

gap = a[k];

for(i=gap; i < count; ++i) {

x = items[i];

for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)

items[j+gap] = items[j];

items[j+gap] = x;

}

}

}

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

Сортировка простыми обменами, сортировка пузырьком — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n ²), Число сравнений: N²

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.

Сортировка очень медленная, но если скорость не главное, можно применить и её.

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

Сортировка обменом основана на многократном обходе массива чисел a₁, a₂,… a_n. При каждом обходе сравниваются два соседних элемента a_i и a_i+1. Если элементы неупорядочены, то они меняются местами. В следствие последовательных перестановок, например, при упорядочивании массива по возрастанию, постепенно продвигается вправо и становится на свое место максимальный элемент массива. При втором обходе – длина массива уменьшается на 1 (исключается последний элемент) и процесс повторяется. Последний обход выполняется для массива из 2 элементов.

Пример:

Отсортировать массив чисел M={5, 4, 8, 2, 9} по возрастанию.

1-ый просмотр. Рассматривается весь массив.

{i - номер первого элемента проверяемой (сравниваемой) пары}.

i=1		>
меняем местами
i=2				<
не меняем
i=3						>
меняем
i=4								<
не меняем

Число 9 встало на свое место и в последующих просмотрах его можно не рассматривать.

2-ой просмотр. Рассматривается весь массив, с первого элемента до предпоследнего.

i=1		<
не меняем
i=2				>
меняем
i=3						<
не меняем

Число 8 также встало на свое место. Говорят, «всплыл» еще один «пузырек».

3-ий просмотр. Рассматривается часть массива без последних двух элементов.

i=1		>
меняем
i=2				<
не меняем

Число 5 встало на свое место.

4-ый просмотр. Рассматривается последняя пара элементов.

i=1		<
не меняем

В итоге имеем отсортированный массив:

Пример программы:

#include<stdio.h>

#define N 1000

int main() {

int n, i, j;

int a[N];

// считываем количество чисел n

scanf("%d", &n);

// считываем n чисел

for(i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

for(i = 0; i < n; i++) {

// сравниваем два соседних элемента.

for(j = 0; j < n - i - 1; j++) {

if(a[j] > a[j+1]) {

// если они идут в неправильном порядке, то

// меняем их местами.

int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp;

}

}

}

}

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

Быстрая сортировка часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Достоинства: быстрота, простота реализации, хорошо сочетается с механизмами кэширования и виртуальной памяти. Требует лишь дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае памяти). Существует эффективная модификация (алгоритм Седжвика) для сортировки строк — сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.

Недостатки:

§ Сильно деградирует по скорости (до ) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort, или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.

§ Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки меньшей из двух частей массива, глубина рекурсии гарантированно не превысит .

§ Неустойчив — если требуется устойчивость, приходится расширять ключ.

Эффективность:

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод.

Оценим эффективность метода быстрой сортировки. На каждом шаге делим массив на две части, для каждой из этих частей – N/2 сравнений (всего – 2*N/2=N), затем на 2-ом шаге снова делим, получаем N/4 сравнений (4*N/4=N) и т.д. Так как глубина рекурсии (количество разбиений) равна Log₂N, а количество сравнений на каждом уровне – N, то сложность алгоритма С = Θ (N*logN).

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

Реализация данного метода сортировки основывается на рекурсивном вызове процедуры упорядочивания. Она была разработана в 1962 году профессором Оксфордского университета К.Хоаром.

Быстрая сортировка основывается на принципе «разделяй и властвуй» и является улучшенной модификацией пузырьковой сортировки. Сначала берется весь массив и частично упорядочивается особенным образом: выбирается серединный элемент, назовем его ключом, а остальные элементы упорядочиваются относительно этого ключа так, чтобы слева располагались элементы меньшие ключа (если массив сортируется по возрастанию), а справа – большие. В итоге ключевой элемент встает на «свое место». Затем к левой и правой частям (относительно ключа) применяется этот же метод, то есть выбирается новый ключ и упорядочивание подмассива относительно его. И так до тех до тех пор, пока каждая из частей не будет содержать ровно один элемент.

Пример:

Рассмотрим работу данного метода на примере сортировки массива А={6, 23, 17, 8, 14, 25, 6, 3, 30, 7} по возрастанию.

Выбирается серединный элемент массива – key=A[5]=14. Просматривая левую часть массива (слева направо) найдем элемент, больший key, а в правой части ищем элемент (двигаясь справа налево), меньший key. Затем эти элементы меняем местами.

(i,j- индексы левой и правой половины соответственно)

i=2 j=10

6 23 17 8 14 25 6 3 30 7

Продолжаем поиск элементов для перестановки:

i=3 j=8

6 7 17 8 14 25 6 3 30 23

i=5 j=7

6 7 3 8 14 25 6 17 30 23

i=6 j=7

6 7 3 8 6 25 14 17 30 23

i=j=6

6 7 3 8 6 25 17 30 23

В итоге ключевой элемент стоит на «своем месте», т.е. всплыл первый «пузырек». Слева (с 1-го по 5-ый элемент) и справа (с 7-го по 10-ый) от ключа элементы еще не упорядочены, применим к ним тот же метод, вызвав процедуру быстрой сортировки. Это уже будет второй уровень рекурсии.

Пример программы:

int n, a[n]; //n - количество элементов

void qs(int* s_arr, int first, int last)

{

int i = first, j = last, x = s_arr[(first + last) / 2];

do {

while (s_arr[i] < x) i++;

while (s_arr[j] > x) j--;

if(i <= j) {

if (i < j) swap(s_arr + i, s_arr + j);

i++;

j--;

}

} while (i <= j);

if (i < last)

qs(s_arr, i, last);

if (first < j)

qs(s_arr, first,j);

}