Размещено на http://www.allbest.ru/

Оглавление

Введение

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

1.1 Алгоритмы сортировки вставками

1.2 Сортировка простым выбором

1.3 Сортировка простым обменом

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

2. Алгоритмы поиска

2.1 Последовательный поиск

2.2 Бинарный поиск

2.3 Поиск подстроки

Заключение

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

Введение

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

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

Научное значение данная работа представляется в анализе и представлении самых известных алгоритмов сортировки. Практическое значение тема «Алгоритмы поиска и сортировки» представляется в исследовании проблем выполнения и применения разных типов алгоритмов поиска и сортировок.

Основная цель этой курсовой работы - анализ алгоритмов поиска и сортировки информации, получение навыков в программировании этих алгоритмов.

Объектом исследования в нашей курсовой работе будут алгоритм сортировки информации и алгоритм поиска данных.

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

Сразу надо отметить, вопросами анализа алгоритмов, группировкой, исследованием и методами их программирования в различные времена были заняты: Кнут Д., Ульман Дж., Левитин А., Цейтлин Г.Е., Гудман С., Хидетниеми С., Ахо А., Хлопккрофт Дж., Вирт Н., Лорин Г., Макконнелл Дж. и другие.

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

Алгоритм (algorithm) -- это любой корректно определенный вычислительный процесс, на входе (input), которого задается какое-то значение или набор значений, а итогом реализации является выходное (output) значение или набор величин. Значит, алгоритм это определенная последовательность вычислительных шагов, которые преобразуют входные значения в выходные.

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

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

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

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

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

Основные критерии эффективности алгоритмов сортировки следующие:

· быстродействие;

· экономия памяти;

· сокращение времени, затрачиваемого программистом, на реализацию алгоритма.

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

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

Во многих программах сортировки оптимально применить простые элементарные алгоритмы. Программы сортировки иногда применяются только единожды (или несколько раз). В случае, когда количество элементов, необходимых отсортировать небольшое (примерно меньше 500 элементов), то тогда применение элементарного алгоритма даст больший эффект, чем новая проработка и отладка громоздкого алгоритма. Элементарные простые методы постоянно полезны для небольших файлов (примерно меньших, чем 50 элементов); конечно сложный алгоритм было бы неразумно применить для подобных файлов, если конечно нет необходимости отсортировать большое количество подобных файлов.

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

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

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

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

Объем применяемой дополнительной памяти алгоритма сортировки - также дополнительный фактор, принимаемый во внимание. Обычно методы сортировки делят на три группы:

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

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

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

Стабильность - также важная свойство методов сортировки. Метод сортировки является стабильным в случае, когда он сохраняет относительный порядок расположения записей с одинаковыми ключами. К примеру, когда алфавитный список учащихся ранжируется по оценкам, тогда стабильный метод организует список, где фамилии учащихся с одинаковыми баллами будут отсортированы по алфавиту, а нестабильный метод организует список, где, возможно, начальный порядок будет нарушен. Большая часть простых методов стабильны, тогда как большая часть всем известных сложных методов - нет. В случае, когда стабильность необходима, тогда можно её добиться путем добавления к ключу маленького индекса перед процессом сортировки или посредством удлинения, каким-то путем, ключа. Стабильность легко принимают за норму; к нестабильности у людей отношение с недоверием. Фактически, только некоторые методы добиваются стабильности без применения дополнительного времени или места.

Для выявления эффективности алгоритма необходимо оценить числа С - нужных сравнений ключей и М - присваиваний элементов. Указанные числа рассчитываются определенными формулами от числа n сортируемых элементов. Удовлетворительные алгоритмы сортировки используют примерно сравнений.

Условимся по терминологии: мы имеем элементы - a₁, a₂, …, a_n. Процедура сортировки предполагает такую перестановку данных элементов в следующем порядке: a_k1, a_k2, …, a_kn, что при данной функции упорядочения f верно отношение f(a_k1)<=f(a_k2)<=…<=f(a_kn).

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

type item = record

key: integer;

{описание прочих элементов}

end;

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

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

1.1 Сортировка вставками

Данный метод в основном применяют те, кто играет в карты. Элементы (карты) условно делятся на готовую конкретную последовательность и входную последовательность . Постоянно на следующем шаге, считая с I = 2 и увеличивая i на один, берется i-й элемент входной последовательности и перекладывается в готовую последовательность, ставя его на нужное место.

Исходные ключи	45	59	12	42	94	18	06	67
I=2	45	59	12	42	94	18	06	67
I=3	12	45	59	42	94	18	06	67
I=4	12	42	45	59	94	18	06	67
I=5	12	42	45	59	94	18	06	67
I=6	18	12	42	45	59	94	06	67
I=7	06	18	12	42	45	59	94	67
I=8	06	18	12	42	45	59	67	94

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

1. Найден элемент ключ, которого меньше, чем ключ x.

2. Достигли левого конца готовой последовательности.

Данный стандартный образец цикла с количеством двух условий окончания предоставляет возможность исследовать всем знакомый способ фиктивного элемента («барьера»). Он легко используется в этом случае, если установить барьер .

Procedure Sortinsert;

Var i,j : index;

x : item;

Begin

For i:=2 to n do Begin

x:=a[i]; a[0]:=x; j:=i-1;

While x.key < a[j].key do Begin

a[j+1]:=a[j];

j:=j-1;

End;

a[j+1]:=x;

End;

End;

Анализ сортировки простыми включениями. Значение сравнений ключей на i-м просеивании будет наибольшим i-1, и наименьшим 1 если допустить, что у всех переводов n ключей равная вероятность, в среднем равная i/2. Число пересылок (присваиваний) рассчитывается, как (с учетом барьера). Таким образом, итоговое значений сравнений и пересылок рассчитывается следующим образом:

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

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

procedure binaryinsertion;

var i,j,l,r,m : index;

x : item;

begin

for i:= 2 to n do begin

x:= a[i];

i := 1;

r := i - 1;

while l <= r do begin

m := (l+r) div 2;

if x.key < a[m].key then r:=m - 1

else l := m+1

end;

for j := i - 1 downto l do a[j+1] :=a [j];

a[l] := x;

end;

end;

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

С = n (Log(n) - Log(e) ± 0,5).

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

1.2 Сортировка простым выбором

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

Этот метод включает следующие условия:

1. Определяется элемент с самым маленьким ключом.

2. Выбранный элемент меняется расположением с первым элементом а[1].

Эти операции затем повторяются с прочими n - 1 элементами, затем c n - 2 элементами, до тех пор, пока в остатке не будет только один элемент - наибольший.

	44	55	12	42	94	18	06	67
	06	55	12	42	94	18	44	67
	06	12	55	42	94	18	44	67
	06	12	18	42	94	55	44	67
	06	12	18	42	94	55	44	67
	06	12	18	42	44	55	94	67
	06	12	18	42	44	55	94	67
	06	12	18	42	44	55	67	94

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

procedure sortselection;

var i,j,k : index;

x: item;

begin

for i := 1 to n - 1 do begin

k := i; х := a[i];

for j :=i+1 to n do

If a[j] .key < x .key then begin

k := j; x := a[j]

end;

a[k] := a[i]; a[i] := x;

end

end;

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

Наименьшее значение присваиваний равно когда с самого начала упорядочены ключи и равно наибольшему значению когда изначально ключи выстроены в обратном порядке. Усредненное у Д. Кнута определено в виде , при этом =0,577216… (константа Эйлера).

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

1.3 Сортировка простым обменом

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

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

procedure bubblesort:

var i,j: index;

x : item;

begin

for i:=1 to n do begin

for j:=n downto i do

if a[j - 1].key > a[j].key then begin

x:=a[j - 1];

a[j - 1]:=а[j];

a[j]:=x;

end

end

end; {bubblesort]

Исходные ключи	i = 02	i = 03	i = 04	i = 05	i = 06	i = 07	i =08
045	06	06	06	06	06	06	06
059	045	012	012	012	012	012	012
012	059	045	018	018	018	018	018
042	012	059	045	042	042	042	042
094	042	018	059	045	045	045	045
018	094	042	042	059	059	059	059
006	018	094	067	067	067	067	067
067	067	067	094	094	094	094	094

Данный алгоритм нетрудно оптимизировать. Данный пример демонстрирует, что три последних прохода никоим образом не оказывают влияния на распорядок элементов, так как они уже отсортированы. Простой способ усовершенствовать этот алгоритм в том, что надо запоминать, был ли на этом проходе какой-нибудь обмен. В случае отрицательного ответа, это значит, что алгоритм может закрыть процесс. Эту процедуру улучшения возможно продолжить, в случае запоминания не только самого факта обмена, но и места (индекса) последнего обмена. Очевидно, что все пары соседcтвующих элементов имеют индексы, которые меньше данного индекса k, уже находятся в необходимом порядке. Соответственно последующие переходы можно окончить на данном индексе, чем двигаться до определенного ранее нижнего уровня i. Тем не менее, если внимательней посмотреть, то тогда возможно отметить необычную асимметрию: один не там, где нужно находящийся «пузырек» в «тяжелом» краю отсортированного массива всплывет на нужное место за один переход, а не там, где нужно, находящийся «пузырек» в «легком» краю опускается на нужное место всего лишь на один шаг на каждом переходе.

К примеру, массив

1218424455679406

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

9406121842445567

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

I=2	3	3	4	4
R=8	8	7	7	4
44	06	06	06	06
55	44	44	12	12
12	55	12	44	18
42	12	42	18	42
94	42	55	42	44
18	94	18	55	55
06	18	67	67	67
67	67	94	94	94

procedure shakersort;

var j,k,l,r : integer;

x: item;

begin

l := 2; r := n; k:= n;

repeat

for j:=r downto l do

if a[j - 1].key > a[j].key then begin

x := a[j - 1];

a[j-1] := a[j];

a[j] := x;

k := j;

end;

l := k + 1;

for j := l to r do

if a[j - 1].key > a[j].key then begin

x := а[j - 1];

a[j - 1] := a[j];

a[j] := x;

k:=j;

end ;

r := k - 1;

until l > r;

end; {shakersort}

Анализ сортировки методом пузырька и шейкер-сортировки. Число сравнений в алгоритме простого обмена равняется , наименьшее, усредненное и наибольшее значения переброски ( присваивание элементов) равняется

Анализ усовершенствованных методов, таких как метод шейкер-сортировка, довольно сложен. Наименьшее количество сравнений равно . Для улучшенного метода пузырька Д. Кнут выявил, что усредненное число переходов пропорционально и среднее значение сравнений прямо пропорционально . Однако видно, что все предлагаемые до того улучшения никак не оказывают влияния на количество обменов; они только сокращают число лишних повторных проверок. Жаль, но операция взаимообмена двух элементов - часто намного дороже стоит, чем сравнение ключей, соответственно все наши улучшения приводят к значительно меньшему эффекту, чем ожидалось.

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

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

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

Небольшое улучшение сортировки простыми вставками сделано Д.Л. Шеллом ещё в 1959году. Данный метод рассмотрим с помощью примера с восьмью элементами (рис. 4.1).



Рис.4.1. Сортировка по методу Шелла

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

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

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

Поэтому, программа формируется независимо от конкретной последовательности приращений. Все t приращений условно обозначиваются как с условиями .

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

Понятно, что всякая h-сортировке нужен собственный барьер, и что программе нужно определить его место, как можно проще. Соответственно в массив a нужно включить не одну компоненту, а [0], a компонент, так что теперь его можно описать как

а: array [-.. n] of item;

Вот как выглядит алгоритм сортировки Шелла для t = 4.

procedure shellsort;

const t = 4;

var i,j,k,s: index;

x: item;

m: 1..t;

h: array [1..t] of integer;

begin

h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1;

for m := 1 to t do begin

k := h[m];

s := - k; {место барьера}

for i := k + 1 to n do begin

x := a[i]; j := i-k;

if s=0 then s := - k;

s := s + 1; a[s] := x;

while x .key < a[j] .key do begin

a[j+k] := a[j]; j := j-k

end ;

a[j+k] := x;

end

end

end;

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

В случае, когда k-рассортированная последовательность i-сортируется, тогда она по прежнему будет k-рассортированной.

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

1, 4, 13, 40, 121, ...,

где и .

Им тоже была рекомендована следующая последовательность

1, 3, 7, 15, 31, ...,

где и .

В дальнейшем анализ указывает, что в последнем случае издержки, требуемые для сортировки n элементов при помощи алгоритма сортировки Шелла, прямо пропорциональны n^6/5. Это намного лучше по сравнению с n².

2. Алгоритмы поиска

2.1 Последовательный поиск

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

Алгоритм SequentialSearch2 (А[0..n], К)

// Алгоритм выполняет последовательный поиск с применением

// ключа поиска в роли ограничителя

// Исходные данные: Массив А из n элементов и ключ поиска К

// Выходные данные: Позиция первого элемента массива A[0..n - 1],

// значение у которого такое же, как и с К; если элемент не обнаружен,

// возвращается значение -1

А[п] = К

i = 0

while А[i] K

i = i + 1

if i < п

return i

else

return -1

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

2.2 Бинарный поиск

Бинарный поиск - это в высшей мере эффективный алгоритм, применяемый с целью поиска в отсортированном массиве. Этот алгоритм работает методом сравнения нужного ключа К со средним элементом массива А[m]. В случае равенства, алгоритм завершает поиск. В обратном случае эта же операция рекурсивно повторяется для начальной половины массива, если К < А[m], и для второй половины, если К > А [m].

Например, найдем ключ К = 70, применяя алгоритм бинарного поиска к массиву. Пример представлен на рисунке 2.6

Рис. 2.6 Пример бинарного поиска

Хоть понятно, что бинарный поиск применяется на рекурсии, тем не менее он легко реализуется в качестве нерекурсивного алгоритма. Далее представлен псевдокод нерекурсивной версии

Алгоритм Binary Search (А[0..п - 1], К)

// Выполняет нерекурсивный бинарный поиск

// Исходные данные: Массив А[0..п - 1], отсортированный

// в возрастающем порядке, и нужный искомый ключ К

// Выходные данные: Индекс элемента массива, равного К,

// или -1, если подобный элемента отсутствует

l = 0;

r = n - 1

while l r do

т = ;

if К = А[т]

return m

else if К < А[т]

r = m - 1

else

r = m + 1

return -1

Обычный метод анализа эффективности бинарного поиска представляет собой вычисление количества сравнений нужного ключа с элементами массива. Также, для простоты, предположим, что применяются тройные сравнения, т.е. что каждое сравнение К и А[m] дает возможность определить, равно значению А[m]. меньше ли К или больше.

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

К примеру, нужно будет максимум 10 тройных сравнений для поиска элемента с данным значением (или определения того, что нужного элемента нет) в массиве из 1000 элементов, и максимум 20 сравнений для поиска в массиве в миллион элементов.

2.3 Поиск подстроки

Формулирование задачи поиска подстроки: задана символьная строка длиной n, которую называют текстом, и строка длиной т (т n), называемая шаблоном (pattern); нужно обнаружить в тексте подстроку, которая соответствует шаблону. Иначе говоря, необходимо найти i - индекс самого левого символа первой подходящей шаблону подстроки в тексте.

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

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

Алгоритм BruteForceStriny Match (Т[0..п - 1], Р[0..т - 1])

// Алгоритм выполняет поиск подстроки методом грубой силы

// Исходные данные: массив Т[0..п - 1] из n символов, составляющий

// текст; массив P[0..m - 1] из т символов, составляющий шаблон

// Выходные данные: позиция начального символа в тексте, с которой

// начинается начальная искомая подстрока, соответствующая шаблону;

// если подстрока не обнаружена, возвращается - 1

for i = 0 to п - т do

j = 0

while j < т and P[j] = Т[i + j] do

j = j + 1

if j = m

return i

return - 1

Работа алгоритма продемонстрирована на рис. 2.7.

Рис. 2.7. Пример поиска подстроки с применением грубой силы

Нужно обратить внимание, что в указанном примере алгоритм обычно всегда перемещает шаблон по результатам первого же сравнения символов. И всё же самый худший вариант более неприятен: алгоритм может исполнять все m сравнений перед перемещением шаблона, и это случается при каждой из n - m + 1 попыток. Но в случае типового поиска слова в тексте на обычном естественном языке возможно, что множество сдвигов будет исполняться после малого числа сравнений (смотрите на указанный пример). Значит, эффективность в среднем случае обязана быть намного выше эффективности в худшем варианте.

Заключение

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

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

· сортировка вставкой;

· сортировка простым выбором;

· сортировка простым обменом;

· сортировка Шелла.

Из различных методов поиска были изучены и приведены следующие алгоритмы:

§ последовательный поиск;

§ бинарный поиск;

§ поиск подстроки методом грубой силы.

В результате исследования каждого алгоритма были показаны:

ь основная идея алгоритм;

ь суть алгоритма;

ь приведен псевдокод алгоритма;

ь приведен пример функционирования алгоритма.

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

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

1. Левитин Ананий. Алгоритмы: введение в разработку и анализ.: Перевод с английского-Москваав: Издат. дом «Вильямс», 2006год - 576стр.: илюстр.

2. Гудман С., Хидетними С. Введение в разработку и анализ алгоритмов- Москва: Издательство Мир, 1981 год.

3.Ахо А.,Хлокрофт Дж., Ульманн Дж. Разработка и анализ вычислительных алгоритмов - Москва: Издательство Мир-1974год.

4. Ахо A.B., Хлокрофт Дж.., Ульмман Дд. Структура данных и алгоритмы-Москва: Издательство «Вильямс», 2000год . 384стр.

5. Цейтлин Г.Е. Введение в алгоритмы. Киев: Издательство «Сфера», 1998год. 473стр.

6. Кнут Д. «Искусство программирования» для ЭВМ. Том. 1. Основные алгоритмы. - Москва.: Изд-во «Мир», 1976год.

7. Кнут Д. «Искусство программирования для ЭВМ.» Том 3. Сортировка и поиск.-Москва: Изд-во «Мир», 1978год.

8. Вирт Н. «Алгоритмы и структуры данных» Москва: Изд-во «Мир», 1989год . - 360стр.

9. Лорин Г. «Сортировка и системы сортировки.» Москва: Изд-во «Наука», 1983год. - 384стр.

10. Цейтлин Г.Е. «Алгоритмы адаптивной сортировки и их классификация». // Проблемы управления и информатики 1995год , № 3. С. 95-103.

11. Макконнелл Дж. «Анализ алгоритмов. Вводный курс». Москва: Изд-во «Техносфера», 2002год.-304стр.

13. Павловская Т.А. «Паскаль. Программирование на языке высокого уровня: Учебник для вузов». - Санкт-Петербург.: Изд-во «Питер», 2007год. - 393стр.

14. М.В. Сухарев «Основы Delphi. Профессиональный подход». - СПб.: Изд-во «Наука и Техника», 2004год. 600c.

15. Н.Б. Культин «Программирование в Turbo Pascal 7.0 и Delphi» - СПб.: BHV - Санкт-Петербург 1998год - 240с.

16. Грызлов В.И., Грызлова Т.П. «Турбо Паскаль 7.0»- Москва.: ДМК, 1998год - 400с.

17. Ж.Джонс, К.Жарроу «Решение задач в системе TurboPascal». - Москва, Финансы и статистика 1991год - 714с.

18. Delphi 5. «Руководство программиста». - Москва: «Нолидж», 2001год. - 880стр

19. Архангельский А. Я. «Delphi 7. Справочное пособие»,- Москва: ЗАО «Издательство БИНОМ», 2003 год.

20. Культин Н. Б. «Delphi 6 Программирование на Object Pascal»- Санкт-Петербург 2001год - 528с : ил.

21. Архангельский А. Я. «Приемы программирования в Delph. Версии 5-7.»-Москва: ЗАО «Издательство БИНОМ», 2003год.

22. Фленов М. Е. «Библия Delphi» - Санкт-Петербург.: БХВ-Петербург, 2004год. - 880стр.:

23. Гринзоу Лу. «Философия программирования для Windows 95/NT». Перевод с английского - Санкт-Петебург.: Символ-плюс, 1997год . - 640стр.

24 Тейксейра C, Пачеко К «Borland Delphi 6. Руководство разработчика» : Перевод с английского -- Москва: Изд-й дом «Вильямс», 2002год -- 1120 стр.

Размещено на Allbest.ru

...