Алгоритм сортировки методом Шелла.

Автор megabax

31.12.2012 г.

Циклы

Алгоритм сортировки методом Шелла.

Исходники к уроку можно скачать здесь.

Данный алгоритм сортировки был изобретен Д. Л. Шеллом. Его суть состоит в том, что сначала мы сортируем, например, элементы отстоящие друг от друга на три позиции, потом на две и наконец, производим сортировку смежных элементов. Все эти сортировки делаем методом вставки. На самом деле могут быть другие шаги сортировки методом Шелла, главное, что бы последний шаг был равен 1. Источники утверждают*, наилучшая скорость достигается при последовательности 9,5,3,2,1. Вот сегодня мы и реализуем алгоритм сортировки Шелла именно с такой последовательностью. В рамках данного урока мы пока поверим источнику на слово, но в будущем обязательно потестим алгоритмы, что бы проверить, так ли это, а так же попробуем обосновать результаты наших тестов математически, в общем, займемся исследованиями. Но это в будущем, а сейчас просто закодим алгоритм:

public void SortShell()

{

int i, j, gap, k;

TType x;

int[] a={9,5,3,2,1};

int count = list.Count;

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

{

gap = a[k];

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

{

x = list[i];

for (j = i - gap; j >= 0 && isLess(x,list[j]); j = j - gap)

{

list[j + gap] = list[j];

}

list[j + gap] = x;

}

Приведенный метод мы вставляем в исходники прошлого урока, прямо в класс Sort<TType>. Лучше всего, сделать копию этих исходников, так как нам надо будет изменять еще и тестовый пример. Впрочем, изменять немного, просто все вызовы метода SortInsert заменим на SortShell, а внешний вид программы у нас не поменяется. Так что запускаем ее после наших изменений и тестим:

Теперь посмотрим, как же алгоритм работает, для этого создадим какой либо тестовый пример, например 3,9,35,31,7,2,5,1,8,3. Навесим этот пример на кнопочку "Наш пример":

private void btnOur_Click(object sender, EventArgs e)

{

intsort = new Sort<int>(Comparer<int>.Default);

intsort.list.Add(3);

intsort.list.Add(9);

intsort.list.Add(35);

intsort.list.Add(31);

intsort.list.Add(7);

intsort.list.Add(2);

intsort.list.Add(5);

intsort.list.Add(1);

intsort.list.Add(8);

intsort.list.Add(3);

lbIntAfter.Items.Clear();

lbIntBefore.Items.Clear();

ShowInt(lbIntBefore, intsort.list);

intsort.SortInsert();

ShowInt(lbIntAfter, intsort.list);

}

И через отладчик посмотрим, как идет процесс сортировки:

Исходный массив	3,9,35,31,7,2,5,1,8,3
gap=9	3,9,35,31,7,2,5,1,8,3
gap=5	2,5,1,8,3,3,9,35,31,7
gap=3	2,3,1,7,5,3,8,35,31,9
gap=2	1,3,2,3,5,7,8,9,31,35
gap=1	1,2,3,3,5,7,8,9,31,35

Так же на ютубте есть прикольный ролик, оригинально иллюстрирующий алгоритм сортировки методом Шелла http://www.youtube.com/watch?v=CmPA7zE8mx0.

Теперь потестим и сравним алгоритм сортировки методом вставки и методом Шелла. Для начала алгоритм методом вставки:

private void btnInsertTest_Click(object sender, EventArgs e)

{

int count = 30000;

InitInt(count);

DateTime dt1 = DateTime.Now;

intsort.SortInsert();

DateTime dt2 = DateTime.Now;

MessageBox.Show("Отсортировано " + count.ToString() + " элементов. Время нач.: " + dt1.ToString() + " кон.: " + dt2.ToString());

}

Смотрим результат (11 секунд).

Теперь посмотрим метод Шелла:

private void btnShell_Click(object sender, EventArgs e)

{

int count = 30000;

InitInt(count);

DateTime dt1 = DateTime.Now;

intsort.SortShell();

DateTime dt2 = DateTime.Now;

MessageBox.Show("Отсортировано " + count.ToString() + " элементов. Время нач.: " + dt1.ToString() + " кон.: " + dt2.ToString());

}

И вот результат работы этот программы:

Как видим, время выполнения порядка 1 секунды, примерно в десять раз быстрее.

Теперь попробуем увеличить количество сортируемых элементов до 60 тыс.:

private void btnInsertTest_Click(object sender, EventArgs e)

{

int count = 60000;

InitInt(count);

DateTime dt1 = DateTime.Now;

intsort.SortInsert();

DateTime dt2 = DateTime.Now;

MessageBox.Show("Отсортировано " + count.ToString() + " элементов. Время нач.: " + dt1.ToString() + " кон.: " + dt2.ToString());

}

private void btnShell_Click(object sender, EventArgs e)

{

int count = 60000;

InitInt(count);

DateTime dt1 = DateTime.Now;

intsort.SortShell();

DateTime dt2 = DateTime.Now;

MessageBox.Show("Отсортировано " + count.ToString() + " элементов. Время нач.: " + dt1.ToString() + " кон.: " + dt2.ToString());

}

Смотрим время сортировки методом вставки:

как видим, оно возросло до 43 секунды, примерно в четыре раза. А метод Шелла? Давайте и его проетстим:

Почти пять секунд. А если увеличить размер массива до 240 тыс., в 4 раза? Давайте проверим:

84 секунды. Короче, примерно в 16 раз больше. Выходит, метод Шелла не такой уж хороший, хотя работает и быстрее алгоритма вставки. Как говорит источник*, количество сравнений при использовании алгоритма Шелла в степени 1.2 от числа элементов в сортируемом массиве. Но эксперимент показал, что это вовсе не так.

Исходники к уроку можно скачать здесь.

* Г. Шилдт, "Теория и практика С++".

Последнее обновление ( 31.12.2012 г. )

« След.		Пред. »

Вернуться