Реферат (1078488)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. Н. Э. Баумана

КАФЕДРА КОНСТРУИРОВАНИЯ И ПРОИЗВОДСТВА ЭЛЕКТРОННОЙ

АППАРАТУРЫ

Отчет о выполнении

командного практического задания

«Сортировка Вставками и сортировка Шелла»

по курсу «Функциональная логика и теория алгоритмов»

Выполнили: студенты гр. ИУ4-33

Полётин Матвей

Грачёв Максим

Забнев Владимир

Ларичев Антон

Кострица Олег

Проверил: д.т.н., профессор, профессор каф. ИУ-4

Л.А. Зинченко

Москва 2014

Содержание

1. Начальные условия

2. Анализ задачи

3. Выполнение работы

4. Принцип исполнения

5. Реализуемый функционал

6. Вывод

Начальные условия

Цель работы: Изучить основные алгоритмы постороения сортировок вставками и Шелла. Опытным путем ознакомится с преимуществами и недостатками данных алгоритмов предложить их возможное усовершенствование.

Задача: Составить программу на языке программирования C или C++, реализующую сортировку вставками и сортировку Шелла для произвольной переданной последовательности натуральных чисел.

Реализуемые функции:

• ввод последовательности чисел с клавиатуры;

• передача набора чисел в пограмму через текстовый файл;

• сортировка вставками;

• сортировка Шелла;

• вывод результата на экран пользователя.

Анализ задачи

Технические аспекты

Среда разработки: Выполненная программа была составлена, отлажена и протестирована в интегрированной среде разработки Microsoft Visual Studio 2013 Update 3, по причине её доступности по студенческой лицензии, надежности и простоты в использовании.

Язык программирования: Языком разработки данной программы послужил язык программирования Си, как наиболее точно отвечающий поставленным задачам.

Способы ввода: Основными способами задание числовой последовательности были выбраны задание через символьный ввод с клавиатуры и передание строки из заранее подготовленного файла.

Реализация сортировок

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

Однако алгоритм сортировки вставками обладает несколькими отличительными преимуществами:

• эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

• эффективен на наборах данных, которые уже частично отсортированы;

• это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

• может сортировать список по мере его получения;

• использует O(1) временной памяти, включая стек. может работать значительно быстрее за счёт бинарного поиска

Минусы:

• Очень высокая вычислительная сложность алгоритма O(n²) (при использовании стандартного алгоритма).

Описание

На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора.

Анализ алгоритма

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — O(n²). Однако, данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей.

Псевдокод

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

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

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

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

Описание

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

Применение

Сортировка Шелла сейчас используется в серьезных приложений используется редко. Он выполняет несколько операций и имеет более высокий коэффициент промахов кэша, чем быстрая сортировка. Однако, поскольку он может быть реализован с помощью небольшого кода и не использует стек вызовов, в некоторых реализациях функции QSort в стандартной библиотеке C, направленных на встраиваемые системы используется вместо быстрой сортировки. Сортировка Шелла, например, используется в библиотеке uClibc. По тем же причинам, реализация этого алгоритма присутствует в ядре Linux.

Сортировка Шелла также может служить в качестве суб-алгоритма интроспективного рода, для сортировки коротких подмассива и предотвратить патологическое замедление, когда глубина рекурсии превышает заданный предел. Используют этот принцип, например, в компрессоре bzip2.

Псевдокод

# Отсортировать массив a[0...n-1]. gaps = [701, 301, 132, 57, 23, 10, 4, 1] # Начать с наибольшего пропуска и понижать пропуск до 1 foreach (gap in gaps) { # Совершать сортировку вставками для заданного интервала # Первые элементы интервала a[0..gap-1] уже в промежуточном порядке # продолжать добавлять по одному элементу, пока массив не # отсортирован на разве for (i = gap; i < n; i += 1) { # добавить a[i] к элментам, отсортированным на участке # сохранить a[i] в temp очисть место в позиции i temp = a[i] # вернуться выше к отсорированному участку, пока правильное место для a[i] не найдено for (j = i; j >= gap and a[j - gap] > temp; j -= gap) { a[j] = a[j - gap] } # расположить temp (оригинальное a[i]) в его праильное положение a[j] = temp } }

Выполнение работы

Алгоритм работы программы:

• Выбор способа ввода;

• Ввод с клавиатуры или чтение из файла;

• Выбор сортировки;

• Выполнение сортировки;

• Вывод результата работы алгоритма на экран.

Более подробно алгоритм работы программы представлен на блок-схеме (смотри приложение).

Струкрура файла ввода: Текстовый файл для передачи информации о сортируемом списке состоит из информации о количестве элементов и посимвольной их записи. В первой строке вводится общее количество элементов. Во второй строке происходит ввод чисел, которые необходимо отсортировать, через символ-разделитель пробел. Ввод из файла создан для более быстрого и удобно взаимодействия пользователя с программой и комфортной работы с большим объемом массива чисел. Синтаксис файла “in.txt” показан на рисунке ниже.

Реализуемый функционал

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

Ввод с клавиатуры: Пользователь имет возможность задать массив чисел непосредственным вводом с клавиатуры внутри программы.

Проверка ввода с клавиатуры:

Ввод на основе файла: Из файла “in.txt”, который располагается в корне папки с исполняем файлом происходит считывание входных данных.

Проверка ввода из фала: В программе частично реализованы проверки на некорректный ввод. В случае отсутствия соответствующего файла на эран выходит собщение и программа прекращает свое исполнение.

Выводы

Результатом данной работы можно считать программу, составленную на языке Си и реализующую сортирову вставками и сортировку Шелла для произвольной переданной последовательности натуральных чисел.

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

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

Приложение

Структурная схема программы

Струкрурная схема сортировки вставками

Структурная схема сортировки Шелла

15

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов домашнего задания