Структуры и алгоритмы обработки данных
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Задача 1. Методы сортировки
Задание:
Составить программу, реализующую указанный вид сортировки для массива элементов размерности N (N?50) указанного типа сформированного случайным образом. Отчет должен содержать краткое объяснение алгоритма сортировки, листинг программы и результаты работы программы. Для варианта №10: сортировка массива целых чисел алгоритмом линейная вставка.
Решение:
Объяснение алгоритма сортировки линейная вставка.
Сортировка линейной вставкой - самый простой алгоритм, реализующий ручную сортировку карт при игре в Бридж. Просматривая массив с одного конца до другого, каждый элемент массива ставится в правильную позицию по отношению к уже отсортированным элементам.
Эта сортировка работает со списком неупорядоченных положительных целых чисел, сортируя их в порядке возрастания.
Описание алгоритма:
Сортируется вектор A длиной N
Нач
Для i от 2 до N Цикл
X:= A[i];:= i-1;
Пока (j 1) и (A[j] > X) Цикл[j+1]:= A[j];{сдвиг элементов}:= j - 1;
КЦикл[j+1]:= X;{вставка элемента на свое место}
КЦикл
Кон
На каждой итерации первое число не отсортированного списка удаляется из него и помещается на соответствующее ему место в отсортированном списке. Для этого отсортированный список, просматривается, начиная с наименьшего числа до тех пор, пока не находят соответствующее место для нового числа, то есть пока все числа с меньшими значениями не окажутся впереди него, а все числа с большими значениями - после него.
Покажем работу алгоритма на примере:
412 71 81 59 14 273 87
Итерация 0:
Неотсортированный: 412 71 81 59 14 273 87
Отсортированный: 27
Итерация 1:
Неотсортированный: 412 71 81 59 14 273 87
Отсортированный: 27412
Итерация 2:
Неотсортированный: 71 81 59 14 273 87
Отсортированный: 2771 412
Итерация 3:
Неотсортированный: 81 59 14 273 87
Отсортированный: 2771 81 412
Итерация 4:
Неотсортированный: 59 14 273 87
Отсортированный: 2759 71 81 412
Итерация 5:
Неотсортированный: 14 273 87
Отсортированный: 14 27 59 71 81 412
Итерация 6:
Неотсортированный: 273 87
Отсортированный: 14 27 59 71 81 273 412
Итерация 7:
Неотсортированный: 87
Отсортированный: 14 27 59 71 81 87 273 412
Листинг программы
{сортировка массива целых чисел алгоритмом линейная вставка}
Program Sort1;crt, dos;
const=50; {максимальный размер вектора}
type=array [1..ARRAYSIZE] of integer; {тип вектора}: arrayType; {сортируемый вектор}
n: integer; {количество элементов в векторе}
i,j: integer;: char;
{процедура создания и вывода вектора theArray с размером SIZE}
Procedure Vector (SIZE, MAX: integer; var theArray:arrayType);;i:=1 to SIZE do[i]:=random(MAX);('Исходный массив: ');i:=1 to Size do(theArray[i],' ');;
{процедура сортировки}InsertSort (size: integer; var theArray: arrayType);
var: integer; {начальная позиция вставляемого на место элемента}: integer; {значение вставляемого на место элемента}: integer; {позиция вставляемого в упорядоченном векторе}
beginnewPos:=2 to SIZE do:=theArray [newPos];:=newPos-1;(currentPos>=1) and (theArray[currentPos]>newValue) do[currentPos+1]:=theArray[currentPos];:=currentPos-1;;[currentPos+1]:=newValue;;;
{главная программа}
clrscr;('Введите желаемое количество элементов (до 50)');
Readln(n);(n,ARRAYSIZE,a);(n,a);;('Отсортированный массив: ');i:=1 to n do(' ',a[i]);
Readln;('Будете еще? (да - y; нет - n)');
ch:=ReadKey;(ch='N') or (ch='n');
end.
Задача 2. Исследование методов сортировки
Задание:
Составить алгоритм и разработать программу, реализующую указанный вид сортировки. Исследовать работу программы на сортировке n целых чисел, если они:
расположены случайным образом;
отсортированы;
отсортированы в обратном порядке;
В результате исследований построить графики зависимости tср (время сортировки) от n (количество элементов) для всех 3-х случаев (случайный массив, отсортированный, отсортирован в обратном порядке). Отчет должен содержать краткое объяснение алгоритма сортировки, листинг программы, графики, построенные в результате работы программы, выводы. Для варианта №10: быстрая сортировка (обменная сортировка с разделением).
Решение:
Объяснение алгоритма быстрой сортировки
Это один из лучших алгоритмов сортировки. Основные особенности этого алгоритма покажем на примере сортировки произвольного вектора А:
Выбирается "центральный" элемент массива А - х. Массив делится на две части этим элементом.
Указатель i устанавливаем в начало левой части. Меняем этот указатель до тех пор, пока элемент Аi меньше центрального элемента х (Аi<х).
Указатель j устанавливаем в конец правой части. Меняем этот указатель до тех пор, пока элемент Аj больше центрального элемента х (Аj<х).
Если левый указатель i меньше правого указателя j, то элементы Аi и Аj меняем местами. Процесс продолжается до тех пор, пока произвольно выбранный вначале "центральный" элемент массива не займет свою позицию в массиве, то есть все элементы стоящие слева от этого элемента будут меньше его, а все элементы, стоящие справа - больше, а также все элементы левой части будут меньше каждого правого элемента.
Если слева от выбранного "центра" более одного элемента, то процедура повторяется для левой части массива.
Если справа от выбранного "центра" более одного элемента, то процедура повторяется для правой части массива.
Листинг программы
{сортировка массива целых чисел алгоритмом быстрая сортировка}
Program Sort2;crt, dos;
const=5000; {максимальный размер вектора}
type=array [1..ARRAYSIZE] of integer; {тип вектора}: arrayType; {сортируемый вектор}
n: integer; {количество элементов в векторе}
exp: integer;: byte;: integer;,j,k: integer;: integer;: text;: real;_time:array[1..3] of real;
{процедура создания век