Программирование - это просто
Advertisement
Главная arrow Уроки программирования arrow Алгоритмы arrow Исследование алгоритма сортировки методом Шелла.
28.02.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Исследование алгоритма сортировки методом Шелла. Печать E-mail
Автор megabax   
03.01.2013 г.
Циклы

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

Это последний урок из серии "Алгоритмы", публикуемый в бесплатном разделе. Начиная со следующего, публикация уроков будет продолжена в платном разделе. В бесплатном же разделе, возможно, иногда будут публиковать некоторые статьи, посвященные алгоритмам.

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

На прошлом уроке мы запрограммировали и протестировали алгоритм сортировки методом Шелла. И результат нас несколько разочаровал. Может, мы неудачно выбрали последовательность проходов? Давайте проверим другие варианты.

Но сначала мы чуть чуть изменим метод ShellSort:

        public void SortShell(int[] a, int N)

        {

            int i, j, gap, k;

            TType x;

            int count = list.Count;

            for (k = 0; k < N; 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;

                }

            }

        }

Как видим, последовательность чисел мы теперь будет задавать в параметре. И попробуем задать другую последовательность чисел, вместо 9,5,3,2,1 зададим 15,9,5,3,2,1 (выделено маркером):

        private void btnShell_Click(object sender, EventArgs e)

        {

            int count = 240000;

            InitInt(count);

            DateTime dt1 = DateTime.Now;

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

            intsort.SortShell(a,6);

            DateTime dt2 = DateTime.Now;

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

        }

Теперь время сортировки составило 50 секунд (в прошлый раз было 84 сек.):

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

Теперь попробуем поменять числа в последовательности, например, попробуем так: 15,11,5,3,2,1. Время получилось 47 секунд. Как видим, изменилось мало. Попробуем добавить впереди еще одно число: 17,15,11,5,3,2,1. Время 46 секцнд:

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

Тоже мало что изменилось. А если первое число не 17, а например, 25? Получается 31 секунда:

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

Сделаем еще более длинную последовательность: 50, 45, 35, 25, 15, 11, 5, 3, 2, 1. У нас получается вообще 15 секунд:

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

Какую закономерность мы наблюдаем? Чем больше чисел в последовательности, тем более быстро идет сортировка! Если честно это уже давно примечено. Так, согласно Википедии, существует ряд стандартных последовательностей для алгоритма сортировки Шелла, например 2i-1≤N, где N - число элементов в сортируемом массиве. При этом сложность алгоритма, по утверждению Википедии, должна быть N3/2. Давайте это проверим. Для начала переделаем слегка метод SortShell:

        public void SortShell()

        {

            int i, j, gap, k;

            TType x;

            int count = list.Count;

            int N = SequenceForShell.Count;

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

            {

                gap = SequenceForShell[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;

                }

            }

        }

SequenceForShell - это список чисел, он должен быть объявлен в классе Sort:

    class Sort<TType>

    {

        //сортируемый массив

        public List<TType> list;

 

        //Последовательность для сортировки методом Шелла

        public List<int> SequenceForShell;

...

И для инициализации этого массива предусмотрим метод CreateSequenceForShell:

        public void CreateSequenceForShell(int N)

        {

            int curritem = 1;

            int i = 2;

            if (SequenceForShell == null) SequenceForShell = new List<int>();

            SequenceForShell.Clear();

            while (curritem <= N)

            {

                SequenceForShell.Add(curritem);

                curritem = Convert.ToInt32(Math.Pow(2,i)-1);

                i++;

            }

        }

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

        private void btnStart_Click(object sender, EventArgs e)

        {

            lbIntAfter.Items.Clear();

            lbIntBefore.Items.Clear();

            lbStringAfter.Items.Clear();

            lbStringBefore.Items.Clear();

            InitInt(amount);

            InitString(amount);

            ShowInt(lbIntBefore, intsort.list);

            ShowString(lbStringBefore, stringsort.list);

            intsort.CreateSequenceForShell(amount);

            intsort.SortShell();

            stringsort.CreateSequenceForShell(amount);

            stringsort.SortShell();

            ShowInt(lbIntAfter, intsort.list);

            ShowString(lbStringAfter, stringsort.list);

        }

Замечу сразу, что тестировать обязательно, потому что изменив что то в программном коде, мы можем его поломать. А значит, нужно убедиться, что все в порядке, ничего "не полетело".

И так, проверим работу алгоритма:

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

И приступим к его тестированию:

        private void btnShell_Click(object sender, EventArgs e)

        {

            int count = 240000;

            InitInt(count);

            DateTime dt0 = DateTime.Now;

            DateTime dt1 = DateTime.Now;

            intsort.CreateSequenceForShell(count);

            intsort.SortShell();

            DateTime dt2 = DateTime.Now;

            MessageBox.Show("Отсортировано " + count.ToString() + " элементов. "+

                "время нач. создания массива " + dt0.ToString() + " Время нач. сортировки: " + dt1.ToString() + " кон.: " + dt2.ToString());

        }

И что мы видим? Действительно, работать стало не просто быстро, а очень быстро. 240 тыс. элементов примерно за 1 секунду:

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

А если миллион? То получается около двух секунд:

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

А вот если взять 10 миллионов элементов, то время сортировки растягивается уже на 8 секунд:

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

При чем заметьте, мы увеличили размер массива в 10 раз, а время сортировки возросло всего лишь в 4 раза. Эффект налицо!

Для прикола попробуем отсортировать сто миллионов элементов. Получилось 2 минуты с копейками:

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

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

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

Последнее обновление ( 03.01.2013 г. )
 
Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги