Файл: Методы сортировки данных.pdf

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

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

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

Сортировка методом Шелла работает путём вставки отсортированных подмножеств основного списка. Каждое подмножество формируется за счёт выборки каждого n-ной части массива, начиная с любой позиции в списке. В результате будет получено n подмножеств, которые отсортированы методом вставок. Полученная последовательность элементов массива называется отсортированной по n. Затем значение n уменьшается и снова выполняется сортировка. Уменьшение значений n происходит до тех пор, пока n не будет равно 1, после чего последний проход будет представлять собой стандартную сортировку методом вставок.

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

Какие значения n лучше использовать?

Дональд Л.Шелл предложил значения 1, 2, 4, 8, 16, 32 и т.д. (естественно в обратном порядке), но с этими значениями связана одна проблема: до последнего прохода элементы массива с чётными индексами никогда не сравниваются с элементами нечётного индексами. И, следовательно, при выполнении последнего прохода всё ещё возможны перемещения элементов на большие расстояния.

В 1969 году Дональд Кнут (Donald Knuth) предложил последовательность 1, 4, 13, 40, 121 и т.д. (каждое последующее значение на единицу больше, чем утроенное предыдущее значение). Для массивов средних размеров эта последовательность позволяет получить достаточно высокие характеристики быстродействия.

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

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

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

Метод пирамидальной сортировки более подробно изложен в книге Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайн: «Алгоритмы: построение и анализ, 2-издание» и в учебном пособии для студентов вузов Л.Г. Гагариной и В.Д. Колдаева «Алгоритмы и структуры данных».

Метод сортирующего дерева основывается на повторяющихся поисках наименьшего значения среди n элементов массива, среди оставшихся n-1 элементов и т.д. К примеру, сделав n/2 сравнений, можно определить в каждой паре значений меньшее значение. С помощью n/4 сравнений — меньшее значение из пары уже выбранных меньших и т. д. Проделав n - 1 сравнений, мы можем построить дерево выбора, по аналогии представленного на рисунке 7.1 и идентифицировать его корень как нужное нам наименьшее значение.

06

06

06

06

12

12

12

44

44

55

42

94

18

18

67

Рис. 7.1. Повторяющиеся выборы среди двух значений

Второй этап сортировки — это спуск вдоль пути, отмеченного наименьшим элементом, и непосредственное исключение его из дерева путем замены на пустой элемент (дырку), как показано на рисунке 7.2. ^[7]

12

12

12

44

44

55

42

94

18

18

67

Рис. 7.2. Исключение наименьшего значения

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

12

18

67

12

12

12

44

44

55

42

94

18

18

67

Рис.7.3. Сдвигание элементов и заполнение пустых элементов (дырок)

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

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

Пирамида определяется как последовательность ключей h_l, h_l+1,...,h_r, такая, что hi <= h_2i. и hi< =h_2i+1, для i =l,..., r/2.

Если любое двоичное дерево рассматривать как массив, представленный на рисунке 7.4, то можно говорить, что деревья сортировок, представленными на рисунках 7.5 и 7.6 являются пирамидами, а элемент h_l её наименьший элемент: h_l = min(h₁, h₂,…, h_n).

h₁

h₃

h₇

h₂

h₅

h₁₀

h₄

h₈

h₉

h₁₁

h₁₂

h₆

h₁₃

h₁₅

h₁₄

Рис. 7.4. Массив h, представленный в виде двоичного дерева

h₁

06

12

42

94

55

18

Рис.7.5. Пирамида из семи элементов.

Представим, что существует некоторая пирамида с заданными элементами hi,.., hr. Возьмем, в качестве примера, непосредственно исходной пирамиду h1, ...,h7, показанную на рисунке 7.5, и расширим эту пирамиду влево, добавив к ней элемент h1 = 44.

Каждый последующий элемент, в нашем случае это - h1 = 44, сначала помещается в вершину дерева, а затем «просеивается» по своему пути, на котором находятся меньшие по сравнению с ним элементы, которые, в свою очередь, поднимутся наверх, так как их значение меньше помещаемого в дерево элемента. В нашем случае 44 меняется местами с 06, затем с 12, и так формируется дерево, показанное на рисунке 7.6.

06

122

44

42

94

55

18

Рис.7.6.Просеивание ключа - 44 через пирамиду.

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

Куда эффективнее остальных может сработать метод сортировки К. Хора, который получил также название «быстрая сортировка» или же «сортировка с разделением». В базу этого метода сортировки положено последовательное дробление взятого множества на части. Перед тем, как приступить к работе, необходимо определить тот элемент, что стоит в середине взятого массива, а после массив стоит разделить на две равные части. Глядя на левую часть массива с левой стороны на правую, выполним поиск такого элемента массива, что M[I] > X, затем при просмотре правой части справа налево отыскивается такой элемент, что M[I] X, не будут обменены с элементами, расположенными справа от середины и удовлетворяющими условию M[I] < X . По окончанию таких действий мы получим массив из двух частей. Далее левая часть в свою очередь дробится на две части и сортируется описанным выше способом. Этот процесс происходит до тех пор, пока в каждой из частей не останется по одному элементу. Затем аналогично сортируется правая часть первоначального массива.

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

Заключение

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

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

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

Теперь, подведя итоги изучения усовершенствованных методов сортировки, мы можем сравнить их эффективность. Как и раньше, n — число сортируемых элементов, а С и М — соответственно число необходимых сравнений ключей и число обменов. Для всех прямых методов сортировки можно дать точные аналитические формулы. Для усовершенствованных методов нет сколько-либо осмысленных, простых и точных формул. Но, в то же время, возвращаясь к теме сортировки методом Шелла, нельзя не обратить внимание на вычислительные затраты, которые составят с×n^1.2, а для пирамидальной сортировки и метода быстрой сортировки — с×n×logn, где с — соответствующие коэффициенты.

Данные формулы дают нам грубую меру для производительности как функции n и позволяют разбить методы сортировки на примитивные, прямые методы (n²) и на усложненные или "логарифмические" методы (n×log(n)).

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

Итак, подведем итог: мы выяснили, что алгоритмы устойчивой сортировки являются самыми медленными из возможным алгоритмов сортировки массивов, принадлежащих к классу О(n²), применяются при небольшом n. Алгоритмы неустойчивой сортировки – наиболее быстрые, принадлежащие к классу О(n×log(n)), применяются при большом n. Выбор наиболее подходящего метода сортировки первоначальных массивов будет зависеть от структуры обрабатываемых данных и от количества элементов. Подходя к решению новой задачи, стоит подобрать тот метод сортировки массивов, что окажется максимально эффективным.

Список использованной литературы

1. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с.
2. Вирт Н. Книга: Алгоритмы и структуры данных. [Текст] / Н.Вирт. Перевод с английского – М. Издательство «Мир», 1989. -358 с.
3. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. [Текст] = Алгоритмы: построение и анализ, 2-издание. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Перевод с английского – М. Издательский дом «Вильямс», 2005. – 1296 с.
4. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с.

1. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

2. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

3. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

4. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

5. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

6. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

7. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑