Главная » Файлы » Курсовые работы [ Добавить материал ]

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

06.04.2014, 16:49

Введение

 
Говорят, и это подтверждается многочисленными примерами, что 90 % времени работы программы приходится на так называемые узкие места, занимающие в общем объеме программы не более 10 % команд. Поиск таких мест и улучшение их временных характеристик – один из основных методов совершенствования программ. К числу таких узких мест относятся фрагменты программ, занимающиеся упорядочением достаточно объемной информации (сортировкой) , поиском данных в больших массивах.
Задача сортировки заключается в перераспределении записей последовательности таким образом, чтобы ключи записей составляли неубывающую (или невозрастающую) последовательность. Методы сортировки делятся на внутренние и внешние. Методы внутренней сортировки выполняются в оперативной памяти. При внешней сортировке информация упорядочивается с использованием дисковой памяти. Во всех внешних сортировках используется методы внутренней сортировки, так как фрагменты последовательности данных считываются с диска в оперативную память и сортируются в ней одним из методов внутренней сортировки.
Методы сортировки делятся на следующие основные группы:
  • сортировка выбором;
  • сортировка вставками;
  • обменная сортировка;
  • распределяющая сортировка;
  • сортировка подсчетом;
  • сортировка слиянием;
  • «карманная» сортировка.
Поиск является наиболее «время емкой» частью многих программ, и замена плохого метода поиска хорошим может значительно увеличить скорость программы.
Методы поиска могут быть классифицированы несколькими способами. Мы можем разделить их на внутренний и внешний поиск. Возможно деление на статические и динамические методы поиска, где термин «статический» означает, что содержимое таблицы остается неизменным и главная задача – уменьшить время поиска без учета времени, необходимого для настройки таблицы. Термин «динамический» означает, что таблица часто изменяется путем вставки (а возможно и удаления) элементов. Третья возможная схема классификации методов поиска – их разделение в зависимости от того, на чем они основаны: на сравнении ключей или на некоторых числовых свойствах ключей (по аналогии с разделением на сортировку методом сравнения и сортировку методом распределения).
Поиск и сортировка зачастую тесно связаны между собой. Сортировка данных выполняется для того, чтобы обеспечить эффективный поиск необходимой информации среди упорядоченных данных. По упорядоченности данных, среди которых выполняется поиск, методы делятся:
  • на методы поиска в неупорядоченных последовательностях данных (последовательный поиск, быстрый последовательный поиск, последовательный поиск в самоорганизующемся массиве)
  • на методы поиска в упорядоченных последовательностях данных (бинарный поиск, однородный бинарный поиск, фибоначчиев поиск, поиск со вставкой по дереву, цифровой поиск со вставкой по дереву, поиск по бору).
Цель данной работы – разработать программы сортировки простыми вставками и последовательного поиска, проанализировать алгоритм этих методов.
 
 
 
  1. Сортировка простыми вставками
 
  1. Описание метода 
 
Пусть в массиве 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.


Не нашел, что искал?  Заказать работу здесь
 
Категория: Курсовые работы | Добавил: admin | Теги: Тестовый пример, Последовательный поиск, Сортировка простыми вставками
Просмотров: 675 | Загрузок: 2