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

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

Южно-Российский государственный технический университет (НПИ)

 

СТРУКТУРЫ И АЛГОРИТМЫ

ОБРАБОТКИ ДАННЫХ

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Для лабораторных и практических занятий

 

 

 

 

Новочеркасск

ЮРГТУ (НПИ)

2013

Составитель Фоменко Г.П.

 

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

 

Направление 220400 “Управление в технических системах”

Профиль “Управление и информатика в технических системах”

Курс – 2 дневной формы обучения

Тираж 20 экз.

Объем в стр

 

 

Методические указания обсуждены и рекомендованы к использованию в учебном процессе на заседании кафедры “Автоматика и телемеханика”

Протокол №… от “ “ января 2013г.

 

 

Зав. кафедрой АиТ В.И.Лачин

 

Лабораторная работа №1

Методы сортировки

Цель работы:

1. Изучить различные методы сортировки;

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

 

Время выполнения 4 часа.

 

ЗАДАНИЕ

 

§ Изучить методы сортировки;

§ Разработать программу, осуществляющую реализацию алгоритма сортировки согласно варианту задания;

§ Произвести отладку программы путем ввода исходных данных и проверки корректности полученного результата;

§ Сделать отчет.

 

 

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

 

Сортировка - это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, і, Ј. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию. Рассмотрим различные алгоритмы сортировки и выясним, почему возникла необходимость появления такого большого числа алгоритмов решения одной и той же задачи.

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

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

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

Методы сортировки

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

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

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

О сложности алгоритмов

При рассмотрении методов будем оперировать понятиями временной T и пространственной O теоретической сложности (в дальнейшем будем опускать слово «теоретическая») алгоритма, поэтому вкратце упомянем, что это такое.

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

Например, если число тактов (действий), необходимое для работы метода, выражается как 11*n²+19*n*log(n)+3*n+4, где n-размерность задачи, то мы имеем дело с алгоритмом со сложностью T(n²). Фактически, мы из всех слагаемых оставляем только слагаемое, вносящее наибольший вклад при больших n (в этом случае остальными слагаемыми можно пренебречь) и игнорируем коэффициент перед ним.

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

Временная (пространственная) сложность не позволяет определить время (необходимый объем дополнительной памяти) работы алгоритма, но она позволяет оценить динамику роста времени (объема дополнительной памяти), необходимого для работы метода, при увеличении размерности задачи. Например, для алгоритма с временной сложностью T(n²) при достаточно больших n можно утверждать, что при увеличении размера задачи (при сортировке - размера массива) в 3 раза время работы алгоритма увеличится в 3²=9 раз.

Если операция выполняется за фиксированное число шагов, не зависящее от размера задачи, то принято писать T(1).

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

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

• максимальную сложность или сложность наиболее неблагоприятного случая, когда метод работает дольше всего;
• среднюю сложность - сложность метода в среднем;
• минимальную сложность - сложность в наиболее благоприятном случае, когда метод справляется быстрее всего.

Алгоритмы, рассматриваемые здесь, имеют временные сложности T(n²), T(n*log(n)), T(n). Минимальная сложность всякого алгоритма сортировки не может быть меньше T(n). Максимальная сложность метода, оперирующего сравнениями, не может быть меньше T(n*log(n)). Доказательство последнего факта можно найти в многочисленной серьезной теоретической литературе, посвященной проблемам сортировки. Однако есть методы, которые не сравнивают элементы между собой. Мы рассмотрим один из них - сортировку распределением.

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

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

for i:= 1 to N dobegin <вычислить_место_k+1_элемента_A[i] в_результирующем_массиве_B> B[k+1]:= A[i];end;

Слева от B[k+1] должны стоять элементы большие или равные B[k+1]. Значит число k складывается из количества элементов меньших A[i] и, возможно, некоторого числа элементов, равных A[i]. Условимся, что из равных мы будем учитывать только те элементы, которые в исходном массиве стоят левее A[i]. Теперь вычисление k можно записать следующим образом:

k:= 0;for j:= 1 to N do if (A[i]>A[j])or((A[i]=A[j])and(i>j)) then Inc(k);

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

Сортировка включением

В этой сортировке массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива.

Простое включение

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

Так как массив из одного элемента можно считать отсортированным, начнем с i=2.

Программа будет выглядеть так:

for i:= 2 to n dobegin Tmp:= A[i]; j:= i-1; while (A[j]>Tmp)and(j>1) do begin A[j+1]:= A[j]; Dec(j) end; A[j+1]:= Tmp;end;

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

Метод Шелла

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

Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i-h], A[i-2h], A[i-3h] и так далее, где h - положительная константа. Таким образом формируется массив, в котором «h- серии» элементов, отстоящих друг от друга на h, сортируются отдельно.

Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h=1.

В настоящее время неизвестна последовательность h_i, h_i-1, h_i-2,..., h₁, оптимальность которой доказана. Для достаточно больших массивов рекомендуемой считается такая последовательность, что h_i+1=3h_i+1, а h₁=1. Начинается процесс с h_m-2, где m - наименьшее целое такое, что h_mі n. Другими словами h_m-2 первый такой член последовательности, что h_m-2і [n/9].

Теперь запишем алгоритм:

Step:= 1;while Step < N div 9 do Step:= Step*3 + 1;Repeat for k:= 1 to Step do begin i:= Step + k; while i <= N do begin x:= A^[i]; j:= i - Step; while (j >= 1) and (A^[j]>x) do begin A^[j + Step]:= A^[j]; Dec(j); end; A^[j + Step]:= x; Inc(i, Step); end; end; Step:= Step div 3;until Step=0;

Как показывают теоретические выкладки, которые мы приводить не будем, сортировке методом Шелла требуется в среднем 1,66n^1,25 перемещений.

Сортировка извлечением

В этих методах массив также делится на уже отсортированную часть A[i+1], A[i+1],..., A[n] и еще не отсортированную A[1], A[2],..., A[i]. Но здесь из неотсортированной части на каждом шаге мы извлекаем максимальный элемент. Этот элемент будет минимальным элементом отсортированной части, так как все большие его элементы мы извлечем на предыдущих шагах, поэтому ставим извлеченный элемент в начало отсортированной части.

Простое извлечение

При простом извлечении мы будем искать максимальный элемент неотсортированной части, просматривая ее заново на каждом шаге. Найдя положение максимального элемента поменяем его с A[i] местами.

for i:= N downto 2 dobegin MaxIndex:= 1; for j:= 2 to i do if A[j]>A[MaxIndex] then MaxIndex:= j; Tmp:= A[i]; A[i]:= A[MaxIndex]; A[MaxIndex]:= Tmp;end;

Простое извлечение во всех случаях имеет временную сложность T(n²) (два вложенных цикла, зависящих от n линейно).

Пузырьковая сортировка

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

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

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

for i:= N-1 downto 1 dobegin Flag:= false; for j:= 1 to i do if a[j]>a[j+1] then begin Tmp:= A[j]; A[j]:= A[j+1]; A[j+1]:= Tmp; Flag:= true; end; if not Flag then Break;end;

Этот алгоритм имеет среднюю и максимальную временные сложности T(n²) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти за исключением памяти для фиксированного числа переменных (i, j, Tmp, Flag). Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к T(n).

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

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

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

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

Запишем то, что мы сейчас сформулировали:

procedure Sort;procedure QuickSort(a, b: Longint);Var x: Longint; {индекс «среднего» элемента}begin x:= элемент_выбранный_средним;...деление на три части: 1) A[a]..A[i]; 2) A[i+1]..A[j-1]; 3) A[j]..A[b] if i>a then QuickSort(a, i); if b>j then QuickSort(j, b);end;begin Sort(1, N);end;

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

i:= A[l]; y:= A[(l+r)div 2]; j:= A[r];if i<=y then if y<=j then x:= (l+r)div 2 else if i<=j then x:= r else x:= lelse if y>=j then x:= (l+r)div 2 else if i>=j then x:= r else x:= l;

Теперь нам надо разделить массив относительно элемента A[x] так, чтобы сначала следовали элементы, меньшие A[x], затем сам элемент A[x], а потом уже элементы, большие или равные A[x]. Для этого мы, двигаясь слева найдем первый элемент A[i], больший A[x], и, двигаясь справа, - первый элемент A[j], меньший A[x]. Если i окажется меньше j, то это значит, что массив еще не поделен на три искомых части, в таком случае обменяем местами элементы A[i] и A[j], а затем продолжим поиск слева от A[i] и справа от A[j].

i:= l; j:= r; x:= A[x];repeat while A[i] < x do Inc(I); while x < A[j] do Dec(j); if i <= j then begin y:= A[i]; A[i]:= A[j]; A[j]:= y; Inc(i); Dec(j); end;until i > j;

Пойдем дальше. Заметим, что все-таки наш способ нахождения «среднего» элемента подмассива в худшем случае приведет к тому, что после деления, например, правая и средняя части поделенного массива будут содержать по одному элементу, а левая все остальные. В этом случае, если мы сначала вызовем QuickSort для левой части, то (опять же в худшем случае) это может породить порядка N рекурсивных вызовов. А значит нам надо будет завести дополнительную память размером пропорциональным N и пространственная сложность будет O(N). Этого можно избежать, если сначала вызывать QuickSort для меньшей части. Тогда можно гарантировать пространственную сложность O(log(N)).

Теперь осталось только собрать вместе части программы:

procedure Sort;procedure QuickSort(a, b: Longint);Var x: Longint; {индекс «среднего» элемента}begin i:= A[l]; y:= A[(l+r)div 2]; j:= A[r]; if i<=y then if y<=j then x:= (l+r)div 2 else if i<=j then x:= r else x:= l else if y>=j then x:= (l+r)div 2 else if i>=j then x:= r else x:= l; i:= l; j:= r; x:= A[x]; repeat while A[i] < x do Inc(i); while x < A[j] do Dec(j); if i <= j then begin y:= A[i]; A[i]:= A[j]; A[j]:= y; Inc(i); Dec(j); end; until i > j; if l-j<i-r then begin if l < j then QuickSort(l, j); if i < r then QuickSort(i, r); end else begin if i < r then Sort(i, r); if l < j then Sort(l, j); end; end;begin QuickSort(1, N);end;

В худшем случае этот алгоритм дает временную сложность T_max(N²) (для случая, когда все выборки «среднего» элемента оказались неудачны), но как показывают теоретические исследования вероятность такого случая очень мала. В среднем же и в лучшем случае получим T(N*log(N)).

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Лабораторная работа выполняется на ПЭВМ.

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

2. Создать отчет

 

 

Контрольные вопросы

§ Что такое сортировка? Чем отличаются внешняя и внутренняя сортировка?

§ Что такое практическая и теоретическая сложности? Можно ли из практической сложности вывести теоретическую? Можно ли из теоретической сложности вывести практическую?

§ Что такое максимальная, средняя и минимальная сложности?

 

Лабораторная работа №2

МЕТОДЫ ПОИСКА

Цель работы:

Ознакомление студента с методами поиска данных.

 

Время выполнения 2 часа.

 

ЗАДАНИЕ

 

§ Изучить различные методы поиска данных в структуре

§ Разработать программу, реализующую работу с динамической структурой.

§ Произвести отладку программы путем ввода исходных данных и проверки корректности полученного результата;

§ Сделать отчет.

 

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

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