Практическая работа №6 по дисциплине: Теория алгоритмов наименование работы: Составление алгоритма быстрой сортировки.


Смоленский колледж телекоммуникаций
(филиал) федерального государственного образовательного
бюджетного учреждения высшего профессионального образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
Практическая работа №6
по дисциплине: Теория алгоритмов
наименование работы: Составление алгоритма быстрой сортировки.
для специальностей: 230115, 09.02.03
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.
Смоленск, 2014
1. Цель работы: овладеть навыками составления алгоритмов быстрой сортировки.
2. Литература:
2.1. Балюкевич, Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф.— Электрон. текстовые данные.— М.: Евразийский открытый институт, 2009.— 188 c. ISBN:978-5-374-00220-1
2.2. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 160 c. ISBN:978-5-4439-0014-8
2.3. Гаврилов, Г.П. Задачи и упражнения по дискретной математике [Электронный ресурс]: учебное пособие/ Гаврилов Г.П., Сапоженко А.А.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2009.— 416 c. ISBN:978-5-9221-0477-7
3. Подготовка к работе:
3.1. Повторить тему «Быстрая сортировка. Двоичный поиск».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Сформулировать определение сортировки?
3.3.2.Описать суть метода декомпозиции при построении алгоритмов?
3.3.3. Описать суть метода слияния?
4. Основное оборудование: ПЭВМ
5. Задание:
Выполните задание согласно варианту.
5.1. Составить алгоритм и разработать программу, выполняющую сортировку заданного массива методом быстрой сортировки. Количество элементов в массиве определяется согласно варианту.
№ варианта Тип элементов Количество элементов Упорядочить по:
1 Целочисленный 26 возрастанию
2 Целочисленный 29 убыванию
3 Целочисленный 30 возрастанию
4 Целочисленный 19 убыванию
5 Целочисленный 21 возрастанию
6 Целочисленный 15 убыванию
7 Целочисленный 24 возрастанию
8 Целочисленный 35 убыванию
9 Целочисленный 25 возрастанию
10 Целочисленный 18 убыванию
11 Целочисленный 32 возрастанию
12 Целочисленный 38 убыванию
13 Целочисленный 34 возрастанию
14 Целочисленный 42 убыванию
15 Целочисленный 21 возрастанию
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задание 5 письменно.
6.4. Сообщить преподавателю о выполненных заданиях.
6.5. Повторить правила техники безопасности:
Правила техники безопасности в компьютерном классе.
Перед началом работы необходимо убедиться в отсутствии видимых повреждений аппаратуры.
Работа с компьютером производится строго по указаниям преподавателя.
Запрещается:
Разъединять или соединять разъемы аппаратуры;
Прикасаться к экрану монитора;
Включать и выключать аппаратуру без указания преподавателя;
Класть какие-либо предметы на монитор, системный блок или клавиатуру;
Работать во влажной одежде, а также влажными или грязными руками;
Пытаться самостоятельно исправлять возникшую в аппаратуре неисправность.
Включите компьютер.
Включите в сеть стабилизатор напряжения (если он имеется).
Включите принтер (если он имеется).
Включите монитор.
Включите системный блок (большая кнопка на передней панели).
Выключение компьютера.
Завершите выполнение всех программ.
Выполните команду: Пуск Завершение работы Выключить компьютер (Alt+F4→ Завершение работы).
Выключите системный блок.
6.6. Приступить к выполнению тестирование программ.
6.7.Оформить отчет.
7. Содержание отчета:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия задач своего варианта.
7.3. Представить выполненные задания согласно варианта, текст программы с комментариями.
7.4. Ответы на контрольные вопросы.
8. Контрольные вопросы:
8.1. Перечислите достоинства алгоритма быстрой сортировки?
8.2. Перечислите недостатки алгоритма быстрой сортировки?
8.3. Объясните суть алгоритма быстрой сортировки?
8.4. Что такое двоичный поиск?
8.5. Какой элемент называют опарным?

Составил преподаватель __________________________Скряго О.С.
9. Приложение:
Массив - это сгруппированный по месту распределения набор значений однотипных переменных, имеющих общее название. Различают одномерный и многомерный массивы. Максимально допустимое количество измерений в массиве - четыре. Допускаются массивы любых типов данных.
Элемент массива - это составная часть массива; индексированная переменная с одноимённым названием, имеющая некоторое значение.

Индекс элемента массива - одно или несколько целых значений, указанных в виде константы, переменной или выражения, перечисленных через запятую и заключённых в квадратные скобки. Индекс элемента массива однозначно определяет место элемента в массиве. Индекс элемента массива указывается непосредственно после идентификатора переменной (названия массива) и является неотъемлемой частью элемента массива. В MQL4 принято индексирование, начинающееся с нуля.

Пример описания массива:
Const
n=20; {задали размерность}
Varmas: array[1..n] of integer; {описали массив из целых чисел заданной размерности}
Пример заполнения массива:
for i:=1 to n do {цикл от 1 до n}
begin
writeln(‘Введите элемент’);
readln(mas[i]); {оператор ввода}
end;
Быстрая сортировка
Основа алгоритма была разработана в 1960 году (C.A.R.Hoare) и с тех пор внимательно изучалась многими людьми. Быстрая сортировка особенно популярна ввиду легкости ее реализации; это довольно хороший алгоритм общего назначения, который хорошо работает во многих ситуациях, и использует при этом меньше ресурсов, чем другие алгоритмы.
Основные достоинства этого алгоритма состоят в том, что он точечный (использует лишь небольшой дополнительный стек), производительный, и имеет экстремально короткий внутренний цикл. Недостатки алгоритма состоят в том, что он рекурсивен (реализация очень затруднена когда рекурсия недоступна), в худшем случае он требует N2 операций, кроме того он очень "хрупок": небольшая ошибка в реализации, которая легко может пройти незамеченной, может привести к тому, что алгоритм будет работать очень плохо на некоторых файлах.
2940050868680Суть алгоритма: число операций перемены местоположений элементов внутри массива значительно сократится, если менять местами далеко стоящие друг от друга элементы. Для этого выбирается для сравнения один элемент х, отыскивается слева первый элемент, который не меньше х, а справа первый элемент, который не больше х. Найденные элементы меняются местами. После первого же прохода все элементы, которые меньше х, будут стоять слева от х, а все элементы, которые больше х, - справа от х. С двумя половинами массива поступают точно также. Продолжая деление этих половин до тех пор пока не останется в них по 1 элементу.
Разбиение массива А[0..п — 1] и, в общем случае, его подмассива А [L..r] (0<=1<=r<=п— 1) можно выполнить следующим образом. Сначала выбирается элемент, относительно которого будет выполняться разбиение. В силу важности роли этого элемента он называется опорным (pivot). Выберем в качестве опорного первый элемент подмассива: р = А [I].
Имеется также ряд различных процедур перестановки элементов для разбиения. Здесь нами будет использоваться эффективный метод, основанный на двух проходах подмассива — слева направо и справа налево, и при каждом проходе элементы массива будут сравниваться с опорным элементом. Проход слева направо начинается со второго элемента. Поскольку мы хотим, чтобы элементы, меньшие опорного, находились в первой части подмассива, первый проход пропускает элементы, меньшие опорного, и останавливается, встретив первый элемент, который не меньше опорного. Проход справа налево начинается с последнего элемента подмассива. Поскольку надо, чтобы все элементы, большие опорного, находились во второй части подмассива, при этом проходе опускаются все элементы, большие опорного, и проход останавливается, встретив первый элемент, не превышающий опорный.
В зависимости от того, пересеклись ли индексы сканирования, возможны три ситуации. Если индексы сканирования i и j не пересеклись, т.е. i < j, то мы просто обмениваем элементы A [i] и A [j] и продолжаем сканирование путем увеличения i и уменьшения j. Если при сканировании произошло пересечение индексов, т.е. г > j, то мы выполняем разбиение, обменивая опорный элемент с A [j]. И, наконец, если при сканировании индексы остановились на одном элементе, т.е. г = j, то значение этого элемента должно быть равно р (почему?). Последний случай можно объединить со случаем пересечения индексов (i > j), обменивая опорный элемент с A [j] при i >=j.
function Part(l, r: integer):integer;
var v, i, j, b: integer;
begin
V:=a[l];
I:=l;
j:=r+1;
repeat
repeat
inc(i)
until (a[i]>=v) or (i=j-1);
repeat
dec(j)
until (a[j]<=v)or (j=i+1);
b:=a[i];
a[i]:=a[j];
a[j]:=b;
until i>=j;
b:=a[j];
a[j]:=a[i];
a[i]:=b;
b:=a[j];
a[j]:= a[l];
a[l]:=b;
part:=j;
end; 82550793756540502251075
procedure QuickSort(l, t: integer);
var s: integer;
begin
if l<t then
begin
s:=part(l, t);
QuickSort(l,s-1);
QuickSort(s+1,t);
end; 82550-1315720

Приложенные файлы

  • docx 21
    Размер файла: 961 kB Загрузок: 0

Добавить комментарий