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

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

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

Сортировка слиянием — это один из видов рекурсивных сортировок [1,12]. В ее основе лежит замечание, согласно которому слияние двух отсортированных списков выполняется быстро. Список из одного элемента уже отсортирован, поэтому сортировка слиянием разбивает список на одноэлементные куски, а затем постепенно сливает их. Поэтому вся деятельность заключается в слиянии двух списков.
Сортировку слиянием можно проиллюстрировать примером:
44 55 12 42 94 18 06 67
Разобьем на первом шаге файл на два файла:
44 55 12 42
94 18 06 67
Объединим эти два файла снова в один файл, содержащий упорядоченные пары:
44 94 ’ 18 55 ’ 06 12 ’ 42 67
Снова разобьем файл и объединим пары в четверки:
44 94 ’ 18 55
06 12 ’ 42 67
Слияние дает:
06 12 44 94 ’ 18 42 55 67
Снова разобьем файл на два и объединим четверки:
06 12 44 94
18 42 55 67
Слияние дает:
06 12 18 42 44 55 67 94
Итак, основной операцией является слияние. При слиянии требуется дополнительная память для размещения файла, образующегося при слиянии. Операция линейно зависит от количества элементов в объединяемых массивах.
В общем, виде можно предположить, что сливаемые файлы имеют разную размерность: A[1 .. n], B[1 .. m]. При слиянии образуется третий массив C[1 ..n+m].
 
Merge (A [1..n ], B [1.. m ], C [1..n+m ])
    1 i ← 1
    2 j ← 1
    3 for k ← 1 to n+m
    4   do ifi = n
    5   then C [k] ← B [j]
    6 j ← j + 1
    7 else    if j = m
    8                    then C [k] ← A [i]
    9    i ← i + 1
    10   else if A [i] < B [j]
    11 then C[k] ← A[i]
    12 i ← i + 1
    13   else C[k] ←B [j]
     14   j ←j + 1
 
Такая операция называется двух путевым слиянием. Операция имеет и самостоятельное значение. Например, если достаточно большой  упорядоченный файл  пополняется новыми элементами, то новые элементы группируются в пакеты и записываются в файл. После этого файл с новыми данными сортируется и сливается с большим файлом.
Нисходящая сортировка является рекурсивной операцией, которая делит файл пополам и выполняет по рекурсии сортировку обеих половин. Дерево рекурсии имеет вид представленный на рис.3.7-3.8

Рис.3.7 Дерево рекурсии

Рекурсия ограничена снизу размером разделяемого файла, равным 1. Каждый рекурсивный вызов делит файл пополам. В случае если размер файла кратен 2, получается полное, сбалансированное дерево рекурсии.


Рис.3.8 Дерево рекурсии

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

 
Этот алгоритм имеет вид:
MergeSort(list,first,last)
list сортируемый список элементов
first номер первого элемента в сортируемой части списка
last номер последнего элемента в сортируемой части списка
if firstmiddle=(first+last)/2
MergeSort(list.first.middle)
MergeSort(list,middle+l,last)
MergeLists(list.first.middle,middle+l,last)
end if
Основной функцией является функция - MergeLists.Рассмотрим ее подробно.
Пусть А и В — два списка, отсортированных в порядке возрастания. Такое упорядочивание означает, что первым элементом в каждом списке является наименьший элемент в нем, а последним — наибольший.
Мы знаем, что при слиянии двух списков в один наименьший элемент в объединенном списке должен быть первым либо в части А, либо в части В, а наибольший элемент в объединенном списке должен быть последним либо в части А, либо в части В. Построение нового списка С, объединяющего списки А и В, мы начнем с того, что перенесем меньший из двух элементов А[1] и В[1] в С[1]. Но что должно попасть в С[2]? Если элемент А[1] оказался меньше, чем -В[1], то мы перенесли его в С[1], и следующим по величине элементом может оказаться В[1] или А[2]. И тот, и другой вариант возможны, поскольку мы знаем только, что А[2] больше, чем А[1] и меньше, чем А[3], однако нам неизвестно отношение между величинами списка А и списка В. Похоже, что проще всего осуществить слияние, если завести два указателя, по одному на А и В, и увеличивать указатель того списка, очередной элемент в котором оказался меньше. Общая процедура продолжает сравнивать наименьшие элементы еще не просмотренных частей списков А и .В и перемещать меньший из них в список С. В какой-то момент, однако, элементы в одном из списков А или В закончатся. В другом списке при этом останутся элементы, большие последнего элемента в первом списке. Нам необходимо переместить оставшиеся элементы в конец общего списка.
В совокупности эти рассуждения приводят к следующему алгоритму:
MergeLists(list,start1,endl,start2,end2)
list упорядочиваемый список элементов
start 1 начало "списка" А
endl конец "списка" А
start2 начало "списка" В
end2 конец "списка" В
// предполагается, что элементы списков А и В
// следуют в списке list друг за другом
finalStart=startl
f inalEnd=end2
indexC=l
while (startl<=endl) and (start2<=end2) do
if Iist[startl]result[indexC]=list[startl]
startl=start1+1
else
result[indexC]=list[start2]
start2=start2+l
end if
indexC=indexC+l
end while
// перенос оставшейся части списка
if (start K=endl) then
for i=startl to endl do
result[indexC]=list[i]
indexC=indexC+l
end for
else
for i=start2 to end2 do
result[indexC]=list[i]
indexC=indexC+l
end for
end if
// возвращение результата в список
indexC=l
for i=finalStartl to finalEnd do
list [i]=result [indexC]
indexC=indexC+l
end for

Сравнением элементов занимается только процедура MergeLists, поэтому мы начнем с ее анализа. Посмотрим на случай, когда все элементы списка А меньше всех элементов списка В. Что будет делать процедура MergeLists? Она по-прежнему сравнивает А[1] и -В[1], и поскольку элемент А[1] меньше, он переносится в список С. Затем сравниваются элементы А[2] и В[1] и меньший элемент А[2] переносится в список С. Процесс сравнения всех элементов списка А с B[i] продолжается пока мы не дойдем до конца списка А, так как все элементы в нем меньше, чем B[i]. Это означает, что алгоритм выполняет NA сравнений, где через NA обозначено число элементов в списке А. Наоборот, если все элементы списка В оказываются меньше всех элементов списка А, то число сравнений оказывается равным NB, числу элементов в списке В.
А что если первый элемент списка А больше первого элемента списка В, но все элементы списка А меньше второго элемента списка В1
Тогда мы сравниваем А[1] и В[1] , переносим элемент В[1] в список С и оказываемся в той же ситуации, что и раньше: после сравнения каждого элемента списка А с В[2] мы будем переносить его в С1
В этом случае, однако, мы проделали не только NA сравнений элементов списка А с В[2], но и сравнили А[1] с В[1] , поэтому полное число сравнений будет равно NA + 1. В остальных случаях также ясно, что описанная в первом абзаце настоящего раздела ситуация может быть, и действительно оказывается, наилучшим случаем.
Мы видели, что если все элементы списка А заключены между B[i] и -В [2], то число сравнений увеличивается по сравнению с ситуацией, когда все элементы списка А меньше всех элементов списка В. Посмотрим, не приводит ли противоположная возможность к наихудшему случаю. Посмотрим, что будет, если значения элементов списков А и В идут «через один». Другими словами, что происходит, если А[1] находится между В[1] и В[2], А[2] находится между В[2] и -В[3], А[3] находится между В[3] и В[4] и т.д. Отметим, что в результате каждого сравнения один из элементов списков А или В переносится в С. В том упорядочивании, которое рассматривалось выше, перенос происходит из обоих списков поочередно: сначала из В, затем из А, затем опять из .В и т.д. пока не окажутся перенесенными все элементы за исключением последнего в списке А. Поскольку по результатам сравнения элементов обоих списков мы перенесли все элементы кроме одного, число сравнений в этом наихудшем случае оказывается равным NA + NB — 1.
Это означает, что сортировка слиянием чрезвычайно эффективна даже в наихудшим случае O(NlogN); проблема, однако, состоит в том, что процедуре MergeLists для слияния списков требуется дополнительная память.

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

Быстрая сортировка — еще один рекурсивный алгоритм сортировки [3,4]. Выбрав элемент в списке, быстрая сортировка делит с его помощью список на две части. В первую часть попадают все элементы, меньшие выбранного, а во вторую — большие элементы.
Алгоритм Quicksort действует по-другому, поскольку он применяется рекуррентно к обеим частям списка. В среднем такая сортировка эффективна, однако в наихудшем случае ее эффективность такая же, как у сортировки вставками и пузырьковой.
Быстрая сортировка выбирает элемент списка, называемый осевым, а затем переупорядочивает список таким образом, что все элементы, меньшие осевого, оказываются перед ним, а большие элементы – заним. В каждой из частей списка элементы не упорядочиваются. Если q — окончательное положение осевого элемента, то нам известно лишь, что все значения в позициях с первой по q — 1 меньше осевого, а значения с номерами от q + 1 до N больше осевого. Затем алгоритм Quicksort вызывается рекурсивно на каждой из двух частей. При вызове процедуры Quicksort на списке, состоящем из одного элемента, он ничего не делает, поскольку одноэлементный список уже отсортирован.
Поскольку основная работа алгоритма заключается в определении осевого элемента и последующей перестановке элементов, главная процедура в алгоритме Quicksort должна лишь проследить за границами обеих частей. Поскольку перемещение ключей происходит в процессе разделения списка на две части, вся работа по сортировке выполняется при возвращении по рекурсии.
Вот алгоритм быстрой сортировки:
Quicksort(list,first.last)
list упорядочиваемый список элементов first номер первого элемента в сортируемой части списка last номер последнего элемента в сортируемой части списка
if firstpivot=PivotList(list,first,last)
Quicksort(list,first,pivot-1)
Quicksort(list,pivot+l,last)
end if
У функции PivotList есть по крайней мере два варианта. Первый из них, который легко запрограммировать и понять, описан в настоящем разделе. Второй вариант записать труднее, однако он работает быстрее. Он описан в упражнениях.
Функция PivotList берет в качестве осевого элемента первый элемент списка и устанавливает указатель pivot в начало списка. Затем она проходит по списку, сравнивая осевой элемент с остальными элементами списка. Обнаружив элемент, меньший осевого, она увеличивает указатель PivotPoint, а затем переставляет элемент с новым номером PivotPoint и вновь найденный элемент. После того, как сравнение части списка с осевым элементом уже произведено, список оказывается разбит на четыре части. Первая часть состоит из первого осевого — элемента списка. Вторая часть начинается с положения first+1, кончается в положении PivotPoint и состоит из всех просмотренных элементов, оказавшихся меньше осевого. Третья часть начинается в положении PivotPoint+1 и заканчивается указателем параметра цикла index. Оставшаяся часть списка состоит из еще не просмотренных значений. Соответствующее разбиение приведено на рис. 2.9.


Рис.2.9 Значение указателей в алгоритме PivotList

Вот алгоритм PivotList.
PivotListdist , first .last)
list обрабатываемый список
first номер первого элемента
last номер последнего элемента
PivotValue=list [first]
PivotPoint=first
for index=first+1 to last do
if list [index] PivotPoint=PivotPoint+l
Swap(list [PivotPoint] , list [index] )
end if
end for
// перенос осевого значения на нужное место
Swap (list [first] , list [PivotPoint])
return PivotPoint

При вызове процедуры PivotList на списке из N элементов она выполняет N — 1 сравнение, поскольку значение PivotValue сравнивается со всеми остальными элементами списка. Как мы уже говорили, быстрая сортировка представляет собой алгоритм вида разделяй и властвуй, поэтому можно предположить, что в наилучшем случае PivotList создает две части одинакового размера. Так оно и есть. Тогда в наихудшем случае размеры списков должны быть максимально неравны. Наибольшая разность величин списков достигается, когда значение PivotValue либо больше, либо меньше всех остальных элементов списка.
В этом случае в одном из списков нет ни одного элемента, а в другом N — 1 элемент. Если такая ситуация возникает при всяком рекурсивном вызове, то всякий раз будет происходить удаление одного элемента (PivotValue). Это означает, что число сравнений дается формулой

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

3.8 Сравнение методов


Заканчивая обзор методов сортировки, сравним их эффективность.
Для всех прямых (простых) методов сортировки можно дать точные аналитические формулы согласно которым можно определить значения для вычислительной сложности алгоритмов сортировки [3]. Столбцы таблицы определяют минимальное, усреднененное и максимальное по всем n! перестановкам из n элементов значения, С-количество сравнений, а M – обменов.

Таблица 3.1
Мин. Сред. Макс. Метод обмена
M=0

Метод выбора


Метод включения



Анализ модифицированных сортировок достаточно сложен с математической точки зрения. Можно отметить, что время выполнения сортировки Шелла пропорционально , а для быстрой сортировки число операций сравнения равно , а число операций обмена равно приблизительно . Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки.
Это хорошо согласуется с данными вычислительных экспериментов, приведенных в работе [3] и приведенных в приложении А.
Анализ экспериментальных данных исследований методов сортировки, представленных в приложении А позволяет сделать вывод о предпочтительности использования в качестве простых методов сортировки метода вставки, в качестве метода сортировки с вычислительной сложностью порядка О(log2N) целесообразно использование методов быстрой и пиромидальной сортировки.
Необходимо отметить, что в случае незначительного количества элементов массива порядка n=4000, выбор алгоритма, сортировки особого значения не имеет, так как алгоритмы одних клас сов например простые и модифицированные показывают временные оценки характерные для всего класса алгоритмов.
Заключение


Анализ основных классов алгоритмов поиска показал общность этих алгоритмов, в частности во всех алгоритмах поиска можно выделить следующие процедуры:
- определение свойства элемента. В большинстве случаев выполнение этого щага алгоритма связано с вычислением значением элемента, или ключа элемента, который должен быть определен;
- процедуры сравнения свойства элемента или ключа элемента с эталонным свойством;
- организация перебора элементов множества (массива, списка, структуры данных), т. е. проведение цикла по элементамрассматриваемой структуры данных.
Различия методов поиска сосредоточены в методах перебора, в стратегии поиска т.е. при выполнении второго и третьего шагов алгоритмов.
Для всех прямых (простых) методов сортировки можно дать точные аналитические формулы согласно которым можно определить значения для вычислительной сложности алгоритмов сортировки.
Анализ модифицированных сортировок достаточно сложен с математической точки зрения
Анализ экспериментальных данных исследований методов сортировки, представленных позволяет сделать вывод о предпочтительности использования в качестве простых методов сортировки метода вставки, в качестве метода сортировки с вычислительной сложностью порядка О(log2N) целесообразно использование методов быстрой и пиромидальной сортировки.
Необходимо отметить, что в случае незначительного количества элементов массива порядка n=4000, выбор алгоритма, сортировки особого значения не имеет, так как алгоритмы одних клас сов например простые и модифицированные показывают временные оценки характерные для всего класса алгоритмов.

Ускорение сортировки может быть обеспечено при использовании нескольких (p>1) вычислительных элементов (процессоров или ядер). Исходный упорядочиваемый набор в этом случае «разделяется» на блоки; которые могут обрабатываться вычислительными элементами параллельно.

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

Ахо А. Структуры данных и алгоритмы: учеб. пособ. / А. Ахо, Д.Э. Хопкрофт, Д. Ульман; пер. с англ. - М.: Издательский дом "Вильяме", 2000.
Ахтамова С.С. Алгоритмы поиска данных // Современные наукоемкие технологии. – 2007. – № 3 – С. 11-14.
Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi. Пер. с англ./Джулиан М. Бакнелл. - СПб: ООО «ДиаСофтЮП», 2003.- 560 с.
Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 2001.
Гагарина Л.Г. Алгоритмы и структуры данных: учеб. пособие/ Л.Г. Гагарина, В.Д. Колдаев. - М.: Финансы и статистика; ИНФРА-М, 2009. -304 с.
Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер с англ. И.В. Романовского. — СПб.: Невский диалект; БХВ-Петербург, 2003 г. — 654 с.
Голицына ОЛ., Попов И.И. Основы алгоритмизации и программирования: учеб. пособие. — 3-е изд., испр. и доп. — М: ФОРУМ, 2008. — 432 с
ГОСТ «Единая система программной документации» (ЕСПД): ГОСТ 19.701-90.
Информатика : учебник для вузов / под ред. Н.В. Макаровой. – М. : Финансы и статистика, 2007. – 768 с.
Кнут, Д. Искусство программирования. Т. 3. Сортировка и поиск. - М.: Издательский дом «Вильямс», 2003.
Колдаев В. Д. Основы алгоритмизации и программирования: Учебное пособие / Под ред. проф. Л. Г. Гагариной. — М.: ИД «ФОРУМ»: ИНФРА-М, 2006. — 416c.
Кормен, Томас X., Лейзерсон, Чарльз И., Ривсст, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. — М. : Издательский дом "Вильяме", 2005. — 1296 с.
Королев, Л. Н. Информатика. Введение в компьютерные науки / Л. Н. Королев, А. И. Миков. - М.: Высш. шк., 2003.
Макконнелл Дж. Основы современных алгоритмов. Москва: Техносфера, 2004. - 368с.
Мейн М. Структуры данных и другие объекты в С++ / М. МеЙн, У Савитч; пер. с англ. - М.: Издательский дом "Вильяме", 2002.
Николаев В. И., Иванова И. В. Теория алгоритмов: Текст лекций. - СПб.: СЗТУ, 1995.
Николаев В. И., Чалов Д. В., Сиоирев В. Н. Информатика. Теоретические основы: Учеб. пособие. - СПб.: СЗТУ, 2002.
Островейковский В. А. Информатика: Учебник для вузов. - М.: Высш. шк.. 2000.
Сотанин С. В. Численный анализ методов сортировки. [Электронный ресурс.- метод доступа: http://conf.sfu-kras.ru/sites/mn2011/thesis/s31/s31_01.pdf]
Хусаинов Б.С. Структуры и алгоритмы обработки данных: примеры на языке Си: учеб. пособ. / Б.С. Хусаинов. - М.: Финансы и статистика, 2004.
Шень А. Программирование: Теоремы и задачи / А. Шень. - М.: МЦНМО, 2004.
Приложение А
Результаты вычислительных экспериментов по сортировке данных


Рис.А.1 – Оценка времени метода пузырьковой сортировки

Рис.А.2 – Оценка времени метода сортировки Шелла

Рис.А.3– Оценка времени метода сортировки Шелла


Рис.А.4– Оценка времени простых методов сортировки

Рис.А.5 – Оценка времени методов сортировки с вычислительной сложностью порядка О(log2N)








44









54