Главная » Файлы » Курсовые работы | [ Добавить материал ] |
Сортировка простыми вставками и последовательный поиск
06.04.2014, 16:49 | |
ВведениеГоворят, и это подтверждается многочисленными примерами, что 90 % времени работы программы приходится на так называемые узкие места, занимающие в общем объеме программы не более 10 % команд. Поиск таких мест и улучшение их временных характеристик – один из основных методов совершенствования программ. К числу таких узких мест относятся фрагменты программ, занимающиеся упорядочением достаточно объемной информации (сортировкой) , поиском данных в больших массивах. Задача сортировки заключается в перераспределении записей последовательности таким образом, чтобы ключи записей составляли неубывающую (или невозрастающую) последовательность. Методы сортировки делятся на внутренние и внешние. Методы внутренней сортировки выполняются в оперативной памяти. При внешней сортировке информация упорядочивается с использованием дисковой памяти. Во всех внешних сортировках используется методы внутренней сортировки, так как фрагменты последовательности данных считываются с диска в оперативную память и сортируются в ней одним из методов внутренней сортировки. Методы сортировки делятся на следующие основные группы:
Методы поиска могут быть классифицированы несколькими способами. Мы можем разделить их на внутренний и внешний поиск. Возможно деление на статические и динамические методы поиска, где термин «статический» означает, что содержимое таблицы остается неизменным и главная задача – уменьшить время поиска без учета времени, необходимого для настройки таблицы. Термин «динамический» означает, что таблица часто изменяется путем вставки (а возможно и удаления) элементов. Третья возможная схема классификации методов поиска – их разделение в зависимости от того, на чем они основаны: на сравнении ключей или на некоторых числовых свойствах ключей (по аналогии с разделением на сортировку методом сравнения и сортировку методом распределения). Поиск и сортировка зачастую тесно связаны между собой. Сортировка данных выполняется для того, чтобы обеспечить эффективный поиск необходимой информации среди упорядоченных данных. По упорядоченности данных, среди которых выполняется поиск, методы делятся:
Пусть в массиве X из N элементов упорядочены по возрастанию первые К элементов (К>=1). Возьмем элемент с номером К+1 и, сравнивая его по очереди со всеми элементами с К-го до 1-го, определяем, в какую позицию i его надо вставить, чтобы выполнилось условие 1<= i <= k. В процессе сравнения элементы с К-го до i-го сдвигаются вправо на одну позицию. Затем выбирается элемент с номером К+2 и вставляется среди элементов с (К+1)-го по 1-й и т.д. до конца массива. program insert1; uses crt; const MAX=20; type xarr=array [0..MAX-1] of integer; var x:xarr; i:integer; procedure insert(var x:array of integer;n:integer); var i,k,tmp:integer; begin for i:=1 to n-1 do begin tmp:=x[i]; k:=i-1; while (k>=0) and (tmp<x[k]) do begin x[k+1]:=x[k]; k:=k-1; end; x[k+1]:=tmp; end; end; begin clrscr; writeln('До сортировки - '); for i:=0 to MAX-1 do begin x[i]:=random(MAX); write(x[i],' '); end; writeln; insert(x,MAX); writeln('После сортировки - '); for i:=0 to MAX-1 do write(x[i],' '); readln; end. Не нашел, что искал? Заказать работу здесь | |
Категория: Курсовые работы | | | |
Просмотров: 675 | Загрузок: 2 |