Алгоритмы сортировки данных. Конкретные примеры алгоритмов сортировки

Содержание:

Введение

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

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

Объектом исследования в данной работе являются основные понятия алгоритмов сортировки, предметом исследования – конкретные алгоритмы.

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

Задачами данной работы являются:

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

В основу исследования легли книги по архитектуре персональных компьютеров из серии «Классика Computer Science» всемирно известных авторов, таких как Э. Таненбаум, Д. Паттерсон и Д. Хеннесси.

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

Паттерсон является заслуженным профессором Калифорнийского университета в Беркли, работающим в области микропроцессоров и информатики. Он известен своим вкладом в проектирование RISC-процессоров и создание принципа работы RAID-массивов.

Хеннесси является американским ученым, работающим в области микропроцессоров и информатики. Также он является основателем MIPS Computer Systems Inc. и ректором Стэнфордского университета.

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

1. Основные понятие алгоритмов сортировки

1.1. Понятие алгоритма сортировки

Алгоритм является набором инструкций, которые описывают порядок действий исполнителя с целью достижения определенного результата. В старой трактовке использовалось слово «последовательность» вместо слова «порядок», но при развитии параллельности в компьютерной работе словом «порядок» стало заменяться более конкретное «последовательность». Независимые инструкции могут выполняться в произвольном порядке, в том числе и параллельно, при условии, что это позволяют используемые исполнители^[1].

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

Задача алгоритма сортировки формулируется наличием массива из определенного количества элементов. Каждый из элементов имеет определенно количество параметров, не влияющих на сортировку, и один сортировочный параметр, называемый ключом. На массиве ключей задано отношение порядка, то есть линейного упорядочивания, для которого должны быть выполнены два условия: закон трихотомии, при котором ключ одного элемента может быть только больше, меньше или равен ключу другого элемента; и транзитивность, при которой если ключ одного элемента, больше ключа второго элемента, который в свою очередь больше ключа третьего элемента, то ключ первого элемента должен быть больше ключа третьего элемента^[3].

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

Точно также только для равенства и убывания можно обозначить сортировку по невозрастанию^[4] [2, 5, 6].

1.2. Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по эффективности использования памяти и скорости выполнения.

Время является основным параметром, который характеризует быстродействие алгоритма. Данный параметр также называется вычислительной сложностью. С целью упорядочения важны лучшее, среднее и худшее поведения алгоритма в терминах мощности входного множества. Для типичного алгоритма выделяют хорошее поведение и плохое поведение. Также существует идеальное поведение для упорядочения. Использующие только абстрактную операцию сравнения ключей алгоритмы сортировки всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана, который использует тот факт, что пространство ключей ограничено. Данный алгоритм чрезвычайно сложен, и не применим в повседневной практике. Также существует понятие сортирующих сетей, предполагающие возможность одновременного (например, при параллельном вычислении) проведения несколько сравнений^[5].

Определенные алгоритмы требуют выделения дополнительной памяти под временное хранение данных. Обычно данные алгоритмы требуют определенное количество памяти. При оценке не учитывается место, занимаемое исходным массивом, и независящие от входной последовательности затраты, такие как хранение кода программы. Не потребляющие дополнительной памяти алгоритмы относят к сортировкам на месте^[6] [3, 7].

1.3. Свойства и классификация алгоритмов сортировки

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

Устойчивость показывает насколько устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.

Естественность поведения показывает эффективность метода при обработке частично или полностью упорядоченных данных. Алгоритм ведет себя естественно, в том случае, когда учитывает данную характеристику входной последовательности и работает качественнее^[7].

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

Также важным свойством алгоритма является его сфера применения. По сферам применения существует два основных типов упорядочения^[8].

Внешняя сортировка оперирует запоминающими устройствами большого объема, но с последовательным доступом, а не с произвольным, то есть в конкретный момент виден единственный элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Данная методика накладывает дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, которые обычно используют дополнительное дисковое пространство. Также доступ к данным во внешней памяти производится намного медленнее операций с оперативной памятью. Доступ к носителю осуществляется последовательным образом так, что в каждый момент времени можно записать или считать только один следующий за текущим элемент. Объем данных не позволяет им разместиться в оперативном запоминающем устройстве^[9].

Внутренняя сортировка оперирует массивами, которые целиком помещаются в оперативной памяти с произвольным доступом к любой ячейке. Данные чаще всего упорядочиваются без дополнительных затрат на том же месте. В современных архитектурах персональных компьютеров широко применяется кэширование и подкачка памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами подкачки и кэширования^[10] [2, 3].

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

2. Конкретные примеры алгоритмов сортировки

2.1. Алгоритмы устойчивой сортировки

2.1.1. Сортировка пузырьком

Сортировка простыми обменами, сортировка является простым алгоритмом сортировки. Для понимания и реализации этот алгоритм являетс простейшим, но он эффективен лишь для небольших массивов.

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка^[11].

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на свое место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива. Таким образом, элемент «всплывает» до нужной позиции, как пузырек в воде, отсюда и название алгоритма^[12] [3, 7].

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

Шейкерная сортировка также называется сортировко2 перемешиванием или двунаправленной. Данный вид сортировки является разновидностью пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.

Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения^[13].

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

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

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

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

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

Данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей^[16] [2].

2.1.4. Гномья сортировка

Гномья сортировка является алгоритмом сортировки, похожим на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице книги Дика Груна «Гномья сортировка».

Концептуально алгоритм прост и не требует вложенных циклов. На практике алгоритм может работать так же быстро, как и сортировка вставками^[17].

Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов [4, 6]^[18].

2.1.5. Сортировка слиянием

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

Для решения задачи сортировки эти три этапа выглядят так:

1. Сортируемый массив разбивается на две части примерно одинакового размера;
2. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
3. Два упорядоченных массива половинного размера соединяются в один^[19] [3].

2.1.6. Сортировка с помощью двоичного дерева

Сортировка с помощью двоичного дерева является универсальным алгоритмом сортировки, который заключается в построении двоичного дерева поиска по ключам массива, с последующей сборкой результирующего массива путем обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путем непосредственного чтения с потока (например, из файла, сокета или консоли)^[20] [7].

2.1.7. Сортировка Timsort

Сортировка Timsort представляет собой комбинированный алгоритм из сортировки вставками и сортировки слиянием. Основная идея алгоритма заключается в том, что алгоритму входной массив разделяется на подмассивы, каждый подмассив сортируется сортировкой вставками, после чего отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием^[21] [2].

2.1.8. Сортировка подсчетом

Сортировка подсчетом является алгоритмом сортировки, в котором используется диапазон чисел сортируемого массива для подсчета совпадающих элементов. Применение сортировки подсчетом целесообразно лишь тогда, когда сортируемые числа имеют диапазон возможных значений, достаточно малый по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысл, так как каждый элемент придется просматривать более одного раза^[22] [4].

2.1.9. Блочная сортировка

Блочная сортировка, также называемая корзинной сортировкой, является алгоритмом сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков так, чтобы все элементы в каждом следующем по порядку блоке были всегда меньше или больше, чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения^[23] [9].

2.1.10. Поразрядная сортировка

Поразрядная сортировка, также называемая цифровой сортировкой является алгоритмом сортировки за линейное время. Числа сортируются по разрядам. Существует два варианта: least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк^[24] [2].

2.2. Алгоритмы неустойчивой сортировки

2.2.1. Сортировка выбором

Сортировка выбором может быть как устойчивой, так и неустойчивой.

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

Для реализации устойчивости алгоритма необходимо при обмене значений минимальный элемент непосредственно вставлять в первую неотсортированную позицию, не меняя порядок остальных элементов^[25] [1].

2.2.2. Сортировка Шелла и сортировка расческой

Сортировка Шелла представляет собой алгоритм сортировки, который является усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, которые стоят не только рядом, но и на определенном расстоянии друг от друга. Другими словами, данный вид сортировки представляет собой сортировку вставками, но с предварительными «грубыми» проходами^[26].

Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расческой». Сортировка расческой является довольно упрощенным алгоритмом сортировки, который был изначально спроектирован Влодзимежом Добосевичем в 1980 году. Позднее он был переоткрыт и популяризован в статье Ричарда Бокса и Стивена Лэйси в журнале Byte Magazine в апреле 1991 года. Сортировка расческой улучшает сортировку пузырьком, и конкурирует с подобными быстрой сортировке алгоритмами. Основная идея алгоритма заключается устранении черепах, или маленьких значений в конце списка, которые крайне замедляют сортировку пузырьком. Кролики противопоставлены черепахам, являясь большими значениями в начале списка, не представляющими проблемы для сортировки пузырьком^[27].

В сортировке пузырьком, когда сравниваются два элемента, промежуток между ними равен 1. Основная идея сортировки расческой в том, что этот промежуток может быть гораздо больше, чем единица. Сортировка Шелла также основана на этой идее^[28] [4, 7, 10].

2.2.3. Пирамидальная сортировка

Пирамидальная сортировка может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает или тонет по многим путям. Сортировка пирамидой использует бинарное сортирующее дерево. Алгоритм сортировки будет состоять из двух основных шагов: элементы массива выстраиваются в виде сортирующего дерева, после чего удаляются элементы из корня по одному за раз и дерево перестраивается^[29] [8].

2.2.4. Плавная сортировка

Плавная сортировка является алгоритмом сортировки выбором, разновидностью пирамидальной сортировки, которая была разработана Э. Дейкстрой в 1981 году. Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо. Куча состоит из последовательности куч, размеры которых равны одному из чисел Леонардо, а корни хранятся в порядке возрастания^[30] [1].

2.2.5. Быстрая сортировка

Быстрая сортировка, также называемая сортировкой Хоара, является широко известным алгоритмом сортировки, который был разработан английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Быстрая сортировка является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена и его вариантов пузырьковой сортировки и шейкерной сортирови, известных, помимо прочего, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов^[31] [4].

2.2.6. Сортировка Introsort

Introsort или интроспективная сортировка является алгоритм сортировки, который был предложен Дэвидом Мюссером в 1997 году. Он использует быструю сортировку и переключается на пирамидальную сортировку, когда глубина рекурсии превысит некоторый заранее установленный уровень (например, логарифм от числа сортируемых элементов). Так как оба алгоритма используют сравнения, этот алгоритм также принадлежит классу сортировок на основе сравнений^[32] [2].

2.3. Прочие алгоритмы сортировки

Bogosort, также называемая случайной сортировкой, сортировкой ружья или обезьяньей сортировкой является очень неэффективным алгоритмом сортировки. Ее используют только в образовательных целях, противопоставляя другим, более реалистичным алгоритмам. Если bogosort использовать для сортировки колоды карт, то сначала в алгоритме нужно проверить, лежат ли все карты по порядку, и если не лежат, то случайным образом перемешать ее, проверить лежат ли теперь все карты по порядку, и повторять процесс, пока не отсортируется колода^[33].

Блинная сортировка является алгоритмом сортировки, с единственной допустимой операцией — переворотом элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить в виде стопки блинов, которую тасуют путем взятия нескольких блинов сверху и их переворачивания^[34].

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

Внешняя сортировка является сортировкой данных, которые расположены на периферийных устройствах и не вмещаются в оперативную память, то есть когда применить одну из внутренних сортировок невозможно. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам и другим подобным устройствам^[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. ↑