Внутренний цикл for имеет два условия проверки
Лабораторная работа № 1
ИССЛЕДОВАНИЕ СОРТИРОВОК РАЗЛИЧНЫХ ТИПОВ
Цель работы: изучить различные методы сортировки как прямые (выбора, включения и обмена), так и улучшенные (слияниями, пирамидальная - турнирная, распределяющая, пузырьковая с просеиванием, метод поиска нового номера и метод последовательного поиска минимумов).
Задача работы: овладеть навыками написания программ при исследовании различных методов сортировки.
Порядок работы :
q изучить описание лабораторной работы;
q по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
q написать программу в соответствии с вариантом задания;
q отладить программу;
q решить задачу;
q оформить отчет.
Теория
Среди улучшенных методов сортировки встречаются как доработанные прямые методы, так и методы уже более высокого уровня, т.е. с новой идеей, где одним из элементов сортировки является прямой метод. Эффективность у доработанных прямых методов лучше, чем N*N, но не достигает N*lonN. А у улучшенных методов более высокого уровня эффективность близка к N*lonN. Улучшенные прямые методы обычно применяют на небольших объёмах данных, а вот улучшенные методы более высокого уровня используются для сортировки больших объёмов.
Краткая теория, примеры сортировок
Каждый алгоритм сортировки состоит из трех основных частей:
|
|
|
1. Функция сравнения пары элементов сортируемого массива.
2. Процедура перестановки, меняющая местами пару элементов.
3. Сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.
Прежде, чем приступить к сортировке необходимо:
· определить класс, выполняющий сортировку.
· Начать с первого элемента.
· Последовательно просмотреть все остальные элементы. Если очередной элемент окажется меньше текущего первого элемента, поменять их местами.
· Начать со второго элемента, просмотреть все остальные элементы.
· Продолжать до последнего элемента.
Пузырьковая сортировка
Самый известный (и пользующийся дурной славой) алгоритм — пузырьковая сортировка (bubblesort, сортировка методом пузырька, или просто сортировка пузырьком)[1]. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки.
Пузырьковая сортировка относится к классу обменных сортировок, т.е. к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения (т.е. многократные сравнения одних и тех же элементов) и, при необходимости, обмен соседних элементов. Элементы ведут себя подобно пузырькам воздуха в воде — каждый из них поднимается на свой уровень. Простая форма алгоритма сортировки показана ниже:
|
|
|
/* Пузырьковая сортировка. */
voidbubble(char *items, intcount)
{
registerint a, b;
register char t;
for(a=1; a < count; ++a)
for(b=count-1; b >= a; --b) {
if(items[b-1] > items[b]) {
/* exchange elements */
t = items[b-1];
items[b-1] = items[b];
items[b] = t;
}
}
}
Здесь items— указатель на массив символов, подлежащий сортировке, a count — количество элементов в массиве. Работа пузырьковой сортировки выполняется в двух циклах. Если количество элементов массива равно count, внешний цикл приводит к просмотру массива count - 1 раз. Это обеспечивает размещение элементов в правильном порядке к концу выполнения функции даже в самом худшем случае. Все сравнения и обмены выполняются во внутреннем цикле. (Слегка улучшенная версия алгоритма пузырьковой сортировки завершает работу, если при просмотре массива не было сделано ни одного обмена, но это достигается за счет добавления еще одного сравнения при каждом проходе внутреннего цикла.)
С помощью этой версии алгоритма пузырьковой сортировки можно сортировать массивы символов по возрастанию. Например, следующая короткая программа сортирует строку, вводимую пользователем:
|
|
|
/* Программа, вызывающая функцию сортировки bubble */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void bubble(char *items, int count);
Int main(void)
{
char s[255];
printf("Введитестроку:");
gets(s);
bubble(s, strlen(s));
printf("Отсортированнаястрока: %s.\n", s);
return 0;
}
Сортировка Шелла
Сортировка Шелла называется так по имени своего автора, Дональда Л. Шелла (DonaldLewisShell)[4]. Однако это название закрепилось, вероятно, также потому, что действие этого метода часто иллюстрируется рядами морских раковин, перекрывающих друг друга (по-английски "shell" — "раковина"). Общая идея заимствована из сортировки вставками и основывается на уменьшении шагов.
/* СортировкаШелла. */
void shell(char *items, int count)
{
registerinti, j, gap, k;
char x, a[5];
a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
for(k=0; k < 5; k++) {
gap = a[k];
for(i=gap; i< count; ++i) {
x = items[i];
for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)
items[j+gap] = items[j];
items[j+gap] = x;
}
}
}
внутренний цикл for имеет два условия проверки.
Сравнение x<items[j] необходимо для процесса сортировки. Выражение j>=0 предотвращает выход за границу массива items.
В слегка модифицированных версиях данного метода сортировки применяются специальные элементы массива, называемые сигнальными метками. Они не принадлежат к собственно сортируемому массиву, а содержат специальные значения, соответствующие наименьшему возможному и наибольшему возможному элементам. Это устраняет необходимость проверки выхода за границы массива. Однако применение сигнальных меток элементов требует конкретной информации о сортируемых данных, что уменьшает универсальность функции сортировки.
|
|
|
Задания по вариантам:
Необходимо выполнить задание в соответствии с номером варианта, таблица 1. В соответствии с заданием необходимо выполнить исследование предложенного по варианту алгоритма.
Таблица 1 - Задание на лабораторную работу №6
| № варианта | Задание |
| 1 | Сортировка методом прямого включения. Определить ее эффективность. Последовательность состоит из 12 элементов. |
| 2 | Сортировка методом прямого выбора. Определить ее эффективность. Последовательность состоит из 20 элементов |
| 3 | Пирамидальная сортировка. Определить ее эффективность. Последовательность состоит из 6 элементов |
| 4 | Сортировка Шелла. Определить ее эффективность. Последовательность состоит из 19 элементов |
| 5 | Быстрая сортировка. Определить ее эффективность. Последовательность состоит из 13 элементов |
| 6 | Сортировка прямого обмена.. Определить ее эффективность. Последовательность состоит из 17 элементов. |
| 7 | Сортировка методом прямого включения. Определить ее эффективность. Последовательность состоит из 18 элементов. |
| 8 | Сортировка методом прямого выбора. Определить ее эффективность. Последовательность состоит из 16 элементов |
| 9 | Пирамидальная сортировка. Определить ее эффективность. Последовательность состоит из 15 элементов |
| 10 | Сортировка Шелла. Определить ее эффективность. Последовательность состоит из 22 элементов |
| 11 | Быстрая сортировка. Определить ее эффективность. Последовательность состоит из 14 элементов |
| 12 | Сортировка прямого обмена.. Определить ее эффективность. Последовательность состоит из 121элемента. |
| 13 | Сортировка методом прямого включения. Определить ее эффективность. Последовательность состоит из 10 элементов. |
| 14 | Сортировка методом прямого выбора. Определить ее эффективность. Последовательность состоит из 23 элементов |
| 15 | Пирамидальная сортировка. Определить ее эффективность. Последовательность состоит из 24 элементов |
| 16 | Сортировка Шелла. Определить ее эффективность. Последовательность состоит из 12 элементов |
| 17 | Быстрая сортировка. Определить ее эффективность. Последовательность состоит из 13 элементов |
| 18 | Сортировка прямого обмена.. Определить ее эффективность. Последовательность состоит из 18 элементов. |
| 19 | Сортировка методом прямого включения. Определить ее эффективность. Последовательность состоит из 117 элементов. |
| 20 | Сортировка методом прямого выбора. Определить ее эффективность. Последовательность состоит из 8 элементов |
| 21 | Пирамидальная сортировка. Определить ее эффективность. Последовательность состоит из 19 элементов |
| 22 | Сортировка Шелла. Определить ее эффективность. Последовательность состоит из 23 элементов |
| 23 | Быстрая сортировка. Определить ее эффективность. Последовательность состоит из 22 элементов |
| 24 | Сортировка прямого обмена.. Определить ее эффективность. Последовательность состоит из 15 элементов. |
| 25 | Сортировка методом прямого включения. Определить ее эффективность. Последовательность состоит из 14 элементов. |
| 26 | Сортировка методом прямого выбора. Определить ее эффективность. Последовательность состоит из 20 элементов |
| 27 | Пирамидальная сортировка. Определить ее эффективность. Последовательность состоит из 19 элементов |
| 28 | Сортировка Шелла. Определить ее эффективность. Последовательность состоит из 13 элементов |
| 29 | Быстрая сортировка. Определить ее эффективность. Последовательность состоит из 11 элементов |
| 30 | Сортировка прямого обмена.. Определить ее эффективность. Последовательность состоит из 22 элементов. |
Лабораторная работа № 2
ИССЛЕДОВАНИЕ «Поиска»
Цель работы: изучить различные методы поиска, линейный поиск, последовательный поиск, двоичный поиск, Индексно-последовательный поиск, Поиск в таблице, Поиск прямой строки, Алгоритм кнута, Морриса и Пратта, Алгоритм Боуера и Мура
Задача работы: овладеть навыками написания программ при исследовании различных методов сортировки.
Порядок работы :
q изучить описание лабораторной работы;
q по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
q написать программу в соответствии с вариантом задания;
q отладить программу;
q решить задачу;
q оформить отчет.
Теория
Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.
Если отрезок имеет длину N, то найти решение с точностью доε можно за время N\over\epsilon.
Таким образом, асимптотическая сложность алгоритма — O(n).
В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов.
поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
В качестве примера можно рассмотреть поиск значения функции на множестве целых чисел, представленной таблично.
Переменные L и R содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Исследования начинаются с первого элемента отрезка. Если искомое значение не равно значению функции в данной точке, то осуществляется переход к следующей точке. Т.о., в результате каждой проверки область поиска уменьшается на один элемент.
01 //Линейныйпоиск
02 int function LinearSearch (Array A, int L, int R, int Key);
03 begin
04 for X = L to R do
05 if A[X] = Key then
06 return X
07 return -1; // элемент не найден
08 end;
09
10 /******************/
Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.
Частным случаем двоичного поиска является метод бисекции, который применяется для поиска корней заданной непрерывной функции на заданном отрезке
Реализация двоичного поиска на С++
Для поиска в массиве, состоящем из 1024 элементов, потребуется максимум 10 сравнений, т.к. деление будет происходить так: 512, 256, 128, 64, 32, 16, 8, 4, 2, 1. Посчитать максимальное количество сравнений можно и таким образом: представим 1024 как 2 в 10-й степени. Число степени и будет нам говорить о количестве максимальных сравнений. К примеру, в массиве из 1 048 576 (2 в 20-й степени) элементов, нужно выполнить как максимум только 20 сравнений. Если брать в сравнение этот вид поиска и линейный поиск, то в массиве из 1 048 576 элементов, нужно было бы выполнить в среднем 1 048 576 / 2 сравнений, а это целых 524 288.
Для того, чтобы начинать программировать, нужно обязательно четко себе уяснить задачу, которую необходимо реализовать - также и в случае с алгоритмом двоичного поиска
Если вам не до конца понятен, после прочтения предыдущих абзацев, принцип его работы, то предлагаю сделать следующее: предложите напарнику загадать число в интервале, к примеру, от 1 до 1000, затем начинайте отгадывать его, называя центральные значения.
Сначала назовите число 500, если не угадаете, то узнайте у напарника: является ли загаданное число большим, чем 500 или нет
Допустим, что загаданное число меньше, то называем центральное значение оставшегосяподмассива чисел - 250. Далее следуем таким же образом, пока не угадаем. В самом наихудшем случае у нас будет как максимум 10 сравнений.
Программа снабжена множеством комментариев, поэтому вам не составит труда разобраться с ее работой.
//Реализация алгоритма бинарного поиска в массиве
//подключаем необходимые заголовочные файлы
#include<iostream>
#include <iomanip>
//определяемпрототипыфункций
intbinarySearch(int[], int, int, int, int);
voidprintHeader(int);
voidprintRow(int[], int, int, int, int);
//подключаем пространства имен
usingnamespacestd;
intmain()
{
//выделяем память под переменные
constintarraysize = 15;
int array[arraysize];
intkey, result;
//заполняем массив отсортированными данными
for (inti = 0; i<arraysize; i++)
array[i] = 2 * i;
//запрашиваем и сохраняем ключ поиска
cout<< "Enter a key of search (0 - 28): ";
cin>>key;
//вызываем функцию, печатающую индексы массива
//в качестве аргумента функция принимает размер массива
printHeader (arraysize);
//вызываем функцию, выполняющую бинарный поиск.
//если функция найдет ключ поиска, то она вернет его индекс,
//вобратномслучаевернет -1
result = binarySearch (array, key, 0, arraysize, arraysize);
if (result != -1)
cout<<endl<< key << " found in element of massiv " << result <<endl;
else
cout<<endl<< key << " no found" <<endl;
return 0;
}
/*Данная функция самая важная - она то и выполняет бинарный поиск.
В качестве аргументов она принимает, соответственно, массив, ключ поиска, нижнюю границу массива, верхнюю границу массива, размер массива.
Первоначально нижней границей массива является 0, а верхней - размер массива, т.к. в первой итерации бинарного поиска мы будем работать со всем массивом, а уже во второй с половиной, третьей - половиной половины (четвертиной) и т.д.
*/
intbinarySearch (int a[], int key, int low, int high, int size)
{
//выделяем место в памяти для переменной, которая будет
//у нас сохранять значение середины массива
intmiddle;
//цикл двоичного поиска
//цикл длится, пока между границами массива есть значения
while (low <= high)
{
middle = (low + high) / 2;
//вызываем функцию вывода подмассива на экран
printRow (a, low, middle, high, size);
//если найден ключ поиска, то возвращаем его индекс
if (key == a[middle])
returnmiddle;
//в случае, если не найден ключ поиска, и его значение меньше
//среднего значения, меняем верхнюю границу массива, тем самым
//отсекая половину с большими значениями, в которой точно искать нечего
else if (key < a[middle])
high = middle - 1;
//в случае, если не найден ключ поиска, и его значение больше
//среднего значения, меняем нижнюю границу массива, тем самым
//отсекая половину с меньшими значениями
else
low = middle + 1;
}
//если ключ поиска не найден в массиве, то возвращаем -1
return -1;
}
//данная функция выводит на экран индексы элементов массива,
//с помощью которых визуально удобнее воспринимать массив
voidprintHeader (int size)
{
cout<<endl<< "Indexes: " <<endl;
for (inti = 0; i< size; i++)
cout<<setw(3) <<i<< ' ';
cout<<endl;
for (inti = 0; i< size; i++)
cout<< "----";
cout<<endl;
}
//данная функция в каждой итерации двоичного поиска выводит
//подмассив, участвующийвпоиске
voidprintRow (int b[], int low, int middle, int high, int size)
{
for (inti = 0; i< size; i++)
{
//элементы, не участвующие в поиске, не выводятся
if (i< low || i> high)
cout<< " ";
//средний элемент помечается звездочкой "*"
else if (i == middle)
cout<<setw(3) << b[i] << '*';
//участвующие в поиске элементы выводятся
else
cout<<setw(3) << b[i] << ' ';
}
//перевод курсора на следующую строку
cout<<endl;
}
Задания по вариантам
| № варианта | Задание |
| 1. | линейный поиск, |
| 2. | Используя последовательный поиск, найти в массиве элемент с ключом 2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 3. | Используя Индексно-последовательный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 4. | Используя Поиск в таблиценайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 5. | Используя Алгоритм кнута, Морриса и Праттанайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 6. | Используя Поиск прямой строкинайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 7. | Используя двоичный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 8. | Используя Алгоритм Боуера и Муранайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 9. | Используя Поиск в таблиценайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 10. | Используя Алгоритм кнута, Морриса и Праттанайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 11. | Используя Поиск прямой строкинайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 12. | Используя двоичный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 13. | Используя Алгоритм Боуера и Муранайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 14. | Используя последовательный поиск, найти в массиве элемент с ключом 2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 15. | Используя Индексно-последовательный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 16. | Используя Поиск в таблиценайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 17. | Используя Алгоритм кнута, Морриса и Праттанайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 18. | Используя Поиск прямой строкинайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 19. | Используя двоичный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 20. | Используя Индексно-последовательный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 21. | Используя Поиск в таблиценайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 22. | Используя Алгоритм кнута, Морриса и Праттанайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 23. | Используя Поиск прямой строкинайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 24. | Используя двоичный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 25. | Используя Индексно-последовательный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 26. | Используя Поиск в таблиценайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 27. | Используя Алгоритм кнута, Морриса и Праттанайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 28. | Используя Поиск прямой строкинайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 29. | Используя двоичный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
| 30. | Используя двоичный поискнайти в массиве элемент с ключом2+N, массив состоит из Mэлементов, M=25-N ГдеN – номер варианта студента. |
Дата добавления: 2018-04-05; просмотров: 173; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!