Файл: Алгоритмы сортировки данных. (Определение понятия «сортировка массива»).pdf

End;

r:= m-1;

Until k>r

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

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

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

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

Алгоритм метода сортировки Selection sort:

1) Ищем порядковый номер минимального значения в не отсортированной части массива.

2) Меняем его с крайним не отсортированным значением, если крайнее но отсортированное значение является минимальным ничего не делаем.

3) Повторяем пункты 1 и 2 пока весь массив не будет отсортирован^[15].

Пример программы представлен в приложении А.

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

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

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

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

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

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

Первоначально автор сортировки, Дональд Шелл, предложил ряд

[n/4], [n/2], [n/8], …, 1

который давал скорость O(n2).

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

701, 301, 132, 57, 23, 10, 4, 1.

Это — результат многочисленных тестов, до сих пор неизвестно, можно или нельзя его улучшить^[17].

Пример реализации сортировки Шелла паскаль:

incr:= n div 2;

while incr>0 do

begin

for i:=incr+1 to n do

begin

j:= i-incr;

while j>0 do

if A[j]>A[j+incr] then

begin

c:= A[j];

A[j]:=A[j+incr];

A[j+incr]:=A[j];

j:=j-incr

end

else j:=0 { останов проверки}

end;

incr:= incr div 2

end;

Сортировка хорошо подходит для массивов среднего размера — например, до нескольких тысяч элементов (в зависимости от конкретной реализации)^[18].

Глава 3. Логарифмические и линейные алгоритмы

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

Далее рассмотрим более сложные методы сортировки, но они являются более эффективными.

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

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

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

Является «умной» модификацией-синтезом сортировки выбором и пузырьковой сортировки^[19].

Фрагмент программы, а именно пирамидальной сортировки показан ниже:

var L, R: integer;

x: integer;

procedure sift (L, R: integer);

var i, j: integer; x: integer;

begin i:=L; j:=2*L; x:=a[L]j

if (j<R) and (a[j] < a[j+l]) then j:=j+l;

while (j <= R) and (x < a[j]) do begin

a[i]:=a[j]j i:=j; j:=2*j;

if (j < R) and (a[j] < a[j+l]) then j:=j+l;

end;

a[i]:=x

end;

begin

L:=(n Div 2)+l; R:=n;

while L > 1 do begin L:=L-1; sift(L, R) end;

while R > - do begin

x:= a[l]; a[l]:= a[R]; a[R]:=x; R:=R-l; sift(L,

end;

Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших n. В худшем случае требуется n·log2n шагов, сдвигающих элементы. Среднее число перемещений примерно равно (n/2)·log2n, и отклонения от этого значения относительно невелики.

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

«Быстрая сортировка» была создана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод быстрой сортировки основан на подходе "разделяй-и-властвуй". Общий метод сортировки следующий:

1. из массива выбирается некоторый опорный элемент a[i],
2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого, то есть:

1. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность^[20].

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

Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n²) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время^[21].

Процедура сортировки методом быстрой сортировки представлен ниже:

procedure quicksort(var mas: array[1..n] of integer; first, last: integer);

var f, l, mid, count: integer;

begin

f:=first;

l:=last;

mid:=mas[(f+l) div 2]; {вычисление опорного элемента}

repeat

while mas[f]<mid do inc(f);

while mas[l]>mid do dec(l);

if f<=l then {перестановка элементов}

begin

count:=mas[f];

mas[f]:=mas[l];

mas[l]:=count;

inc(f);

dec(l);

end;

until f>l;

if first<l then quicksort(A, first, l);

if f<last then quicksort(A, f, last);

end;

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

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

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

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

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

length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове),

range - количество возможных значений одного разряда (при сортировке слов - количество букв в алфавите).

Количество проходов равно числу length.

Пошаговое описание алгоритма

Пусть даны следующие числа: 39, 48, 54, 59, 34, 41, 32 (length = 2, range = 10)

1. Создаем пустые списки, количество которых равно числу range.

2. Распределяем исходные числа по этим спискам в зависимости от величины младшего разряда (по возрастанию).

Для нашего примера получим:

41

32

54, 34

48

59, 39

(Вообще надо создать 10 списков, но некоторые из них оказались пустыми)

3. Собираем числа в той последовательности, в которой они находятся после распределения по спискам.

Получим: 41, 32, 54, 34, 48, 59, 39

4. Повторяем пункты 2 и 3 для всех более старших разрядов поочередно.

Для двузначных чисел мы должны сделать еще один проход. Распределение по спискам будет выглядеть так:

32, 34, 39

41, 48

54, 59

Объединив числа в последовательность, получим отсортированный массив.

Заключение

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

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

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

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

Библиография

1. Динман М. И. С++. Освой на примерах. - - СПб.: БХВ-Петербург, 2006.- 384 с: ил
2. Катаев, С. М. Бейсик для школьников. Подготовка к ЕГЭ / С. М. Катаев. Л. В. Шеретнева. — СПб.: БХВ-Пстсрбург, 2012. — 272 с.
3. Кетков Ю. Л., Кетков А. Ю. Практика программирования: Бейсик, Си, Паскаль. Самоучитель. — СПб.: БХВ-Петербург, 2001. - 480 с: ил
4. Культин, Н. Small Basic для начинающих /II. Культин, Л. Цой. — СПб.: КХВ-Петербург, 2011. — 256 с.
5. Лафоре P. Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. — СПб.: Питер, 2011. — 704 с.
6. Макарова Н. В., Волков В. Б. Информатика: Учебник для вузов. — СПб.: Питер, 2015. — 576 с.
7. Могилев, А. В. Методы программирования. Компьютерные вычисления/ А. В. Могилев, Л. В. Листрова. - - СПб,: БХВ-Петербург, 2008. - 320 с. - ISBN 978-5-9775-0151-4
8. Простые методы сортировки массивов [онлайн] - URL: http://hosting.vspu.ac.ru/~chul/program/sortmass.pdf (дата обращения 24.09.2016)
9. Понятие сортировки. Прямые методы сортировки [Онлайн] - URL: http://www.aisd.kubsau.ru/lections/lect_kurs_bi/lect9_bi.html (дата обращения 02.10.2016)
10. Основные методы внутренней сортировки. Классификация методов сортировки [онлайн] - URL:http://studopedia.su/14_96708_osnovnie-metodi-vnutrenney-sortirovki.html (дата обращения 28.09.2016)).
11. Сортировка вставками [онлайн] - URL: http://learnc.info/algorithms/insertionsort.html (дата обращения 01.10.2016)
12. Сортировка вставками [онлайн] - URL: http://ucxodnuku.ru/algoritm/sortirovka-vstavkami.html (дата обращения 29.09.2016)
13. Сортировка вставками [онлайн] - URL: http://cppstudio.com/post/462/ (дата обращения 29.09.2016)
14. Сортировка Шелла :: Shell sort [онлайн] - URL: http://sorting.valemak.com/shell/ (дата обращения 29.09.2016)
15. Сортировка кучей :: Heap sort [онлайн] - URL: http://sorting.valemak.com/heap/ (дата обращение 28.09.2016)
16. Быстрая сортировка [онлайн] - URL: http://truthiness.ru/88951d72e2ba6711.html (дата обращения 27.09.2016)
17. Лекция №4.1: Сортировки массивов [Онлайн] - URL:https://www.google.com/search?tbm=bks&q=+%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0+%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2%D0%B0 (дата обращения 02.10.2016)