Реферат
«Алгоритмы сортировки данных»
- 17 страниц
Введение 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/
| Тема: | «Алгоритмы сортировки данных» | |
| Раздел: | Информатика | |
| Тип: | Реферат | |
| Страниц: | 17 | |
| Цена: | 300 руб. |
Закажите авторскую работу по вашему заданию.
- Цены ниже рыночных
- Удобный личный кабинет
- Необходимый уровень антиплагиата
- Прямое общение с исполнителем вашей работы
- Бесплатные доработки и консультации
- Минимальные сроки выполнения
Мы уже помогли 24535 студентам
Средний балл наших работ
- 4.89 из 5
написания вашей работы
У нас можно заказать
(Цены могут варьироваться от сложности и объема задания)
682 автора
помогают студентам
42 задания
за последние сутки
10 минут
время отклика
Основные алгоритмы сжатия данных
Курсовая работа:
Проектирование автоматизированной системы «станок-качалка-насос (скн)»
Курсовая работа:
Аппроксимация табличных данных алгебраическими полиномами методом наименьших квадратов (Pascal)
Курсовая работа:
Создание базы данных Access. Ремонт компьютерной техники.
Шпаргалка:
Ответы по информационным технологиям
