Алгоритмы сортировки данных - Реферат

Содержание

Введение 3

Алгоритмы сортировки: понятие, история 4

Сравнительная характеристика алгоритмов сортировки данных 10

Заключение 17

Список литературы 18

Введение (выдержка)

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

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

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

- собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены.

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

Основная часть (выдержка)

Алгоритмы сортировки: понятие, история

Алгоритм сортировки — это алгоритм для упорядочивания элементов. Проблема сортировки данных является актуальной в наше время, в связи с большой востребованностью и гибкостью, в плане разработки алгоритма [2, 4].

Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы [3].

Практически каждый алгоритм сортировки можно разбить на три части:

• сравнение, определяющее упорядоченность пары элементов;

• перестановку, меняющую местами пару элементов;

• сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены. [3, 4]

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

Важное практическое значение проблема сортировки данных в больших массивах впервые приобрела в США в середине XIX века. В 1840 году там был создан центральный офис переписи населения, куда стекались первичные данные из всех штатов. В ходе переписи было опрошено 17 069 453 человек, каждая анкета состояла из 13 вопросов. Объем полученных данных был столь велик, что их обработка традиционным ручным способом потребовала непомерных затрат труда и времени. Ситуация усугублялось необходимостью проведения постоянных сверок и пересчетов из-за допускаемых при ручной сортировке данных ошибок. С каждой новой переписью, которая проводилась раз в десять лет, объем обрабатываемой информации, а вместе с ним стоимость и длительность обработки данных возрастали [9].

Так, ручная обработка данных переписи населения 1880 года (50 189 209 человек) потребовала привлечения сотен служащих и длилась семь с половиной лет. Перед переписью 1890 года для решения проблемы сортировки данных в очень больших массивах информации по инициативе бюро переписи был проведен конкурс на лучшее электромеханическое сортировочное оборудование, которое сделало бы сортировку данных более эффективной — более быстрой, точной и дешевой. Конкурс выиграл американский инженер и изобретатель немецкого происхождения Герман Холлерит (Herman Hollerith), разработавший оборудование для работы с перфокартами — электрическую табулирующую систему, ставшую известной как Hollerith Electric Tabulating System [1, 5].

Заключение (выдержка)

Таким образом, существующие алгоритмы сортировки массивов значительно различаются по уровню сложности, скорости, устойчивости, требованиям к памяти и другим параметрам. Однако практически каждый алгоритм оказывается наиболее удобным в какой-либо конкретной ситуации. Востребованными являются даже очень медленные алгоритмы, которые из-за своей простоты находят применение в образовательных целях. [1, 2, 3, 4]

Если сравнивать алгоритмы сортировки по скорости и устойчивости, то для большинства устойчивых алгоритмов характерно среднее число операций n2, а большинство алгоритмов неустойчивой сортировки являются более быстрыми. Среднее число операций здесь меньше n2 (n log n для большинства алгоритмов) [1,3].

Литература

1. Алгоритмы сортировки [Электронный ресурс]: Википедия. – Режим доступа https://ru.wik**edia.org/wiki/Алгоритм_сортировки

2. Временная сложность алгоритма [Электронный ресурс]: Википедия. – Режим доступа https://ru.wik**edia.org/wiki/Временная_сложность_ алгоритма.

3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2000. – 1328 с.

4. Керниган Б., Пайк Р. Практика программирования. – Вильямс, 2004. 288с.

5. Непрактические сортировки – бессмысленные и беспощадные [Электронный ресурс]: Habr. – Режим доступа https://h**br.com/ru/ post/198114/

6. Прата С. Язык программирования С: лекции и упражнения. – Диа- Софт, 2018. – 928 с.

7. Рублев В.С. Основы теории алгоритмов. – М.: Научный мир, 2008. – 136 с.

8. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. – ДиаСофт 2001. – 704 с.

9. Шагбазян, Д.В. Алгоритмы сортировки. Анализ, реализация, применение: учебное пособие / Д.В. Шагбазян, А.А. Штанюк, Е.В. Малкина. – Нижний Новгород: Нижегородский госуниверситет, 2019. – 42 с.

10. Эзотерические сортировки Дэвида Морган-Мара [Электронный ресурс]: Habr. – Режим доступа https://h**r.com/ru/post/161835/