Программирование - это просто
Advertisement
Главная arrow Уроки программирования arrow Алгоритмы arrow Алгоритм сортировки методом Шелла.
28.02.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Алгоритм сортировки методом Шелла. Печать E-mail
Автор 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 г. )
 
« След.   Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги