Реферат по теме алгоритмы сортировки

Обновлено: 05.07.2024

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

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

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

Таким образом, задачами курсовой работы являются:

- найти определение понятию алгоритма сортировки;

- определить основные параметры оценки алгоритмов сортировки;

- рассмотреть различные методы сортировки данных;

- разработать алгоритм решения экономической задачи, представленной в практической части работы;

- использовать в работе, в целях более наглядного восприятия, шаблоны

выходных документов, показав их расположение на рабочем листе

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

I. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Что представляет собой алгоритм сортировки

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

Алгоритм сортировки — это порядок действий для упорядочения элементов в списке. Обычно говорят о сортировке записей (содержащих любые данные) по ключам – фрагментам этих записей, допускающих отношение упорядочения. Например, ключи могут быть числами (в этом случае используется естественный математический порядок возрастания или убывания чисел) или строковыми значениями (в этом случае упорядочение производится по алфавиту). [4, стр. 195]

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

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

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

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

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

• Естественность поведения — эффективность метода при обработке уже

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

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

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

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

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

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

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

Обменная сортировка

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

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

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

1. Сначала верхняя граница устанавливается равной размеру массива.

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

3. Новая верхняя граница устанавливается равной последней записи, для которой был произведен обмен.

4. Если обменов не было вообще, алгоритм заканчивает работу.

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

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

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

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

1. Начнем формировать новый отсортированный массив.

2. После того как в него помещено iзаписей, размещаем очередную запись (с номером i+1) в то место, где она должна располагаться, чтобы не нарушить порядок последовательности.

3. Когда все записи перенесены в новый массив, данные располагаются в отсортированном порядке.

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

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

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

Наиболее известным методом блочной сортировки является метод Шелла.

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

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

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

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

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

После первого этапа работы алгоритма массив данных преобразуется таким образом, что максимальный элемент (временно) размещается в самой первой записи и для всех элементов верны неравенства: a (j) > a (2*j) и a(j) > a (2*j+1), если соответствующие элементы все еще лежат внутри массива. Пари этом a – элемент массива; j – его порядковый номер. Последующие этапы работы алгоритма приводят к тому, что максимальный в данный момент элемент отправляется на правильное место в отсортированном массиве, а для всех остальных элементов сохраняются такие же неравенства. [5, стр. 214-215]

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

· Каждый лист имеет определенную глубину;

· Значение в любой вершине больше, чем значения ее потомков.

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

Линейная сортировка (сортировка отбором)

Идея линейной сортировки по невозрастанию заключается в том, что

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

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

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

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

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

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

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

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

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

( метод назван также обменной сортировкой с выбором) .

Нужна помощь в написании реферата?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

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

На этот раз при просмотре мaccива мы будем искать наименьший элемент, Сравнивая его с первым. Если такой элемент найден, поменяем его местами с первым. Затем повторим эту операцию, но начнем не с первого элемента, а со второго. И будем продолжать подобным образом, пока не рассортируем весь массив.

Метод Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

Метод Хoopа

Этот метод, называемый также быстрой сортировкой(QuickSort), был Разработан в 1962 г. (его разработал Charles Antony Richard Hoare).

Нужна помощь в написании реферата?

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

Содержание

ВВЕДЕНИЕ 3
Глава 1 АЛГОРИТМЫ СОРТИРОВКИ 5
1.1 ОБЩАЯ ХАРАКТЕРИСТИКА АЛГОРИТМОВ СОРТИРОВКИ 5
1.2 ОСНОВНЫЕ ВИДЫ СОРТИРОВОК 7
1.2.1 Сортировка пузырьком 7
1.2.2 Сортировка перемешиванием 7
1.2.3 Сортировка методом вставок 7
1.2.4 Сортировка подсчетом 8
1.2.5 Сортировка слиянием 8
1.2.6 Сортировка методом выбора 9
1.2.7 Сортировка методом Шелла 9
1.2.8 Метод Хoopа 10
1.2.9 Цифровая сортировка 10
1.2.10 Поразрядная сортировка 11
1.2.11 Быстрая сортировка 11
Глава 2 ПРАКТИЧЕСКАЯ ЧАСТЬ 13
2.1 Общая характеристика задачи 13
2.2 Алгоритм решения задачи 14
ЗАКЛЮЧЕНИЕ 19
СПИСОК ЛИТЕРАТУРЫ 21

Работа состоит из 1 файл

курсовик информатика.doc

Федеральное агентство по образованию

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

Кафедра прикладной информатики

Факультет менеджмент и маркетинг

Специальность менеджмент организации

Студент: Коновалова Надежда Васильевна

Курс 2 № группы 202

Личное дело № 08ММБ00284

Преподаватель: Савин Дмитрий Александрович

Глава 1 АЛГОРИТМЫ СОРТИРОВКИ

1.1 ОБЩАЯ ХАРАКТЕРИСТИКА АЛГОРИТМОВ СОРТИРОВКИ

1.2 ОСНОВНЫЕ ВИДЫ СОРТИРОВОК

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

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

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

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

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

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

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

1.2.8 Метод Хoopа

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

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

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

Глава 2 ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Общая характеристика задачи

2.2 Алгоритм решения задачи

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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 ₁ N – 1, упорядочиваются друг относительно друга, на втором то же гарантируется для элементов, расстояние между которыми L ₂ L ₁ и так далее до последнего k -ого прохода, когда должно выполняться L_k = 1. Обычно расстояние L для сортировки Шелла берутся из приблизительного соотношения L_k ≤ 2 L_k _-1 и L ₁ ≤ N /2, но лучше для расстояний L брать простые числа, ближайшие к L_k , выбираемой по описанной выше схеме.

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 элементов. Этот алгоритм, по существу, следует процедуре обменной поразрядной сортировки с разделениями,

Заключение.

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

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

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

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