Файл: Алгоритмы сортировки данных.pdf

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

Внешняя сортировка является сортировкой данных, которые расположены на периферийных устройствах и не вмещаются в оперативную память, то есть когда применить одну из внутренних сортировок невозможно. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам и другим подобным устройствам^[35] [1, 2, 4].

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

Заключение

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Баула В. Г. Архитектура ЭВМ и операционные среды / В. Г. Баула, А. Н. Томилин, Д. Ю. Волканов. – М.:Academia, 2011 – 336 с.
2. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – 240 с.
3. Гук М. Аппаратные средства IBM PC. Энциклопедия / М. Гук. – СПб.:Питер, 2014. – 1072 с.
4. Максимов Н. В. Архитектура ЭВМ и вычислительные системы / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. – М.: Форум, Инфра-М, 2013. — 512 с.
5. Новожилов О. П. Архитектура ЭВМ и систем / О. П. Новожилов. – М.:Юрайт, 2011 – 528 с.
6. Орлов С. А. Организация ЭВМ и систем: Учебник для вузов / С. А. Орлов. – СПб.: Питер, 2014. – 688 с.
7. Паттерсон Д. Архитектура компьютера и проектирование компьютерных систем / Д. Паттерсон, Д. Хеннеси. – СПб.: Питер, 2012. – 784 с.
8. Серрано Н. Сервисы, архитектура и унаследованные системы / Н. Серрано, Х. Эрнантес, Г. Галлардо // Открытые системы. – М., 2014. – №08. – С. 76-81.
9. Симонович С. Информатика. Базовый курс / С. Симонович. – СПб.: Питер, 2016. – 640 с.
10. Таненбаум Э. Архитектура компьютера / Э. Таненбаум, Т. Остин. – СПб.: Питер, 2015. – 816 с.

1. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 145. ↑

2. Новожилов О. П. Архитектура ЭВМ и систем / О. П. Новожилов. – М.:Юрайт, 2011 – С. 256. ↑

3. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 163. ↑

4. Орлов С. А. Организация ЭВМ и систем: Учебник для вузов / С. А. Орлов. – СПб.: Питер, 2014. – С. 472. ↑

5. Гук М. Аппаратные средства IBM PC. Энциклопедия / М. Гук. – СПб.:Питер, 2014. – С. 275. ↑

6. Серрано Н. Сервисы, архитектура и унаследованные системы / Н. Серрано, Х. Эрнантес, Г. Галлардо // Открытые системы. – М., 2014. – №08. – С. 76. ↑

7. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 168. ↑

8. Гук М. Аппаратные средства IBM PC. Энциклопедия / М. Гук. – СПб.:Питер, 2014. – С. 931. ↑

9. Гук М. Аппаратные средства IBM PC. Энциклопедия / М. Гук. – СПб.:Питер, 2014. – С. 832. ↑

10. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 135. ↑

11. Гук М. Аппаратные средства IBM PC. Энциклопедия / М. Гук. – СПб.:Питер, 2014. – С. 271. ↑

12. Серрано Н. Сервисы, архитектура и унаследованные системы / Н. Серрано, Х. Эрнантес, Г. Галлардо // Открытые системы. – М., 2014. – №08. – С. 78. ↑

13. Максимов Н. В. Архитектура ЭВМ и вычислительные системы / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. – М.: Форум, Инфра-М, 2013. — С. 125. ↑

14. Новожилов О. П. Архитектура ЭВМ и систем / О. П. Новожилов. – М.:Юрайт, 2011 – С. 236. ↑

15. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 157. ↑

16. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 167. ↑

17. Орлов С. А. Организация ЭВМ и систем: Учебник для вузов / С. А. Орлов. – СПб.: Питер, 2014. – С. 226. ↑

18. Максимов Н. В. Архитектура ЭВМ и вычислительные системы / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. – М.: Форум, Инфра-М, 2013. — С. 158. ↑

19. Гук М. Аппаратные средства IBM PC. Энциклопедия / М. Гук. – СПб.:Питер, 2014. – С. 728. ↑

20. Паттерсон Д. Архитектура компьютера и проектирование компьютерных систем / Д. Паттерсон, Д. Хеннеси. – СПб.: Питер, 2012. – С. 272. ↑

21. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 166. ↑

22. Симонович С. Информатика. Базовый курс / С. Симонович. – СПб.: Питер, 2016. – С. 415. ↑

23. Максимов Н. В. Архитектура ЭВМ и вычислительные системы / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. – М.: Форум, Инфра-М, 2013. — С. 256. ↑

24. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 142. ↑

25. Баула В. Г. Архитектура ЭВМ и операционные среды / В. Г. Баула, А. Н. Томилин, Д. Ю. Волканов. – М.:Academia, 2011 – С. 135. ↑

26. Максимов Н. В. Архитектура ЭВМ и вычислительные системы / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. – М.: Форум, Инфра-М, 2013. — С. 235. ↑

27. Таненбаум Э. Архитектура компьютера / Э. Таненбаум, Т. Остин. – СПб.: Питер, 2015. – С. 625. ↑

28. Паттерсон Д. Архитектура компьютера и проектирование компьютерных систем / Д. Паттерсон, Д. Хеннеси. – СПб.: Питер, 2012. – С. 325. ↑

29. Симонович С. Информатика. Базовый курс / С. Симонович. – СПб.: Питер, 2016. – С. 225. ↑

30. Баула В. Г. Архитектура ЭВМ и операционные среды / В. Г. Баула, А. Н. Томилин, Д. Ю. Волканов. – М.:Academia, 2011 – С. 154. ↑

31. Максимов Н. В. Архитектура ЭВМ и вычислительные системы / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. – М.: Форум, Инфра-М, 2013. — С. 145. ↑

32. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 156. ↑

33. Баула В. Г. Архитектура ЭВМ и операционные среды / В. Г. Баула, А. Н. Томилин, Д. Ю. Волканов. – М.:Academia, 2011 – С. 125. ↑

34. Максимов Н. В. Архитектура ЭВМ и вычислительные системы / Н. В. Максимов, Т. Л. Партыка, И. И. Попов. – М.: Форум, Инфра-М, 2013. — С. 124. ↑

35. Горнец Н. Н. ЭВМ и периферийные устройства. Компьютеры и вычислительные системы / Н. Н. Горнец, А. Г. Рощин. – М.:Academia, 2012 – С. 124. ↑