Сортировка массива

Федеральное государственное  автономное 
образовательное учреждение 
высшего профессионального образования 
«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Институт космических  и информационных технологий 
Кафедра информатики

УТВЕРЖДАЮ

Заведующий кафедрой

_____  _______________

подпись      инициалы, фамилия

«____»  ________ 2012 г.

 

 

 

 

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №2

Сортировка массива

 

 

 

 

 

 

Гринин К.Е.

Преподаватель                         ___________    ______________

    подпись, дата            инициалы, фамилия

Санников С.О.

КИ11-17Б

031102966

Студент    __________   ________________   ___________   ______________ 
          номер группы    номер зачетной книжки          подпись, дата          инициалы, фамилия

 

 

 

 

 

 

Красноярск 2013

 

ЛАБОРАТОРНАЯ  РАБОТА №2

Сортировка массива

 

Цель работы

 

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

 

Постановка задачи

 

Написать программу, выполняющую сортировку одномерного массива с использованием алгоритмов:

1) шейкерная сортировка;

2) сортировка Шелла.

 

Краткие теоретические  сведения

 

1 Шейкерная сортировка

 

Шейкерная сортировка – разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства. Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения. Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

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

Лучший случай для этой сортировки – отсортированный массив (О(n)), худший – отсортированный в обратном порядке (O(n²)).

Наименьшее число сравнений  в алгоритме Шейкер-сортировки C=N-1. Это соответствует единственному  проходу по упорядоченному массиву (лучший случай).

 

2 Сортировка Шелла

 

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

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

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

 

Описание программной  реализации

 

Программа, реализующая сортировку массива, написана на языке C# с использованием графического интерфейса. Главное окно программы представлено на рисунке 1.

 

Рисунок 1 – Главное окно программы

 

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

Листинг программного кода функций, выполняющих сортировку массива  шейкерным методом и методом  Шелла представлен ниже.

 

// шейкерная сортировка

private void SheikerSort(int[] arr)

        {

            int n = arr.Length;

            int l, r, i, k, tmp;

            int exchg = 0;

            int compr = 0;

            k = l = 0;

            r = n - 2;

 

            while (l <= r)

            {

                for (i = l; i <= r; i++)

                {

                    if (arr[i] > arr[i + 1])

                    {

                        tmp = arr[i];

                        arr[i] = arr[i + 1];

                        arr[i + 1] = tmp;

                        k = i;

                        exchg++;

                        PrintArray(arr);

                    }

                    compr++;

                }

                r = k - 1;

                for (i = r; i >= l; i--)

                {

                    if (arr[i] > arr[i + 1])

                    {

                        tmp = arr[i];

                        arr[i] = arr[i + 1];

                        arr[i + 1] = tmp;

                        k = i;

                        exchg++;

                    }

                    compr++;

                }

                l = k + 1;

            }

        }

 

// сортировка Шелла

private void ShellSort(int[] arr)

        {

            int exchg = 0;

            int compr = 0;

            int j;

            int step = arr.Length / 2;

 

            while (step > 0)

            {

                for (int i = 0; i < (arr.Length - step); i++)

                {

                    j = i;

                    while ((j >= 0) && (arr[j] > arr[j + step]))

                    {

                        int tmp = arr[j];

                        arr[j] = arr[j + step];

                        arr[j + step] = tmp;

                        j--;

                        exchg++;

                        compr++;

                    }

                    compr++;

                }

                step = step / 2;

            }

        }

Руководство пользователя

 

В текстовое поле главного окна программы введите элементы массива, разделяя их пробелом, или нажмите кнопку «Сгенерировать» с указанием числа элементов.

Выберите метод сортировки из выпадающего списка и нажмите  «Отсортировать».

Результат сортировки представлен  в поле «Отчет о работе алгоритма».

Для сохранения отчета нажмите  кнопку «Сохранить в файл».

 

Пример работы программы

 

Примеры работы программы представлены на рисунках 2-4.

 

 

Рисунок 2 – Пример работы программы. Демонстрируется шейкерная сортировка

 

 

Рисунок 3 – Пример работы программы. Демонстрируется сортировка Шелла

Рисунок 4 – Пример отчета о работе алгоритма

 

Сравнение алгоритмов

 

Для сравнения алгоритмов составим таблицу результатов тестирования. Отсечку времени будем производить в тактах процессора, целевой массив будем генерировать случайно (если не указано иное).

 

Таблица 1 – Тестирования алгоритмов сортировки

№ опыта	Размер массива	Шейкерная сортировка			Сортировка Шелла
		Число обменов	Число сравнений	Время выполнения	Число обменов	Число сравнений	Время выполнения
1	10	14	26	5262	5	27	633
2	15	47	72	18561	27	61	10053
3	20	102	153	39632	47	109	17650
4	20 (отсортирован)	0	19	2	0	62	3
5	20 (отсортирован в обратном порядке)	190	190	71518	44	106	16629

 

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

 

Выводы

 

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