Сортировка методом пузырька реферат

Обновлено: 02.07.2024

Изучение алгоритмов и разновидности методов сортировки в программировании. Характеристика ее видов: сортировка пузырьком, перемешиванием, методом вставок, подсчётом, слиянием, цифровая, поразрядная, методом выбора, методом Шелла, пирамидальная и быстрая.

Рубрика Программирование, компьютеры и кибернетика
Вид реферат
Язык русский
Дата добавления 20.11.2014
Размер файла 32,1 K

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

Федеральное агентство железнодорожного транспорта

Алгоритмы сортировки. Сортировка вставками

1. Алгоритмы сортировки

2. Разновидности методов сортировки

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

2.2 Сортировка перемешиванием

2.3 Сортировка методом вставок

2.4 Сортировка подсчётом

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

2.6 Цифровая сортировка

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

2.8 Сортировка методом выбора

2.9 Сортировка методом Шелла

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

2.11 Быстрая сортировка

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

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

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

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

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

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

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

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

Алгоритм сортировки выбором более эффективная сортировка обменами за критерием М(n), то есть за количеством пересылок, но также является не очень эффективным. Из этих причин были разработаны некоторые новые алгоритмы сортировки, которые получили название быстрых алгоритмов сортировки. Это такие алгоритмы, как сортировка деревом, пирамидальная сортировка, быстрая сортировка Хоора и метод цифровой сортировки.

1. Алгоритмы сортировки

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

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

Время сортировки -- основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение -- это O(n log n) и плохое поведение -- это Щ(nІ). Идеальное поведение для сортировки -- O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в Щ(n log n) сравнениях в среднем;

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

Устойчивость (stability) -- устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.

Естественность поведения -- эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

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

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим объём данных не позволяет им разместиться в ОЗУ

Список алгоритмов сортировки

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

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

Сортировка пузырьком (англ. Bubble sort ) -- сложность алгоритма: Q(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку

Сортировка перемешиванием (Сортировка коктейлем, Cocktail sort, bidirectional bubble sort) -- Сложность алгоритма: O(n2)

Сортировка методом вставок (Insertion sort) -- Сложность алгоритма: O(n2); определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда

Блочная сортировка (Корзинная сортировка, Bucket sort) -- Сложность алгоритма: O(n); требуется O(k) дополнительной памяти

Сортировка подсчетом (Counting sort) -- Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти

Сортировка слиянием (Merge sort) -- Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти; сортируем первую и вторую половину списка отдельно, а затем -- сливаем отсортированные списки

In-place merge sort -- Сложность алгоритма: O(n2)

Двоичное древо сортировки (Binary tree sort) -- Сложность алгоритма: O(n log n); требуется O(n) дополнительной памяти

Цифровая сортировка (Сортировка по отделениям, Pigeonhole sort) -- Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти

Поразрядная сортировка (Radix sort) -- Сложность алгоритма: O(n·k); требуется O(n) дополнительной памяти сортирует строки буква за буквой

Гномья сортировка (Gnome sort) -- Сложность алгоритма: O(n2)

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

Сортировка методом выбора (Selection sort) -- Сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка

Сортировка методом Шелла (Shell sort) -- Сложность алгоритма: O(n log n); попытка улучшить сортировку вставками

Сортировка расчёской (Comb sort) -- Сложность алгоритма: O(n log n)

Пирамидальная сортировка (Сортировка кучи, Heapsort) -- Сложность алгоритма: O(n log n); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка

Плавная сортировка (Smoothsort) -- Сложность алгоритма: O(n log n)

Быстрая сортировка (Quicksort) -- Сложность алгоритма: O(n log n) -- среднее время, O(n2) -- худший случай; широко известен как быстрейший из известных для сортировки больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине

Introsort -- Сложность алгоритма: O(n log n)

Patience sorting -- Сложность алгоритма: O(n log n + k) -- наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность

Непрактичные алгоритмы сортировки

Сортировка Акульшина (Akulshin sort) -- O(n Ч n!) -- худшее время. Генерируем всевозможные перестановки исходного массива и для каждой осуществдяем проверку верной отсортированности.

Глупая сортировка (Stupid sort) -- O(n3); рекурсивная версия требует дополнительно O(n2) памяти

Bead Sort -- O(n) or O(vn), требуется специализированное железо

Блинная сортировка (Pancake sorting) -- O(n), требуется специализированное железо

2. Разновидности методов сортировки

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

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

Пример реализации алгоритма (язык Pascal):

for i := n - 1 downto 1 do

for j := 1 to i do

if a[j] > a[j+1] then

2.2 Сортировка перемешиванием

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

Лучший случай для этой сортировки -- отсортированный массив (О(n)), худший -- отсортированный в обратном порядке (O(nІ)).

2.3 Сортировка методом вставок

Сортировка методом вставок (англ. insertion sort) -- простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

прост в реализации

эффективен на небольших наборах данных

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

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

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

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

2.4 Сортировка подсчётом

Сортировка подсчётом -- алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

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

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

Двоичное дерево (структура данных)

Двоичное дерево -- абстрактная структура данных, являющееся программной реализацией двоичного дерева (графа). Оно состоит из узлов (записей) вида (data, l, r), где data -- некоторые данные привязанные к узлу, l, r -- ссылки на узлы, являющиеся детьми данного узла. Узел l называется левым ребёнком, а узел r -- правым.

2.6 Цифровая сортировка

Алгоритм цифровой сортировки действует следующим образом:

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

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

Эффективность этого алгоритма сильно зависит от плотности элементов в массиве ячеек. Если элементов этого массива намного больше, чем сортируемых предметов, то шаги 1 и 3 будут относительно медленными.

Сортировку подсчётом применяют редко, потому что её требования редко удовлетворяются, и часто бывает проще применить другие, более гибкие и почти такие же быстрые алгоритмы сортировки. В особенности, блочная сортировка является более практичным вариантом сортировки подсчётом. В некотором роде, быстрая сортировка представляет собой обобщённую сортировку подсчётом (всего с двумя ячейками в каждый момент времени).

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

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

2.8 Сортировка методом выбора

Сортировка методом выбора (англ. selection sort) -- алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае И(n2), предполагая, что сравнения делаются за постоянное время.

находим минимальное значение в текущем списке

производим обмен этого значения со значением на первой позиции

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

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

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

2.9 Сортировка методом Шелла

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

Анализ алгоритма сортировки Шелла

Время выполнения сортировки пропорционально n1.2. Эта зависимость значительно лучше квадратичной зависимости n2, которой подчиняется большинство простых алгоритмов сортировки.

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




Министерство образования и науки Российской Федерации

Федеральное агентство по образованию ГОУ ВПО

Всероссийский заочный финансово-экономический институт

Кафедра Автоматизированной обработки экономической

информации
КУРСОВАЯ РАБОТА

Работа выполнена Глушко

1. Метод пузырька

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

3. Сортировка вставкой

5. Быстрая сортировка (метод Хоара)

6. Сортировка бинарным деревом

7. Сортировка массивом (хероширование)

8. Обменная поразрядная сортировка

Введение.


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

1.Методы сортировки.

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

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

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

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

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

1.1.Метод пузырька.

Идея этого метода отражена в его названии. Самые легкие элементы массива "всплывают" наверх, самые "тяжелые" - тонут. Последовательность из N элементов данных просматривается от начала до конца так, что стоящие рядом элементы меняются местами, если первый из них меньше ("легче") второго. Таким образом, после такого просмотра самый "легкий" элемент "выталкивается" в конце последовательности.

Если теперь повторить такой просмотр еще N – 1 раз, то, очевидно, что вся заданная последовательность окажется от сортированной. Этот алгоритм можно несколько оптимизировать двумя добовлениями:

1) Просматривая на k -м проходе не весь массив, а только элементы с первого до ( N - k +1)-го;

2) Повторяя просмотр не N раз, а лишь до тех пор, пока при очередном просмотре не произойдет ни одной перестановки.

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

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

1.3.Сортировка вставкой.

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

Этот процесс реализован в следующей программе. Для каждого i от 2 до N, под массив a[1..i] сортируется посредством помещения a[i] в подходящую позицию среди уже отсортированных элементов:

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

Виды сортировок вставкой:

· Сортировка простыми вставками

· Сортировка бинарными вставками

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

1.4. Метод Шелла.


Этот метод является модификацией метода пузырька. Такой метод предложен в 1959 г . Дональдом Л. Шеллом. Основная его идея заключается в том, чтобы вначале устранить массовый беспорядок в сортируемой последовательности, сравнивая, далеко отстоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшают до единицы, то есть на первом проходе гарантируется, что все элементы, расстояние между которыми L 1 N – 1, упорядочиваются друг относительно друга, на втором то же гарантируется для элементов, расстояние между которыми L 2 L 1 и так далее до последнего k -ого прохода, когда должно выполняться Lk = 1. Обычно расстояние L для сортировки Шелла берутся из приблизительного соотношения Lk ≤ 2 Lk -1 и L 1 ≤ N /2, но лучше для расстояний L брать простые числа, ближайшие к Lk , выбираемой по описанной выше схеме.

1.5. Быстрая сортировка (метод Хоара).

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

Установим два индекса на 1-ый (индекс ί ) и на последний (индекс ј) элемент последовательности. Затем пока элемент с индексом ј меньше или равен элементу с индексом ί, будем уменьшать ј на 1. Если же элемент с индексом ј больше или равен элементу с индексом ί, то меняем местами элементы с индексами ί и ј. Затем, пока элемент с индексом ј меньше или равен элементу с индексом ί, будем увеличивать ί на 1. Если же элемент с индексом ј больше или равен элементу с индексом ί, то меняем элемент с индексом ί на ј. Этот процесс продолжается до тех пор, пока ј не станет равным ί. Элемент с индексом ί = ј и есть искомый.

1.6. Сортировка бинарным деревом.

Бинарным (двоичным) деревом называют упорядоченную структуру данных, в которой каждому элементу данных поставлены в соответствие до трех других элементов: левый и правый преемник и предшественник. Левый преемник должен быть больше, а правый – меньше или равен предшественнику. Единственный элемент, не имеющий предщественника, называется корнем дерева.

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

Правила обхода дерева:

· Обход начинается с корня, предыдущим элементом считается верхний;

· Если предыдущий элемент – верхний, то если левый преемник существует, то переход к этому элементу, в противном случае вывод текущего элемента данных и если правый приемник существует, то переход к этому элементу, в противном случае переход к предшественнику;

· Если предыдущий элемент – левый, то вывод текущего элемента и если правый приемник существует, то переход к правому преемнику, в противном случае переход к предшественнику;

· Если предыдущий элемент – правый, то переход к предшественнику;

· Обход заканчивается после вывода последнего элемента, по счетчику.

Сортировка бинарным деревом – это нерекрусивная быстрая сортировка. При рекурсивной быстрой сортировке дерево автомотически строится и обходится в сетке.

1.7. Сортировка массивом (хеширование)

Сортировка массивом – это самый быстрый метод сортировки, однако существует множество существенных недостатков.

Суть метода заключается в заполнении вспомогательного массива, содержащего элементы несколько больше, чем исходная последовательность. Заполнение этого вспомогательного массива происходит таким образом: вычисляются значения некоторой монотонной функции, называемой хэш-функция, на элементах сортируемой последовательности и эти значения считаются индексами этих элементов в заполняемом массиве. Если же окажется, что подлежащий заполнению элемент вспомогательного массива уже занят, то происходит сдвиг соответствующих элементов этого массива так, чтобы образовалось “окно” для вносимого элемента и сохранялась упорядоченность между элементами. Функция должна выбираться так, чтобы ее значения лежали внутри диапазона индексов вспомогательного массива. Например, если известно, что сортируемая последовательность состоит из натуральных чисел от 1 до N , то вкачестве искомой функции можно взять , . В общем случае, в качестве такой функции рекомендуется взять

где A – это исходная последовательность (массив), Max ( A ) и Min ( A ) максимальный и минимальный элемент A , B – это вспомогательный массив, а Size ( B ) – это его размер. Эта монотонная (почти линейная) функция гарантирует, что ее значение на элементах сортируемого массива будут лежать в диапазоне от 1 до Size ( B ). Она определена только при Max ( A ) ≠ Min ( A ). Если же Max ( A ) = Min ( B ), то это означает, что массив состоит из одинаковых элементов, то есть он отсортирован.

1.8.Обменная поразрядная сортировка.

Этот метод, совершенно отличен от всех схем сортировки, которые рассматривались прежде; в нем используется двоичное представление ключей, и потому он предназначен исключительно для двоичных машин. Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли 0 или 1 отдельные биты ключа. В других отношениях он обладает характеристиками обменной сортировки и на самом деле очень напоминает быструю сортировку. Так как он зависит от разрядов ключа, представленного в двоичной системе счисления, мы называем его "обменной поразрядной сортировкой". В общих чертах этот алгоритм можно описать следующим образом:

1) Последовательность сортируется по старшему значащему двоичному биту так, чтобы все ключи, начинающиеся с 0, оказались перед всеми ключами, начинающимися с 1. Для этого надо найти самый левый ключ Ki, начинающийся с 1, и самый правый ключ Kj, начинающийся с 0, после чего Ri и Rj меняются местами, и процесс повторяется, пока не станет i > j.

2) Пусть F0—множество элементов, начинающихся с 0, а F1—все остальные. Применим к F0 поразрядную сортировку (начав теперь со второго бита слева, а не со старшего) до тех пор, пока множество F0 не будет полностью отсортировано; затем проделаем то же с F1.

Алгоритм обмена по разрядной сортировки:

Записи R1, . . . , RN переразмещаются на том же месте; после завершения сортировки их ключи будут упорядочены:K1 ≤ . . . ≤ KN. Предполагается, что все ключи—m-разрядные двоичные числа ( a1 a2 . . . am ) 2; i-й по старшинству бит ai называется "бит i" ключа. Требуется вспомогательный стек, вмещающий до m − 1 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями,

Заключение.

Казалось бы, к чему плодить много алгоритмов, давайте найдем один, самый оптимальный и успокоимся на этом. Это ошибочное мнение. Найти оптимальный алгоритм, не привязываясь при его выборе к условию задачи - это иллюзия.

Какой алгоритм, из множества известных сейчас самый быстрый?

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

Читайте также: