Министерство образования и науки Российской Федерации
ФГБОУ ВПО «Нижегородский государственный университет им. »
Факультет вычислительной математики и кибернетики.
Кафедра математического обеспечения ЭВМ.
Скачано с http://vmk. /
Содержание:
1) Введение
2) Постановка учебно-практической задачи
3) Руководство пользователя
4) Руководство программиста
А) Описание алгоритмов
- Работы программы. Сортировки массива и поиска элемента в нём в общем виде Алгоритмов поиска элемента в массиве Алгоритмов сортировки массива
Б) Описание структур данных
В) Описание программного комплекса
5) Заключение
6) Литература
7)Приложение : перевод диалогов
8)Приложение : код программы
Введение.
Целью лабораторной работы является написание программы, способной осуществлять сортировку в случайно сформированном массиве различными методами и поиск в нём нужных элементов.
После решения написать программу встаёт вопрос: какой язык для этого выбрать? Пусть будет Паскаль: его знают все, а кто не знает, те поймут и так, поскольку Паскаль создавался именно с целью обучения. С другой стороны, не являясь языком, часто используемым при разработке ПО (как, например, C++ и Java), его код в дальнейшем будет, в принципе, бесполезен. Поэтому каждый алгоритм будет сопровождать подробное теоретическое пояснение, чтобы его можно было переписать на другой язык программирования с минимальными временными затратами.
Для дальнейшей работы следует понять, что же за зверь такой эта «сортировка».
Определим понятие "сортировка" как упорядочение элементов некоторой последовательности (например, массива) в определённом (например, возрастающем или убывающем) порядке.
Для чего нужна сортировка? Думаю, уже очевидно, что сортировка нужна для создания некого порядка среди данных. Искать что-либо становится гораздо удобнее, если мы знаем, где это искать, т. е. порядок расположения. Итак, причина использование сортировки - создание удобных условий для быстрого поиска данных.
Следующая задача является классической: "Сколько в массиве находиться одинаковых элементов каждого типа?" Допустим, что у нас есть массив анкет о сотрудниках организации и нам надо найти их распределение возрастов (сколько человек имеют 30, 50, 60 лет). Эту задачу легко решить, если отсортировать анкеты по возрасту сотрудников, и затем пройтись по массиву, подсчитывая количество сотрудников с каждым возрастом.
Другой пример: требуется определить все общие элементы двух массивов. Если отсортировать каждый массив в одном и том же порядке, то за один проход по ним мы получаем искомый ответ.
Таким образом, сортировка массива является одной из наиважнейших базовых задач в программировании, алгоритм которой использует в своей деятельности любой пользователь компьютера, работая с файловым менеджером и большинством прикладных и офисных программ.
В нашей программе будут рассматриваться такие алгоритмы сортировок, как: вставками, пузырьком и линейная.
За «поиск» обозначим нахождение какого-то элемента в массиве и вывод его местоположения пользователю.
Постановка учебно-практических задач.
Постановка задачи:
Массивом будем называть ряд (последовательность, набор) величин одного типа (например, real, integer или char), расположенных в памяти непосредственно друг за другом, и имеющих одно имя (один идентификатор).
Наш массив может содержать до 10 000 элементов.
Нужно составить программу, которая:
Обеспечивает заполнение массива числовыми значениями. Используя алгоритмы, могла бы осуществлять его сортировку и поиск в нём определённого элемента. Рассчитывает время работы каждого алгоритма сортировки для каждого данного массива. На основе обработки данных о времени работы, рисует таблицу со временем работы сортировок для обработанного массива.Программа должна:
Выполнять выше перечисленное. Обеспечивать диалог посредством пользовательских экранов; Осуществлять контроль ошибок при вводе (исходных данных на допустимые значения).Руководство пользователя:
Для того, чтобы воспользоваться данной программой вам нужно найти и запустить ярлык LAB_1 с расширением. EXE через файловый менеджер, иначе – открыть с расширением. PAS в любом компиляторе языка Паскаль.
На чёрном фоне перед вами высветились 8 строчек-команд и строка, предлагающая ввести номер желаемого действия.
(Весь диалог с программой совершается на английском языке – перевод на русский будет находиться в приложении)
В случае ввода «1» вам будет предложено ввести количество элементов массива (максимум определён на программном уровне).
Если число больше 20, то вы должны определить возможное самое большое значение в массиве, который будет заполнен рандомными числами, иначе – ввод с клавиатуры.
(В случае выбора команд до задания массива – вам будет предложено его ввести, либо использовать старый).
«2» и «3» отвечают за поиск элемента в массиве: вы вводите какое-либо число и узнаёте, какое место он занимает, либо занимал, если бы находился в массиве.
«4», «5» и «6» сортируют массив различными способами (каждый раз используется неотсортированный массив).
«7» выводит таблицу, в которой сравнивается время выполнения сортировок массива.
«8» завершает программу.
P. S. После ввода массив всегда сохраняется в файл lab_1a. txt, что позволяет использовать «старый» массив после запуска программы и контролировать данные самостоятельно.
Руководство программиста:
Описание алгоритма работы программы:
Диалог с программой происходит через пользовательский интерфейс, где каждая команда имеет свой личный №. В процессе работы программы выводятся сообщения-комментарии о том, что требуется\предлагается сделать пользователю.
Ввод данных (элементов массива) осуществляется в диалоговом режиме. При указании более 20 составляющих массива – он заполняется рандомными числами и сохраняется в файл. Либо, по желанию пользователя, можно использовать старые данные, сохранённые в файле.
Процедуры сортировки, поиска и вывода таблицы активны только если задан массив. В ином случае перед их активацией будет предложено заполнить массив данными.
Вывод таблицы со временем работы подпрограмм сортировок возможен только после использования их всех относительно введённого массива (обеспечивается корректность выводимых данных), либо после отказа пользователя от оного.
Описание общего алгоритма поиска элемента в массиве:
Задача поиска заключается в том, чтобы в массиве с заданным количеством элементов найти номер заданного элемента либо выяснить, что заданного элемента в массиве нет.
Исходные данные:
А – массив целочисленных элементов, N – число элементов в массиве, Val – заданный элемент.
Требуемый результат:
Pos – номер элемента Val в массиве А;
ResultOk – код результата решения задачи (ResultOk = true, если элемент Val в массиве А найден, ResultOk = false, если элемента Val в массиве А нет).
Пример: Пусть N = 5, А = (7, 2, 3, 5, 86). Тогда при заданном Val = 5 результатом будет Pos = 4, ResultOk = true.
Описание общего алгоритма сортировки массива:
Задача сортировки заключается в том, чтобы упорядочить массив с заданным количеством элементов.
Исходные данные:
A – массив целочисленных элементов, N – число элементов в массиве.
Требуемый результат: А – отсортированный массив.
Пример: Пусть N = 7, A = (15, 8, 1, 11, 14, 52, 31). Тогда результатом будет А = (1, 8, 11, 14, 15, 31, 52).
Описание алгоритмов поиска данных:
1) Метод двоичного поиска элемента в отсортированном массиве.
Поиск нужного числа element в отсортированном числовом массиве a[1..n] осуществляется следующим образом. Число element сравнивается с числом, расположенным в середине массива a. В качестве такого числа выбирается элемент, находящийся в позиции i = (n +1) div 2.
Если a[i] < element, то продолжить поиск на сегменте a[i+1..n] и увеличить k_k (показывает, сколько элементов массива стоит перед искомым), если a[i] > element, то на сегменте a[1..i-1]. Если a[i] = element, то искомое число обнаружено в позиции i. Таким образом, если число element присутствует в массиве, то оно будет обнаружено и в качестве ответа переменной search_element присваивается номер позиции, в которой оно находится. В противном случае переменной search_element присваивается число 0, как признак того, что числа element в нашем массиве нет.
Ниже приведена демонстрационная процедура, которая производит поиск числа element в массиве a[1..n]. Если оно присутствует в массиве, то будет напечатано сообщение, в какой позиции оно находится, если числа element в массиве нет, то об этом тоже будет напечатано соответствующее сообщение.
2) Метод линейного поиска элемента в неотсортированном массиве.
Для решения задачи поиска номера search_element заданного элемента element в неупорядоченном массиве a[1..n] Идея алгоритма поиска в неупорядоченном массиве a[1..n] состоит в последовательном сравнивании элементов массива с значением element. Поиск заканчивается при совпадении сравниваемого элемента a[i] с искомым, либо при переборе всех элементов массива. В первом случае элемент element в массиве найден, во втором случае элемента element в массиве нет.
Описание алгоритмов сортировок массивов:
1) Алгоритм пузырьковой сортировки.
Бесхитростный алгоритм сортировки числового массива a[1..n] заключается в последовательном сравнении элемента a[j] со всеми последующими и, при нахождении большего элемента, замене их местами.
При работе алгоритма будет выполнено ровно n (n – 1) / 2 сравнений «a[j] < a[j+1]», а суммарное число перемещений, выполненных в процедуре перемещения, будет не более чем умноженное на 3 указанное число сравнений.
2) Алгоритм линейной сортировки (выбором).
В массиве a[n-1] выбирается наименьший, по сравнению с остальными, элемент (в случае сортировки по возрастанию) и меняется местами с первым. Процесс повторяется с оставшимися элементами на сегменте a[i..n-1]. Вне зависимости от номера текущего шага i, последовательность a[1]..a[i] является упорядоченной. Таким образом, на (n-1)-м шаге весь массив, кроме элемента a[n], оказывается отсортированным, а a[n] стоит на последнем месте, так как все меньшие ушли влево.
3) Алгоритм сортировки вставками.
Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На каждом следующем (i+1)-м шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним.
В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.
Программный комплекс.
Программный комплекс состоит из таких взаимодействующих процедур, как:
процедура Time_start считывает системное время во время запуска какого-либо сортировочного алгоритма. процедура Time_end считывает системное время после окончания сортировки массива и, высчитывая разницу между конечным и начальным, получает в милисекундах время действия процедуры-алгоритма. процедура sort_buble сортирует массив с помощью пузырькового алгоритма. процедура sort_lin реализует сортировку массива линейным алгоритм. процедура sort_insertion сортирует массив с использованием алгоритма вставками. процедура search_binary реализует поиск элемента в массиве по бинарному алгоритму. процедура search_linear реализует поиск элемента в массиве по бинарному алгоритму. процедура tabl рисует на экране таблицу и выводит время сортировки массива каждым запущенным алгоритмом. процедура menu выводит на экран визуальное текстовое меню. процедура check_array служит для быстрой проверки – правильно ли отсортирован массив. процедура message уведомляет пользователя о завершении какого-либо действия и возвращает его в меню.Все процедуры используют внешние параметры.
Структуры данных.
Для хранения чисел в массиве, в соответствии с постановкой задачи, в программе необходимо организовать данную структуру данных:
type massiv=array [1..10000] of integer; { тип элементов и их количество }
Другие типы данных не использовались в виду малого размера программы и, как следует, их ненадобности.
Заключение.
Время работы разных алгоритмов сортировки случайного массива в миллисекундах.(Windows 7, 64 разрядная, процессор Intel(R) Core(TM) i3 CPU, 2.53 GHz)
Кол-во элементов в массиве | Сортировка выбором | Сортировка вставками | Сортировка пузырьком |
N=500 | 0 | 0 | 6 |
N=1000 | 11 | 0 | 11 |
N=1500 | 44 | 17 | 101 |
N=2000 | 110 | 128 | 204 |
N=2500 | 246 | 116 | 313 |
N=3000 | 369 | 160 | 517 |
N=3500 | 303 | 225 | 643 |
N=4000 | 406 | 331 | 834 |
N=4500 | 539 | 410 | 1066 |
N=5000 | 670 | 451 | 1351 |
N=5500 | 835 | 604 | 1858 |
N=6000 | 906 | 708 | 1804 |
N=6500 | 1109 | 841 | 2214 |
N=7000 | 1321 | 923 | 2527 |
N=7500 | 1538 | 1134 | 2725 |
N=8000 | 1708 | 1219 | 3428 |
N=8500 | 2045 | 1363 | 3922 |
N=9000 | 2225 | 1651 | 4234 |
N=9500 | 2528 | 1741 | 7139 |
N=10000 | 2870 | 2078 | 6705 |
Следовательно, самым медленным является алгоритм пузырька, а самым быстрым из трёх – сортировка вставками.
Литература.
, ; , «Методы программирования», Н. Н., 2006. Материалы http://algolist. manual. ru/ и http://a-urusov2011.narod2.ru/Приложение .
To search, the array will first be sorted using a linear algorithm.
Для поиска массив будет сначала отсортирован с помощью линейного алгоритма.
Enter the element that we search:
Введите элемент, который мы ищем:
Element ‘n’ is in the array on the ‘i’-th place!
Элемент ‘n’ в массиве на ‘i’-м месте!
This array is not an element! If he was, would be on the k_k-th place!
Этого элемента нет в массиве! Если бы он был, был бы на ‘k_k’-м месте!
Checking the sort.
Проверка сортировки.
Press any key to continue...
Нажмите любую клавишу, чтобы продолжить...
To perform an action, enter the desired number:
Чтобы выполнить действие, введите нужный номер:
You have not entered an array. You want to use the old array? (y/n)
Вы не ввели массив. Вы хотите использовать старый массив? (Да / Нет)
Enter the number of elements in the array.
Введите количество элементов в массиве.
If you do not want to introduce an element of itself, then the number must be greater than 20.
Если вы не хотите вводить элементы самостоятельно, то число должно быть больше 20.
The array will consist of random numbers.
Введите наибольшее значение среди рандомных чисел.
Enter them the greatest number.
Массив будет состоять из случайных чисел.
An array of 'n' elements is given randomly.
Массив из 'N' элементов задается случайным образом.
Enter the values of the array elements. Введите значения элементов массива.
Not all of the algorithms used. If you want to fix it - press "1", otherwise - press "2".
Не все алгоритмы использованы. Если Вы хотите это исправить - нажмите «1», иначе - нажмите "2".
Activation sort buble! Press any key to continue...
Активирована сортировка пузырьком! Нажмите любую клавишу, чтобы продолжить...
Приложение .
uses CRT, Graph, dos; type massiv=array [1..10000]of integer; { максимальное количество элементов массива} Var i, j,n, value, max, min, register, counter, element, search_element: integer; a, b: massiv; name_file, name_array: string; faile: text; key, key_check, key_table: char; flag, exit, flag_array, check_exit: boolean; time, time_buble, time_lin, time_insert, time_search_lin, time_search_binary: longint; punkt_number, punkt_text: array [1..20] of string; h, m,s, ms, h1,m1,s1,ms1,hour, minute, second, millisecond: word;procedure Time_start; { начинает отсчёт времени работы процедуры } begin Dos. GetTime(h, m,s, ms); end;
procedure Time_end; begin { высчитывает время, переводит в милисеккунды } Dos. GetTime(h1,m1,s1,ms1); if h1>h then hour:=h1-h else hour:=h-h1; if m1>m then minute:=m1-m else minute:=m-m1; if s>s1 then second:=s-s1 else second:=s1-s; if ms>ms1 then millisecond:=ms-ms1 else millisecond:=ms1-ms; time:=millisecond+100*(second+60*(minute+60*hour)); end;
{ Основные процедуры }
procedure sort_buble; { сортировка пузырьком } begin Time_start; for i:=n downto 2 do for j:=1 to i-1 do if a[j]>a[j+1] then begin value:=a[j]; a[j]:=a[j+1]; a[j+1]:=value; end; Time_end; time_buble:=time; end;procedure sort_lin; { линейная сортировка (выбором) } begin Time_start; for i:=1 to n-1 do begin min:=i; for j:=i+1 to n do if a[j] < a[min] then min:=j; value:=a[i]; a[i]:=a[min]; a[min]:=value; end; Time_end; time_lin:=time; end;
procedure sort_insertion; { сортиовка вставками } begin Time_start; for i:=2 to n do if a[i-1] > a[i] then begin value:=a[i]; j:=i-1; while (j > 0)and(a[j] > value) do begin a[j+1]:=a[j]; j:=j-1; end; a[j+1]:=value; end; Time_end; time_insert:=time; end;
procedure search_binary; { бинарный (двоичный) поиск } Var left, right, k_k, place: integer; begin ClrScr; Writeln('To search, the array will first be sorted using a linear algorithm.'); Writeln('Enter the element that we search: '); Readln(element); sort_lin; left:=1; right:=n; k_k:=0; { количество элементов меньших искомого } while left<=right do begin i:=(left+right) div 2; if a[i]=element then break else if a[i]<element then begin left:=i+1; inc(k_k); end else right:=i-1; end; if a[i]=element then Writeln('Element ',element,' is in the array on the ',i,'th place!') else Writeln('This array is not an element! If he was, would be on the ',k_k,'-th place!') end;
procedure search_linear; { линейный поиск } begin ClrScr; Writeln('Enter the element that we search: '); Readln(element); search_element:=0; for i:=1 to n do begin if a[i]=element then begin search_element:=i; break; end; end; if search_element=0 then Writeln('This array is not an element!') else Writeln('Element ',element,' is in the array on the ',search_element,'th place!'); end;
procedure tabl; { рисует таблицу, выводит значения } var x1,x2,y1,y2,GrDriver, grMode, i, y: integer; s_time, s_oper: array [1..5] of string; begin ClrScr; GrDriver:=Detect; InitGraph(GrDriver, grMode,' '); SetColor(4); SetLineStyle(0,0,3); Rectangle(10,50,500,250); Line(300,50,300,250); y1:=50; for i:=1 to 4 do begin Line(10,y1,500,y1); y1:=y1+50; end; { закраска первой строки } SetFillStyle(8,2); FloodFill(55,55,4); SetFillStyle(1,3); FloodFill(305,55,4); y2:=105; { Основные процедуры } for i:=4 to 6 do begin SetFillStyle(1,14); FloodFill(105,y2,4); { первый столбец} SetFillStyle(1,15); FloodFill(305,y2,4); { второй столбец } OutTextXy(13,y2,punkt_text[i]); y2:=y2+50; end; OutTextXy(340,70,'Time(m/s):'); { вывод времени } str(time_buble:6,s_time[3]); str(time_insert:6,s_time[4]); str(time_lin:6,s_time[5]); y:=125; for i:=3 to 5 do begin OutTextXY(355,y, s_time[i]); y:=y+50; end; Readln; CloseGraph; end; { Дополнительные процедуры } procedure menu; begin { считывает пункты меню с файла и выводит их } ClrScr; Assign(faile, name_file); Reset(faile); Readln(faile, counter); { количество пунктов } for i:=1 to counter do begin Readln(faile, punkt_number[i]); Readln(faile, punkt_text[i]); Writeln(punkt_number[i],' ',punkt_text[i]); end; Close(faile); end;
procedure check_array; { проверка сортировки } begin Writeln(' '); Writeln('Checking the sort:'); for i:=1 to n do Write(' ',a[i]); Writeln(''); end;
procedure message; { задержка и зачистка экрана } begin Writeln(''); Writeln('Press any key to continue...'); Readln; menu; end;
{ ОСНОВНОЙ КОД ПРОГРАММЫ } begin ClrScr; name_file:='lab_1.txt'; { файл с меню } name_array:='lab_1a. txt'; { файл с массивом } menu;
repeat
repeat { проверка – является ли число номером пункта } Writeln('To perform an action, enter the desired number:'); Readln(key); until ( (key <=char(‘8’))and(key>=char(‘1’)); a:=b; { запись введённого массива в массив для работы }
{ проверка – введён ли массив } if (key='1')or(key='8')or(flag_array = true) then { ничего } else begin repeat Writeln('You have not entered an array. You want to use the old array? (y/n)'); Readln(key_check); case key_check of 'n': begin key:='1'; check_exit:=true; { переходим к созданию нового массива } end; 'y': begin Assign(faile, name_array); Reset(faile); Readln(faile, n); { считывает старый массив } for i:=1 to n do Readln(faile, b[i]); a:=b; flag_array:=true; check_exit:=true; end; end; until (key_check='n')or(key_check='y'); end;
case key of '1': begin { создание массива } repeat ClrScr; Writeln('Enter the number of elements in the array.'); Writeln('If you do not want to introduce an element of itself, then the number
must be greater than 20.');
Enter them the greatest number.');
Readln(max); for i:=1 to n do b[i]:=random(max); Writeln('An array of ',n,' elements is given randomly.'); end else begin Writeln('Enter the values of the array elements.'); for i:=1 to n do Read(b[i]); end;Assign(faile, name_array); { Запись массива в файл } Rewrite(faile); Writeln(faile, n); for i:=1 to n do Writeln(faile, b[i]); Close(faile); flag_array:=true; time_buble:=0; time_lin:=0; time_insert:=0; message; end;
'2': begin { Бинарный поиск } search_binary; message; end;
'3': begin { Линейный поиск } search_linear; message; end;
'4': begin { Сортировка пузырьком } ClrScr; sort_buble; {check_array;} message; end;
'5': begin { Сортировка вставками } ClrScr; sort_insertion; {check_array;} message; end; '6': begin { Линейная сортировка (выбором) } ClrScr; sort_lin; {check_array;} message; end; '7': begin { Вывод таблицы } if (time_buble=0)or(time_lin=0)or(time_insert=0) then begin repeat Writeln('Not all of the algorithms used. If you want to fix it - press "1",
otherwise - press "2".');
Readln(key_table);case key_table of '1': begin if (time_buble=0) then begin Writeln('Activation sort buble! Press any key to continue...'); Readln; sort_buble; end; if (time_insert=0) then begin Writeln('Activation sort insertion! Press any key to continue...'); Readln; sort_insertion; end; if (time_lin=0) then begin Writeln('Activation sort lin! Press any key to continue...'); Readln; sort_lin; end; end; '2': begin { ничего }end; end; until (key_table='1')or(key_table='2'); end; tabl; message; end;
'8': begin { Выход из программы } exit:=true; break; end;
end; until (exit = true); end.
Скачано с http://vmk. /
