Алгоpитм соpтиpовки шелла


Улучшенные алгоритмы сортировки

Все алгоритмы, рассмотренные в предыдущих разделах, имеют один фатальный недостаток — время их выполнения имеет порядок n 2 . Это делает сортировку больших объемов данных очень медленной. По существу, в какой-то момент эти алгоритмы становятся слишком медленными, чтобы их применять [1] . К сожалению, страшные истории о «сортировках, которые продолжались три дня», зачастую реальны. Когда сортировка занимает слишком много времени, причиной этому обычно является неэффективность использованного в ней алгоритма. Тем не менее, первой реакцией в такой ситуации часто становится оптимизация кода вручную, возможно, путем переписывания его на ассемблере. Несмотря на то, что ручная оптимизация иногда ускоряет процедуру на постоянный множитель [2] , если алгоритм сортировки не эффективен, сортировка всегда будет медленной независимо от того, насколько оптимально написан код. Следует помнить, если время работы процедуры пропорционально n 2 , то увеличение скорости кода или компьютера даст лишь небольшое улучшение [3] , поскольку время выполнения увеличивается как n 2 . (На самом деле, кривая n 2 на рис. 21.1 (пузырьковая сортировка) растянута вправо, но в остальном соответствует действительности.) Существует правило: если используемый в программе алгоритм слишком медленный сам по себе, никакой объем ручной оптимизации не сделает программу достаточно быстрой. Решение заключается в применении лучшего алгоритма сортировки.

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

Сортировка Шелла

Сортировка Шелла называется так по имени своего автора, Дональда Л. Шелла (Donald Lewis Shell) [4] . Однако это название закрепилось, вероятно, также потому, что действие этого метода часто иллюстрируется рядами морских раковин, перекрывающих друг друга (по-английски «shell» — «раковина»). Общая идея заимствована из сортировки вставками и основывается на уменьшении шагов [5] . Рассмотрим диаграмму на рис. 21.2. Сначала сортируются все элементы, отстоящие друг от друга на три позиции. Затем сортируются элементы, расположенные на расстоянии двух позиций. Наконец, сортируются все соседние элементы.

Рис. 21.2. Сортировка Шелла

То, что этот метод дает хорошие результаты, или даже то, что он вообще сортирует массив, увидеть не так просто. Тем не менее, это верно. Каждый проход сортировки распространяется на относительно небольшое количество элементов либо на элементы, расположенные уже в относительном порядке. Поэтому сортировка Шелла эффективна, а каждый проход повышает упорядоченность [6] .

Конкретная последовательность шагов может быть и другой. Единственное правило состоит в том, чтобы последний шаг был равен 1. Например, такая последовательность:

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

Вы могли заметить, что внутренний цикл for имеет два условия проверки. Очевидно, что сравнение x необходимо для процесса сортировки. Выражение j>=0 предотвращает выход за границу массива items . Эти дополнительные проверки в некоторой степени понижают производительность сортировки Шелла.

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

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

при сортировке n элементов [8] . А это уже существенное улучшение по сравнению с сортировками порядка n 2 . Чтобы понять, насколько оно велико, обратитесь к рис. 21.3, на котором показаны графики функций n 2 и n 1,2 . Тем не менее, не стоит чрезмерно восхищаться сортировкой Шелла — быстрая сортировка еще лучше.

Рис. 21.3. Попытка наглядного представления кривых n 2 и n 1,2 . Хотя вычертить эти кривые с точным соблюдением масштаба на каком-нибудь значимом для целей сортировки интервале изменения количества записей (n), например, на интервале от 0 до 1000, не представляется возможным, получить представление о поведении этих кривых можно с помощью графиков функций у=(n/100) 2 и у=(n/100) 1,2 . Для сравнения построен также график прямой у=n/100. Кроме того, чтобы получить представление о росте этих кривых, можно на оси ординат принять логарифмический масштаб, — это все равно, что начертить логарифмы этих функций

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

Быстрая сортировка, придуманная Ч. А. Р. Хоаром [9] (Charles Antony Richard Hoare) и названная его именем, является самым лучшим методом сортировки из представленных в данной книге и обычно считается лучшим из существующих в настоящее время алгоритмом сортировки общего назначения. В ее основе лежит сортировка обменами — удивительный факт, учитывая ужасную производительность пузырьковой сортировки!

Быстрая сортировка построена на идее деления. Общая процедура заключается в том, чтобы выбрать некоторое значение, называемое компарандом (comparand) [10] , а затем разбить массив на две части. Все элементы, большие или равные компаранду, перемещаются на одну сторону, а меньшие — на другую. Потом этот процесс повторяется для каждой части до тех пор, пока массив не будет отсортирован. Например, если исходный массив состоит из символов fedacb , а в качестве компаранда используется символ d , первый проход быстрой сортировки переупорядочит массив следующим образом:

Затем сортировка повторяется для обеих половин массива, то есть bса и def . Как вы видите, этот процесс по своей сути рекурсивный, и, действительно, в чистом виде быстрая сортировка реализуется как рекурсивная функция [11] .

Значение компаранда можно выбирать двумя способами — случайным образом либо усреднив небольшое количество значений из массива. Для оптимальной сортировки необходимо выбирать значение, которое расположено точно в середине диапазона всех значений. Однако для большинства наборов данных это сделать непросто. В худшем случае выбранное значение оказывается одним из крайних. Тем не менее, даже в этом случае быстрая сортировка работает правильно. В приведенной ниже версии быстрой сортировки в качестве компаранда выбирается средний элемент массива.

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

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

а среднее количество обменов примерно равно

Эти величины намного меньше соответствующих характеристик рассмотренных ранее алгоритмов сортировки.

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

[1] Конечно, это не означает, что функция f(n)=n 2 в какой-то точке возрастает скачкообразно. Вовсе нет! Просто при увеличении размера массива n меняется характер сортировки, из внутренней она фактически становится внешней , когда массив не помещается в оперативной памяти и начинается интенсивная подкачка страниц, а за ней пробуксовывание механизма виртуальной памяти. Вот эти-то события действительно могут наступить внезапно, и тогда может показаться, что незначительное увеличение сортируемого массива или просто добавление какой-либо совершенно незначительной задачи приведет к катастрофическому увеличению времени сортировки (например в десятки раз!).

[2] Отдельные программисты — «любители рассказов о рыбной ловле» — клянутся об увеличении эффективности сначала наполовину, затем вдвое-втрое, к середине рассказа — на порядок, а к концу рассказа — на несколько порядков. (Такое не получается даже в специально подобранных примерах для рекламного проспекта по языку Ассемблера.) На самом деле производительность может даже упасть. В лучшем случае удается повысить ее на 10-12% для реально значимых производственных задач. При этом чем сложнее алгоритм, тем сложнее переписать его на Ассемблере и тем проще сделать в нем ошибку при переписывании, а тем более сложнее ее найти. Кроме того, следует учитывать и такой фактор: например, программу писал какой-то квалифицированный программист, который выбрал простой (но не очень эффективный — при чем об этом он знал) алгоритм потому, что менеджеры настаивали на скорейшем завершении программы, а оптимизацию этой программы те же менеджеры поручат весьма не самым квалифицированным специалистам! Эффект действительно будет на несколько порядков больше, но в совершенно противоположную сторону! Ведь с таким же успехом для «улучшения» трагедий Шекспира за пишущие машинки можно было усадить стадо обезьян!

[3] Действительно, чтобы увеличить в m раз размер сортируемого массива при сохранении времени сортировки, быстродействие процессора придется увеличить в m 2 раз при условии, что время доступа к элементам массива не увеличится, т.е. не уменьшится, например, эффективность подкачки страниц.

[4] Считается, что Дональд Л. Шелл описал свой метод сортировки 28 июля 1959 года. Данный метод классифицируется как слияние с обменом ; часто называется также сортировкой с убывающим шагом .

[5] Шаг — расстояние между сортируемыми элементами на конкретном этапе сортировки.

[6] Т.е. уменьшает количество беспорядков (инверсий).

[8] Вообще говоря, время сортировки Шелла зависит от последовательности шагов. (Впрочем, минимум равен, конечно, n log 2 n .) Оптимальная последовательность не известна до сих пор. Дональд Кнут исследовал различные последовательности (не забыв и последовательность Фибоначчи). Фактически он пришел к выводу, что в определении наилучшей последовательности есть какое-то «колдовство». В 1969 г. Воган Пратт обнаружил, что если все шаги выбираются из множества чисел вида 2 p 3 q , меньших n, то время работы будет порядка n(log n) 2 . А.А. Папернов и Г.В. Стасевич в 1965 г. доказали, что максимальное время сортировки Шелла не превосходит О(n 1,5 ), причем уменьшить показатель 1,5 нельзя. Большое число экспериментов с сортировкой Шелла провели Джеймс Петерсон и Дэвид Л. Рассел в Стэнфордском университете в 1971 г. Они пытались определить среднее число перемещений при 100≤ n ≤250`000 для последовательно сти шагов 2 k -1. Наиболее подходящими формулами оказались 1,21 n 1,26 и ,39 n (ln n )-2,33 n ln n . Но при изменении диапазона n оказалось, что коэффициенты в представлении степенной функцией практически не изменяются, а коэффициенты в логарифмическом представлении изменяются довольно резко. Поэтому естественно предположить, что именно степенная функция описывает истинное асимптотическое поведение сортировки Шелла.

Илон Маск рекомендует:  Php и com

[9] Встречается также написание Ч. Э. Р. Хоор.


[10] Компаранд — операнд в операции сравнения. Иногда называется также основой и критерием разбиения .

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

Визуализации алгоритмов сортировки

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

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

Сортировка вставками (Insertion sort)

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

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

Временная сложность алгоритма — O(n 2 )

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

Сортировка пузырьком (Bubble sort)

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

В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как сортировка перемешиванием, пирамидальная сортировка и быстрая сортировка.

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

Сортировка выбором (Selection sort)

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

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

Сортировка Шелла (Shell Sort)

Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами.

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

  • отсутствие потребности в памяти под стек;
  • отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

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

Сортировка слиянием (Merge sort)

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

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

Быстрая сортировка (Quick Sort)

Этот широко известный алгоритм сортировки был разработан английским информатиком Чарльзом Хоаром во время его работы в МГУ в советские годы.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n-элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Быстрая сортировка относится к алгоритмам «разделяй и властвуй».

Алгоритм состоит из трёх шагов:

  1. Выбор опорного элемента из массива.
  2. Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные — после.
  3. Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.


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

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

Heapsort — алгоритм, в основе которого лежит сравнение.

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

Пирамидальная сортировка является одним из методов, быстродействие которых оценивается как O(n log n).

С исходным кодом алгоритма и его интерактивной презентацией вы можете ознакомиться в исходной статье.

Сортировка Шелла

Описание

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

  • отсутствие потребности в памяти под стек;
  • отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

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

Остановиться нужно на значении inc[i-1], если 3*inc[i] > размер массива.

Оценка сложности

Лучшая Средняя Худшая
n n (log n)² или n^(3/2) n (log n)²

Лучший случай

Массив уже отсортирован в правильном порядке. Количество сравнений в таком случае наименьшее

Сортировка Шелла

Связанные понятия

Этот относительно простой алгоритм сортировки, разработанный для использования на параллельных процессорах, является модификацией пузырьковой сортировки. Суть модификации в том, чтобы сравнивать элементы массива под чётными и нечётными индексами с последующими элементами независимо. Алгоритм был впервые представлен Н. Хаберманом (N. Haberman) в 1972 году.

В математическом анализе и информатике кривая Мортона, Z-последовательность,Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры.

Схе́ма — графическое представление определения, анализа или метода решения задачи, в котором используются символы для отображения данных, потока, оборудования и т. д.Блок-схема — распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности. Правила выполнения регламентируются ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем.

В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того.

Улучшенные алгоритмы сортировки

Все алгоритмы, рассмотренные в предыдущих разделах, имеют один фатальный недостаток — время их выполнения имеет порядок n 2 . Это делает сортировку больших объемов данных очень медленной. По существу, в какой-то момент эти алгоритмы становятся слишком медленными, чтобы их применять [1] . К сожалению, страшные истории о «сортировках, которые продолжались три дня», зачастую реальны. Когда сортировка занимает слишком много времени, причиной этому обычно является неэффективность использованного в ней алгоритма. Тем не менее, первой реакцией в такой ситуации часто становится оптимизация кода вручную, возможно, путем переписывания его на ассемблере. Несмотря на то, что ручная оптимизация иногда ускоряет процедуру на постоянный множитель [2] , если алгоритм сортировки не эффективен, сортировка всегда будет медленной независимо от того, насколько оптимально написан код. Следует помнить, если время работы процедуры пропорционально n 2 , то увеличение скорости кода или компьютера даст лишь небольшое улучшение [3] , поскольку время выполнения увеличивается как n 2 . (На самом деле, кривая n 2 на рис. 21.1 (пузырьковая сортировка) растянута вправо, но в остальном соответствует действительности.) Существует правило: если используемый в программе алгоритм слишком медленный сам по себе, никакой объем ручной оптимизации не сделает программу достаточно быстрой. Решение заключается в применении лучшего алгоритма сортировки.

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

Сортировка Шелла

Сортировка Шелла называется так по имени своего автора, Дональда Л. Шелла (Donald Lewis Shell) [4] . Однако это название закрепилось, вероятно, также потому, что действие этого метода часто иллюстрируется рядами морских раковин, перекрывающих друг друга (по-английски «shell» — «раковина»). Общая идея заимствована из сортировки вставками и основывается на уменьшении шагов [5] . Рассмотрим диаграмму на рис. 21.2. Сначала сортируются все элементы, отстоящие друг от друга на три позиции. Затем сортируются элементы, расположенные на расстоянии двух позиций. Наконец, сортируются все соседние элементы.

Рис. 21.2. Сортировка Шелла

То, что этот метод дает хорошие результаты, или даже то, что он вообще сортирует массив, увидеть не так просто. Тем не менее, это верно. Каждый проход сортировки распространяется на относительно небольшое количество элементов либо на элементы, расположенные уже в относительном порядке. Поэтому сортировка Шелла эффективна, а каждый проход повышает упорядоченность [6] .

Конкретная последовательность шагов может быть и другой. Единственное правило состоит в том, чтобы последний шаг был равен 1. Например, такая последовательность:


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

Илон Маск рекомендует:  Создание изображения

Вы могли заметить, что внутренний цикл for имеет два условия проверки. Очевидно, что сравнение x необходимо для процесса сортировки. Выражение j>=0 предотвращает выход за границу массива items . Эти дополнительные проверки в некоторой степени понижают производительность сортировки Шелла.

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

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

при сортировке n элементов [8] . А это уже существенное улучшение по сравнению с сортировками порядка n 2 . Чтобы понять, насколько оно велико, обратитесь к рис. 21.3, на котором показаны графики функций n 2 и n 1,2 . Тем не менее, не стоит чрезмерно восхищаться сортировкой Шелла — быстрая сортировка еще лучше.

Рис. 21.3. Попытка наглядного представления кривых n 2 и n 1,2 . Хотя вычертить эти кривые с точным соблюдением масштаба на каком-нибудь значимом для целей сортировки интервале изменения количества записей (n), например, на интервале от 0 до 1000, не представляется возможным, получить представление о поведении этих кривых можно с помощью графиков функций у=(n/100) 2 и у=(n/100) 1,2 . Для сравнения построен также график прямой у=n/100. Кроме того, чтобы получить представление о росте этих кривых, можно на оси ординат принять логарифмический масштаб, — это все равно, что начертить логарифмы этих функций

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

Быстрая сортировка, придуманная Ч. А. Р. Хоаром [9] (Charles Antony Richard Hoare) и названная его именем, является самым лучшим методом сортировки из представленных в данной книге и обычно считается лучшим из существующих в настоящее время алгоритмом сортировки общего назначения. В ее основе лежит сортировка обменами — удивительный факт, учитывая ужасную производительность пузырьковой сортировки!

Быстрая сортировка построена на идее деления. Общая процедура заключается в том, чтобы выбрать некоторое значение, называемое компарандом (comparand) [10] , а затем разбить массив на две части. Все элементы, большие или равные компаранду, перемещаются на одну сторону, а меньшие — на другую. Потом этот процесс повторяется для каждой части до тех пор, пока массив не будет отсортирован. Например, если исходный массив состоит из символов fedacb , а в качестве компаранда используется символ d , первый проход быстрой сортировки переупорядочит массив следующим образом:

Затем сортировка повторяется для обеих половин массива, то есть bса и def . Как вы видите, этот процесс по своей сути рекурсивный, и, действительно, в чистом виде быстрая сортировка реализуется как рекурсивная функция [11] .

Значение компаранда можно выбирать двумя способами — случайным образом либо усреднив небольшое количество значений из массива. Для оптимальной сортировки необходимо выбирать значение, которое расположено точно в середине диапазона всех значений. Однако для большинства наборов данных это сделать непросто. В худшем случае выбранное значение оказывается одним из крайних. Тем не менее, даже в этом случае быстрая сортировка работает правильно. В приведенной ниже версии быстрой сортировки в качестве компаранда выбирается средний элемент массива.

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

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

а среднее количество обменов примерно равно

Эти величины намного меньше соответствующих характеристик рассмотренных ранее алгоритмов сортировки.

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

[1] Конечно, это не означает, что функция f(n)=n 2 в какой-то точке возрастает скачкообразно. Вовсе нет! Просто при увеличении размера массива n меняется характер сортировки, из внутренней она фактически становится внешней , когда массив не помещается в оперативной памяти и начинается интенсивная подкачка страниц, а за ней пробуксовывание механизма виртуальной памяти. Вот эти-то события действительно могут наступить внезапно, и тогда может показаться, что незначительное увеличение сортируемого массива или просто добавление какой-либо совершенно незначительной задачи приведет к катастрофическому увеличению времени сортировки (например в десятки раз!).
[2] Отдельные программисты — «любители рассказов о рыбной ловле» — клянутся об увеличении эффективности сначала наполовину, затем вдвое-втрое, к середине рассказа — на порядок, а к концу рассказа — на несколько порядков. (Такое не получается даже в специально подобранных примерах для рекламного проспекта по языку Ассемблера.) На самом деле производительность может даже упасть. В лучшем случае удается повысить ее на 10-12% для реально значимых производственных задач. При этом чем сложнее алгоритм, тем сложнее переписать его на Ассемблере и тем проще сделать в нем ошибку при переписывании, а тем более сложнее ее найти. Кроме того, следует учитывать и такой фактор: например, программу писал какой-то квалифицированный программист, который выбрал простой (но не очень эффективный — при чем об этом он знал) алгоритм потому, что менеджеры настаивали на скорейшем завершении программы, а оптимизацию этой программы те же менеджеры поручат весьма не самым квалифицированным специалистам! Эффект действительно будет на несколько порядков больше, но в совершенно противоположную сторону! Ведь с таким же успехом для «улучшения» трагедий Шекспира за пишущие машинки можно было усадить стадо обезьян!
[3] Действительно, чтобы увеличить в m раз размер сортируемого массива при сохранении времени сортировки, быстродействие процессора придется увеличить в m 2 раз при условии, что время доступа к элементам массива не увеличится, т.е. не уменьшится, например, эффективность подкачки страниц.
[4] Считается, что Дональд Л. Шелл описал свой метод сортировки 28 июля 1959 года. Данный метод классифицируется как слияние с обменом ; часто называется также сортировкой с убывающим шагом .
[5] Шаг — расстояние между сортируемыми элементами на конкретном этапе сортировки.
[6] Т.е. уменьшает количество беспорядков (инверсий).
[7] -∞ и +∞.
[8] Вообще говоря, время сортировки Шелла зависит от последовательности шагов. (Впрочем, минимум равен, конечно, n log 2 n .) Оптимальная последовательность не известна до сих пор. Дональд Кнут исследовал различные последовательности (не забыв и последовательность Фибоначчи). Фактически он пришел к выводу, что в определении наилучшей последовательности есть какое-то «колдовство». В 1969 г. Воган Пратт обнаружил, что если все шаги выбираются из множества чисел вида 2 p 3 q , меньших n, то время работы будет порядка n(log n) 2 . А.А. Папернов и Г.В. Стасевич в 1965 г. доказали, что максимальное время сортировки Шелла не превосходит О(n 1,5 ), причем уменьшить показатель 1,5 нельзя. Большое число экспериментов с сортировкой Шелла провели Джеймс Петерсон и Дэвид Л. Рассел в Стэнфордском университете в 1971 г. Они пытались определить среднее число перемещений при 100≤ n ≤250`000 для последовательно сти шагов 2 k -1. Наиболее подходящими формулами оказались 1,21 n 1,26 и ,39 n (ln n )-2,33 n ln n . Но при изменении диапазона n оказалось, что коэффициенты в представлении степенной функцией практически не изменяются, а коэффициенты в логарифмическом представлении изменяются довольно резко. Поэтому естественно предположить, что именно степенная функция описывает истинное асимптотическое поведение сортировки Шелла.
[9] Встречается также написание Ч. Э. Р. Хоор.
[10] Компаранд — операнд в операции сравнения. Иногда называется также основой и критерием разбиения .
[11] Если хотите избежать рекурсии, не волнуйтесь, все очень легко переписывается даже для Фортрана IV, в упомянутой ранее литературе вы без труда найдете нужный нерекурсивный вариант.

Алгоpитм соpтиpовки шелла

Wikimedia Foundation . 2010 .

Смотреть что такое «Сортировка Шелла» в других словарях:

Сортировка расчёской — (англ. comb sort) это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1980 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine … Википедия

Сортировка слиянием — Действие алгоритма на примере сортировки случайных точек. Сортировка слиянием (англ. merge sort) алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только п … Википедия

Сортировка выбором — (Selection sort) алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… … Википедия

Сортировка вставками — Сортировка вставками простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: эффективен на небольших наборах данных, на наборах данных до … Википедия

Сортировка пузырьком — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) простой алгоритм сортировки. Для понимания и реализации этот алгоритм простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).… … Википедия

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

Сортировка перемешиванием — (Шейкерная сортировка) (англ. Cocktail sort) разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во первых, если при движении по части массива перестановки не происходят, то эта… … Википедия

Сортировка с помощью двоичного дерева — Пример двоичного дерева Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ.&#1 … Википедия

Пирамидальная сортировка — Анимированная схема алгоритма Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) … Википедия

Сортировка Шелла.

Данный метод разработан американским ученым в области информатики Дональдом Шеллом. Метод сортировки Shellsort был назван в честь него. Сортировка Шелла базируется на методе сортировки вставками. При неудачном наборе данных может выйти так, что несколько наименьших элементов массива окажутся последними, тогда как массив уже почти полностью отсортирован. В этом случае нам придется сравнивать их почти со всеми элементами массива. Конечно, такого хотелось бы избежать. В методе Шелла выполняется сравнение нескольких элементов, находящихся на заданном расстоянии друг от друга. Сначала этих элементов для сравнения несколько. Затем величина этого интервала постепенно сокращается, увеличивается количество элементов для сравнения, но и элементы массива уже оказываются почти упорядочены. На последнем этапе можно выполнить обычную сортировку вставкой, которая очень эффективна на почти отсортированных данных.

Илон Маск рекомендует:  Iis об административных сценариях

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


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

h = 3*h + 1, где

h — величина интервала.

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

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

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

Shell Sort — это тот же самый Insertion Sort, но перед сортировкой с помощью Insertion Sort, мы проводим “грубый” проход. Грубый проход — это сравнение элементов, которые находяться на расстоянии D. После этого сравниваются элементы которые находятся на меньшем расстоянии, и так, пока D=1, что является заключительной проверкой, после которой мы имеем отсортированный массив. Как помните из статьи об Insertion Sort сортировка проходит практически мгновенно, в случае если массив частично отсортирован.

Итак, в чем же неопределнность? Неопределенность, именно в этом самом выборе расстояния D между двумя числами.

Есть огромное количество методов выбора числа D:

  1. Самый просто пример это D = n / 2, D2 = D /2 … Dn =1 . В худшем случае сложность алогритма O(n) = N ^ 2
  2. Предложение Хиббарда: проверить на всем N ^i — 1

Внимательные читатель заметит, что для того чтоб показать хоть какие-то цифры, добавилась еще одна строчка, с 1000000 ( 1 миллион ) элементами.

Потому, если кто-то вас спросит какая разница, или алгоритм работает со O(n) = n ^ 2 или O(n) = N^ (3/2) ( вряд ли именно такое число спросят ☺ )просто покажите эти две картинки. Картинка обычного Insertion Sort так, чисто для памяти прилагается:

Сортировка Шелла :: Shell sort

Сортировка Шелла — это модифицированная сортировка простыми вставками.

Алгоритм

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

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

Как известно, вставочный метод очень эффективно обрабатывает почти отсортированные массивы. Сортировка Шелла при первоначальных проходах достаточно быстро и доводит массив к состоянию неполной упорядоченности. На заключительном этапе шаг равен единице, т.е. «Шелл» естественным образом трансформируется в сортировку простыми вставками.

Сложность по времени

Известно, что при удачном раскладе этот способ сортирует за O(n). Но, в целом, сортировка работает существенно медленнее чем, к примеру быстрая сортировка или сортировка слиянием. Средняя временная сложность зависит от того, какую последовательность брать для циклических итераций.Первоначально автор сортировки, Дональд Шелл, предложил ряд[n/4], [n/2], [n/8], . который давал скорость O(n 2 ).

В течении последующих 50 лет, многие исследователи (среди которых — легендарный Роберт Седжвик) подбирали различные зависимости, постепенно улучшая результат. На данный момент таковым является ряд, предложенный в 2001 году Марсином Сиурой:701, 301, 132, 57, 23, 10, 4, 1.

Улучшенные методы сортировки (шелла, сортдеревом).

Метод Шелла.В 1959 году Д.Шелл предложил алгоритм, который можно рассматривать

как усовершенствование сортировки простыми включениями. Как уже упоминалось,

алгоритм с простыми включениями достаточно эффективно работает на частично

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

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

расстояние между элементами, то можно улучшить сложностные показатели метода

простых вставок. В варианте Шелла на i -м шаге алгоритма текущая последовательность

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

последовательности на расстоянии hi , с последующей сортировкой элементов в каждом


множестве. Числа hi убывают от шага к шагу в определенном порядке (например, может

быть 2^t , 2^t -1 ,…,2,1), на последнем шаге сортируется вся последовательность (другое

название алгоритма Шелла — сортировка включением с уменьшающимся расстоянием),

однако эта операция производится на достаточно хорошо к этому моменту упорядоченной

последовательности. Каждый проход алгоритма использует результаты предыдущих

проходов. Основная идея состоит в перемешивании достаточно далеко расположенных

друг от друга элементов с последующим уменьшением этого расстояния.

Проиллюстрируем метод Шелла для нашего примера с шагами h1=6 h2=3, h3=2, h4=1

Фактически метод Шелла на каждом шаге разбивает последовательность на

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

подпоследовательностей трактуется как единая последовательность, и процесс

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

достаточно сложна, она существенно зависит от выбора последовательности чисел

h1 ,h2 ,…,h t. Кнут [14] показал, что достаточно эффективная реализация получается при

следующей зависимости: h(i-1)=3h(i)+1, h(t)=1, t=(log3n) -1. Наилучшая

последовательность приращений неизвестна. Однако доказано, что числа этой

последовательности не должны быть кратны друг другу43. Более подробный анализ

метода Шелла приведен в [14]. Показано, при определенном выборе последовательности

h(i) сложность алгоритма может оцениваться как O(nlog2 n) » O(n1,2 ). При реализации

алгоритма для хранения последовательности используется массив. Эффективность этого

алгоритма объясняется тем, что при каждом проходе используется относительно

небольшое число элементов или элементы массива уже находятся в относительном

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

Алгоритм сортировки с помощью кучи (пирамидальная сортировка).Рассмотрим

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

обновлении R2 алгоритм передает из R1 максимальный элемент (случай сортировки по

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

поиска максимального элемента и его удаления. АТД с такими операциями хорошо

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

реализации такого типа данных (массив, линейный список) дает линейную оценку для

реализации операции поиска максимального элемента, возникает вопрос об

использовании древообразных структур, поддерживающих требуемое отношение порядка


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

структура существует и называется двоичной кучей. В силу свойства транзитивности при

поиске максимального элемента отпадает необходимость попарного его сравнения с

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

поддержки основных свойств структуры при изменении R1 . Покажем, что можно за O(n)

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

порядок на элементах множества R 1.

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

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

бинарных деревьев. Рассмотрим бинарное дерево, каждая вершина которого

соответствует некоторому элементу массива. Если вершина соответствует элементу ai , то отец этой вершины хранит информацию об элементе ai/2 , а дети соответствуют

элементам массива с индексами 2i и 2i +1. Такое дерево напоминает пирамиду, вид этого

дерева показан на рисунке

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

Основное свойство, которое должно поддерживаться кучей заключается в следующем:

значение элемента приписанному отцу вершины ai не меньше значения, приписанного

самой вершине ( aотец ( I ) = a ( i) ). Очевидно, куча, для которой выполняется основное

свойство, задает частичный порядок на элементах массива (а потому её ещё называют

сортирующим деревом). Процедура построения отношения частичного порядка, является

рекурсивной. Пусть отношение частичного порядка выполняется для вершин поддеревьев

Поскольку на каждом из деревьев D1 и D2 выполняется отношение частичного порядка,

то это отношение может быть нарушено только для корня дерева. Сравнивая элемент a с

корнями деревьев D1 и D2 и, в случае нарушения порядка, обменивая a со значением

одного из корней, получаем ситуацию, когда отношение частичного порядка может не

выполняться для одного из деревьев D1 или D2. Продолжая рекурсивно этот процесс,

можно добиться того, что для всех поддеревьев выполняется отношение частичного

порядка. Поскольку, необходимо просмотреть n / 2 поддеревьев, и построение

частичного порядка для каждого из них занимает не более log n шагов получаем верхнюю

оценку на время построения кучи O(nlog n) . Более точный подсчет с учетом высоты, уже

построенной части пирамиды дает оценку O(n) .

Рассмотрим пример построения кучи для последовательности 13, 11, 23, 10, 12, 18, 30,


8, 7, 6, 15, 21. Строка № (до) характеризует состояние массива до операции построения

частичного порядка на поддереве, корень которого выделен жирным шрифтом. Строка №

(после) характеризует массив после построения частичного порядка на соответствующем

поддереве. В этой строке выделены элементы, которые участвуют (посредством обмена) в

построении требуемого порядка.

Ниже на рисунке графически проиллюстрированы шаги по построению сортирующего

дерева для нашего примера

Слева от стрелки нарисовано состояние поддерева до выполнения шага, а справа – после.

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

максимального элемента занимает O(1) шагов. Поскольку в процессе работы алгоритма

множество R1 изменяется (удаляются максимальные элементы), то необходима

процедура, позволяющая поддерживать свойства сортирующего дерева при изменении R 1.

Можно показать, что время работы такой процедуры связано с высотой дерева и

составляет O(log n) . Поскольку сортирующее дерево кодирует массив с фиксированными

связями между определенными индексами элементов, все операции на дереве легко

моделируются на линейном массиве. Основное свойство сортирующего дерева для

массива записывается с использованием неравенств: a(i)=

Алгоритм сортировки с помощью двоичной кучи состоит из следующих шагов:

1. Построение сортирующего дерева, сложность — O(n).

2. Для каждого начального отрезка массива длины i(i = n,n -1,…,1) найти

максимальный элемент, поменять этот элемент с последним элементом начального

отрезка массива, уменьшить число элементов 1 и переставляя элементы

восстановить основное свойство кучи. Сложность — O(nlog n)

Рассмотрим сортировку на нашем примере. В строках таблицы приведены состояния

последовательностей R1 и R2 на момент обновления R2(после) и приведения

последовательности R1 к основному свойству кучи (до). Элементы, участвующие в

обменах на соответствующих шагах выделены жирным шрифтом.

Статьи к прочтению:

Сортировка Шелла! Рекомендую тебе понять ее! Алгоритм прост и эффективен!

Похожие статьи:

Данный тип сортировки по своей сути является обратным слиянию. Данный тип сортировки начал широко использоваться со времен машин с перфокарточным…

Существует три общих метода сортировки массивов: Обмен Выбор (выборка) Вставка Чтобы понять, как работают эти методы, представьте себе колоду игральных…

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL