Постановка задач

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

1. 
   Установить начальные значения переменой m=0 {количество перестановок};
   
2. 
   Для i=1 до n, для j=1 до 5 выполнять;
   
3. 
   Расстоянию b1 присваиваем b, а значениям I, k присваиваем 1, 0 соответсвенно;
   
4. 
   Если b[i,3]<>0, тогда:
   
   1. 
      i присваиваем b[i,3;
      
5. 
   Увеличить количество перестановок на 1, m: = m+1;
   
   1. 
      Для i1:=1 до n выполнять A [i1]:=b1 [i1,1];
      
   2. 
      Увеличить k на 1, k:=k+1;
      
   3. 
      Присваиваем b1[k,1]:=b[i,1] и b1[k,2]:=b[i,2];
      
   4. 
      Если b[i,4]<>0, тогда i присваиваем b[i,4];
      
6. 
   Увеличить количество перестановок на 1, m: = m+1;
   
   1. 
      Для i1:=1 до n выполнять A [i1]:=b1 [i1,1];
      
   2. 
      Присваиваем j:=i и i:=b[i,5];
      
   3. 
      Если i<>0 и если b[i,1]> b[j,1], тогда goto l2 else goto l3;
      
   4. 
      Увеличить количество перестановок на 1, m: = m+1;
      
   5. 
      Для i1:=1 до n выполнять A [i1]:=b1 [i1,1];
      

4 Руководство по пользованию программой

• 
  На окне вывода появится сообщение «Исходный массив» и будет распечатан неупорядоченный массив А;
  
• 
  На окне вывода появится сообщение «Отсортированный методом пузырька:». После будет распечатан упорядоченный массив, полученный методом пузырька;
  
• 
  На окне вывод появится сообщение «Отсортированный методом дерева:». После будет распечатан упорядоченный массив, полученный методом дерева;
  
• 
  На окне вывода появится сообщения «Линейный поиск элемента» и «Введите элемент, который хотите найти -». После информация об искомом элементе.
  
• 
  На окне вывод появится сообщение «Для завершения поиска введите слово "end", иначе нажмите "enter"»;
  
• 
  На окне вывода появится сообщения «Двоичный поиск элемента» и «Введите элемент, который хотите найти -». После информация об искомом элементе.
  
• 
  На окне вывод появится сообщение «Для завершения поиска введите слово "end", иначе нажмите "enter"»;
  

4.2 Руководство программиста

1. 
   Процедура form – предназначена для формирования элементов массива с помощью ввода с клавиатуры. Вызов процедуры имеет следующий вид: form(A,n), где А – исходный массив, n – количество элементов.
   
2. 
   Процедура form_random – предназначена для формирования элементов массива, задавая значение каждого элемента результатом случайной функции Random(R). Вызов процедуры имеет следующий вид: form_random(A,n), где А – исходный массив, n – количество элементов.
   
3. 
   Процедура print – предназначена для печати элементов массива на каждую строку по 5 элементов, если количество элементов массива меньше 20, иначе по 10 элементов. Вызов процедуры осуществляется следующим образом: print(A), где А – исходный массив.
   
4. 
   Процедура linei – предназначена для линейного поиска искомого элемента. Вызов процедуры осуществляется следующим образом: linei(A,x), где А – исходный массив,x- элемент для поиска.
   
5. 
   Процедура binar_search – предназначена для двоичного поиска искомого элемента. Вызов процедуры осуществляется следующим образом: binar_search (A,x), где А – исходный массив, x- элемент для поиска.
   
6. 
   Процедура обменная сортировка – предназначена, чтобы привести массив к упорядоченному виду методом Шелла. Вызов процедуры осуществляется следующим образом: Shella (T,K,KP), где T – исходный массив, 1,n – индексы массива, h- количество перестановок при поиске.
   
7. 
   Процедура Tree_Sort – предназначена, чтобы привести массив к упорядоченному виду сортировкой методом дерева. Вызов процедуры осуществляется следующим образом: Tree_Sort (a, n, b), где a – исходный массив, m – количество перестановок при поиске.
   

5 Анализ результатов

Таблица 2. Среднее время линейного поиска (теоретическое)

По данным, представленным в таблицах 1 и 2,построен график зависимости времени поиска от числа элементов в массиве (рис. 4).

Таблица 4. Среднее время двоичного поиска (теоретическое)

По данным, представленные в таблицах 3 и 4 нарисуем график зависимости времени поиска от числа элементов в массиве (рис. 5).

Таблица 6 Среднее время сортировки деревом

По данным, представленным в таблицах 5 и 6,построен график зависимости времени поиска от числа элементов в массиве (рис. 6).

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

Таблица 7 Среднее время сортировки методом дерева (практическое)

Таблица 8 Среднее время обменной сортировки методом дерева (теоретическое)

По данным, представленным в таблицах 7 и 8,построен график зависимости времени поиска от числа элементов в массиве:

Рисунок 7 – График метода обменной сортировки с разделением

В ходе курсового проектирования выполнено следующее:

• 
  Разработаны алгоритмы сортировок (Шелла и деревом) и поисков (линейного и двоичного)
  
• 
  Выполнена реализация разработанных алгоритмов в среде ABCPascal
  
• 
  Разработаны руководства пользователя и программиста
  
• 
  Разработаны схемы алгоритмов
  
• 
  Выполнены тестирование и отладка программы для одномерного целочисленного массива с числом элементов N=16,128,512,1024.
  
• 
  Выполнен анализ результата работыпрограммы (оценена эффективность программы в зависимости от объема обрабатываемых данных)
  
• 
  Построены графики зависимости времени от количества элементов сортировок и поисков
  
• 
  Проведенный анализ показал, что при поиске для малых N нужно использовать линейный поиск, а для больших N – двоичный.
  
• 
  В ходе исследования было выявлено, что сортировка методом дерева является более эффективной, чем метод Шелла, однако занимает больше памяти.
  

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