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

Поиск в зависимости от вида обрабатываемых данных делиться на внутренний - поиск в оперативной памяти (поиск в последовательности) и внешний – поиск на внешней памяти.[12, c. 288]
В курсовой работе будут рассмотрены распространенные методы внутреннего поиска.
Основными способами поиска в таблице являются.
Последовательный поиск. Эффективность поиска (среднее число обращений к таблице для нахождения искомой строки) равна n/2.
Логарифмический поиск (бинарный, с помощью двоичного дерева). Число обращений к таблице равно log(n).
Последовательный поиск
Последовательный или как его еще называют линейный поиск, является самым простым видом поиска, не требует сортировки значений множества, дополнительной памяти и это его основные достоинства. Сложность алгоритма последовательного поиска в среднем равна проверке n/2 элементов. Может так получиться, что проверить надо будет только один элемент, но в худшем варианте необходимо будет проверить все n элементов. В случае не отсортированных исходных данных, последовательный поиск является единственным возможным методом поиска. Недостатком данного вида является то, что его целесообразно использовать, если последовательность не слишком велика.
Основная идея метода состоит в том, чтобы последовательно в цикле просматривать элементы последовательности до момента обнаружения искомого элемента или до достижения конца последовательности с отрицательным результатом поиска.
Например, если имеет место последовательность 1 2 3 4 5 и надо найти элемент со значением 4, то будет выполнено три шага в цикле и три раза будет выполнена проверка на равенство искомому элементу.
Пример реализации алгоритма в коде [7,10,11,14]:
function SeqSearch(item: DataArray; count:integer; key:DataItem):integer;
var
t:integer;
begin
t:=1;
while (key<>item[t]) and (t<=count) t:=t+1;
if t>count then SeqSearch:=0
else SeqSearch:=t;
end; { конец последовательного поиска }


Двоичный поиск
Двоичный поиск, применяется только, если элементы массива отсортированы по возрастанию или убыванию. Основная идея алгоритма заключается в неоднократном делении исходной отсортированной последовательности на две части поиска искомого элемента в одной из этих частей, работа алгоритма завершается, когда элемент делящий последовательность совпадет с искомым или при отрицательном результате поиска.
Алгоритм метода сортировки можно записать по шагам следующим образом:
Определяется центральный элемент исходной отсортированной последовательности, этот элемент сравнивается с искомым если имеет место совпадение, то поиск завершен, если центральный элемент не равен искомому, если искомое значение меньше центрального поиск продолжается в левой части последовательности (при условии что последовательность отсортирована по возрастанию) в противном случае наоборот поиск продолжается в правой части последовательности. Далее выбранная часть делиться центральным элементом и цикл повторяется до тех пор, пока не будет найден искомый элемент или будут просмотрены все элементы и будут отрицательный результат поиска – искомый элемент не найден.
Если в последовательности имеется несколько элементов со значениями, равными искомому. Алгоритм находит первый равный искомому элементу, который в порядке следования в последовательности может быть ни первым и ни последним.
При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.
Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел 1 2 3 4 5. Здесь средним элементом является 3. Это значение меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел 4 5. На следующем шаге нужный элемент будет найден.
Пример реализации алгоритма в коде[7,10,11,14]:
function BSearch (item: DataArray; count:integer; key:DataItem):integer;
var
low, high, mid: integer;
found:boolean;
begin
low:=1; high:=count;
found:=false; { не найден }
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if key else if key>item[mid] then low:=mid+1
else found:=true; { найден }
end;
if found then BSearch:=mid
else BSearch:=0; { не найден }
end; { конец поиска }


ЗАКЛЮЧЕНИЕ
Произведено знакомство с различными информационными источниками по сортировке и поиску информации. Как уже отмечалось во введении тема сортировки и поиска информации очень емкая и объем информации очень велик. Большинство книг по программированию включают главу посвященную алгоритмам сортировки и поиска данных.
При выполнении курсовой работы удалось рассмотреть и проанализировать лишь небольшую часть основных алгоритмов поиска и сортировки данных, рассмотрены некоторые простые прямые и сложные или как их еще называют усовершенствованные алгоритмы внутренней сортировки массивов. Представлены их алгоритмы в словесном описании, в виде программ и схем.
Обзор литературы по данной тематики позволил сформировать основные особенности каждого алгоритма, привести схемы работы алгоритмов. Книги по программированию и интернет ресурсы позволили привести примеры программного кода реализации алгоритмов на языке Паскаль. Каждый алгоритм (работа алгоритма) рассмотрена на конкретном примере для конкретного исходного массива и последовательного преобразования по шагам этого массива в отсортированную последовательность. Описанию алгоритмов посвящено две главы работы, в которых описывается три простых метода сортировки и три усовершенствованных метода.
Совокупная информация по алгоритмам позволила провести анализ этих методов на предмет оценки эффективности в зависимости от поставленной задачи.
Для анализа алгоритмов, прежде всего, были определены параметры, характеризующие основные показатели алгоритмов. Определено пять основных свойств алгоритмов по которым алгоритмы можно сравнивать. Данному разбору посвящена глава Анализ алгоритмов сортировки. Можно сделать заключение методы сложных сортировок, эффективнее, чем алгоритмы простых сортировок. В простых методах сортировки массивов время процесса сортировки пропорционально n2 в сложных (n log n). Учитывая не очень хорошую скорость, простые алгоритмы сортировки целесообразно использовать при малых значениях n, при больших значениях более эффективно использовать сложные алгоритмы.
Анализ основных алгоритмов показывает, что наиболее эффективная простая сортировка будет менее эффективна, чем самая не производительная сложная сортировка. В ходе теоретического сравнения были сделаны выводы, что алгоритм сортировки вставок эффективнее алгоритма методом простых перестановок, имеет место меньшее количество сравнений ключей и меньшее число перестановок. В данном разделе приведены сравнительные таблицы с показателем скорости работы алгоритмов.
В работе рассмотрены основные самые распространенные методы поиска. Рассмотрено два способа поиска последовательный и бинарный. Как правило, процессу поиска предшествует процесс упорядочивания данных именно поэтому тема сортировки и поиска рассматриваются в совокупности.
Последовательный поиск является самым простым методом поиска, хотя не самым эффективным. Данный вид поиска очень наглядный и легкий в изучении. В работе продемонстрирована основная идея метода, продемонстрирован программный код реализации метода и конечно метод продемонстрирован на конкретном числовом примере.
Для метода двоичного поиска аналогичным образом приведено словесное описание особенности данного вида поиска, приведен программный код реализации алгоритма на языке Паскаль и продемонстрирован пример реализации на конкретных числовых значениях.
Выявлены достоинства и недостатки каждого из методов для чего сначала определены основные свойства алгоритмов. Наиболее эффективным методом поиска данных является двоичный поиск, применяется для отсортированных массивов данных, хотя в случае не отсортированной последовательности можно использовать только последовательный метод.
Изучив и проанализировав основные алгоритмы сортировки и поиска данных можно сделать выводы, что на ряду, с уже большим количеством решенных изученных вопросов по данной теме, остается много не решенных и не изученных вопросов, что еще раз доказывает сложность тематики. Алгоритмы будут совершенствоваться, поскольку объем обрабатываемой сейчас информации на ЭВМ очень велик это большие информационные системы, информационные ресурсы, качество которых во многом зависит от скорости (оперативности) поиска нужной информации.
В результате выполнения работы изучен большой объем информации, получены знания по тематике сортировки и поиска информации, что позволит в дальнейшем применять эти знания на практике. Выполнение работы было полезным и интересным.
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы / Пер. с англ. – М.: Вильямс, 2001.- 384 с.
Вирт Н. Алгоритмы и структуры данных. - 2-е изд. - СПб: “Невский Диалект”, 2001. - 352 с.
Голицина О.Л., Попов И.И. Основы алгоритмизации и программирования: Учебное пособие. - 2-е изд. - М.: ФОРУМ: ИНФРА-М, 2006. - 432 с.
Клиффорд Ш. Алгоритмы: построение и анализ. - 2-е изд.: Пер. с англ. - М.: «Вильямс», 2005. - 1296 с.
Кнут Д. Искусство программирования, том 3. Сортировка и поиск. - М.: «Вильямс», 2007. - 824 с.
Колдаев В.Д. Основы алгоритмизации и программирования: Учебное пособие / Под ред. проф. Л.Г. Гагариной. - М.: ИД "ФОРУМ": ИНФРА-М, 2006. - 416 с.
Красиков И.В. Алгоритмы. Просто как дважды два. – М.: Эксмо, 2007.- 256 с.
Левитин, Ананий В. Алгоритмы: введение в разработку и анализ. - М.: «Вильямс», 2006. - 576 с.
Макконнел Дж. Анализ алгоритмов. Вводный курс.: Пер. с англ. – М.: Техносфера, 2002.- 304 с.
Немнюгин С. А Turbo Pascal - СПб: Издательство «Питер», 2000. - 496 с.
Павловская Т. А. Паскаль. Программирование на языке высокого уровня. – СПб.: Питер, 2007. - 393 с.
Программирование и основы алгоритмизации: Учеб. пособие / В.Г. Давыдов. - 2-е изд., стер. - М.: Высш. шк., 2005. - 447 с.
Скиена С. Алгоритмы. Руководство по разработке. - 2-е изд.: Пер. с англ. - СПб.: «БХВ-Петербург», 2011. - 720 с.
Стивене Р. Delphi. Готовые алгоритмы. - 2-е изд., стер.: Пер. с англ. Мерещука П. А. - М.: ДМК Пресс ; - СПб.: Питер, 2004. - 384 с.
Томас Ниман Сортировка и поиск: Рецептурный справочник Пер. с англ. П.Н.Дубнер - М.: ДМК Пресс, 1998. - 59 с
Андреева Т. А. Лекция №4.2: Сортировки массивов – 2008 URL: http://pascal.toom.su/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D0%B8 (дата обращения: 22.02.2012).
Быстрицкий В.Д. Сравнение алгоритмов сортировки массивов.// ALGLIB [Электронный ресурс]. URL: http://alglib.sources.ru/articles/sort.php (дата обращения: 22.02.2012).
Кантор Илья Алгоритмы сортировки – 2000 URL: http://algolist.manual.ru/sort/index.php (дата обращения: 22.02.2012).
Okcode – 2010. – 29 сентября [Электронный ресурс]. URL: http://okcode.ru/practicum-po-massivam/ (дата обращения: 22.02.2012).
Сундукова Т.О., Ваныкина Г.В. Структуры и алгоритмы компьютерной обработки данных.// Интернет-Университет Информационных Технологий – 2011. – 2 февраля [Электронный ресурс]. URL: http://www.intuit.ru/department/algorithms/staldata/42/ (дата обращения: 22.02.2012).












9



max

max

n-1

n-2

n-1

0

0

arr

arr

i=1,2,…,n-1

arr

Вставка на подходящее место или остается на месте

0

n-1

i-1

i

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

1

Внутренняя сортировка

Внешняя сортировка

Простые методы

Модифицированные методы

Метод простого обмена

Простые методы

Простые методы



Сортировка с разделение (быстрая сортировка)

Сортировка Флойда (с помощью дерева)

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