Сортировка посредством выбора
Упорядоченный список В' получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В', который первоначально должен быть пустым.
Например:
B=<20,10,8,-5,7>, B'=< >
B=<20,10,8,7>, B'=<-5>
B=<20,10,8>, B'=<-5,7>
B=<20,10>, B'=<-5,7,8>
B=<20>, B'=<-5,7,8,10>
B=< >, B'=<-5,7,8,10,20> .
Функция selekt упорядочивает массив s сортировкой посредством выбора.
/* сортировка методом выбора */
double *select( double *s, int n){
int i,j;
double c;
for (i=0; i<n-1; i++)
for (j=i+1;j<n;j++)
if (s[i]>s[j]){
c=s[i];
s[i]=s[j];
s[j]=c;
}
return(s);
}
Здесь, как и в предыдущем примере оба списка В и В' размещаются в разных частях массива s (см. рис.2).
Рис.2. Схема движения индексов при сортировке выбором.
Поиск в линейных списках
Последовательный поиск
Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V=<V1,V2,...,Vm> (в простейшем случае это целые числа).Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента.
Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В , а Si - количество сравнений, необходимое для его поиска, то
|
|
|
Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядке их расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка, что достигается использованием стоппера.
Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.
Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:
/* последовательный поиск без стоппера */
#include <iostream.h>
main() {
int k[100],v,i;
cout>>”Введите элементы массива”;
for (i=0;i<100;i++) cin>>k[i];
cout<<”Введите значение для поиска”;
cin>>v;
i=0;
while(k[i]!=v && i<100) i++;
|
|
|
if (k[i]==v) cout<<v<<i;
else cout<<"не найден"<<v;
}
С использованием стоппера программу можно записать в виде:
/* последовательный поиск со стоппером */
#include <iostream.h>
main() {
int k[100],v,i;
cout>>”Введите элементы массива”;
for (i=0;i<100;i++) cin>>k[i];
cout<<”Введите значение для поиска”;
cin>>v;
k[100]=v; /* стоппер */
i=0;
while(k[i]!=v) i++;
if (i<100) cout<<v<<i;
else cout<<"не найден"<<v;
}
Бинарный поиск
Для упорядоченных линейных списков существуют более эффективные алгоритмы поиска, хотя и для таких списков применим последовательный поиск. Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом списка. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин списка.
Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.
Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V - элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке К1,К2,...,К100.
|
|
|
/* Бинарный поиск */
#include <iostream.h>
main() {
int k[100], v, i, j ,m;
cout>>”Введите элементы массива”;
for (i=0;i<100;i++) cin>>k[i];
cout<<”Введите значение для поиска”;
cin>>v;
i=0; j=100; m=50;
while (k[m]!=v) {
if (k[m]<v) i+=m;
else j=m-i;
m=(i+j)/2;
}
cout<<v<<m;
}
Содержание работы
2. 1. Определить массив, элементы которого будут упорядочиваться. Тип массива выбрать по таблице №1.
Разработать функцию сортировки массива методом, выбранным по таблице 2 в соответствии с вариантом. Любым способом заполнить элементы массива значениями. Выполнить сортировку массива с помощью заданного алгоритма и проконтролировать ее результат. Сделать выводы.
Сохранить файл с тестом программы для последующих работ.
Таблица 1
| № варианта | Тип массива | № варианта | Тип массива |
| 1 | Одномерный символьный массив | 16 | Одномерный символьный массив |
| 2 | Одномерный массив целых чисел | 17 | Одномерный массив целых чисел |
| 3 | Одномерный массив плавающих чисел | 18 | Одномерный массив плавающих чисел |
| 4 | Одномерный массив длинных целых чисел | 19 | Одномерный массив длинных чисел |
| 5 | Одномерный массив коротких целых чисел | 20 | Одномерный массив коротких целых чисел |
| 6 | Одномерный массив типа double | 21 | Одномерный массив типа double |
| 7 | Статический одномерный массив беззнаковых целых чисел | 22 | Одномерный массив беззнаковых целых чисел |
| 8 | Одномерный массив типа float | 23 | Одномерный массив типа float |
| 9 | Одномерный массив беззнаковых коротких целых чисел | 24 | Одномерный массив коротких беззнаковых целых чисел |
| 10 | Одномерный массив коротких целых чисел | 25 | Одномерный массив коротких целых чисел |
| 11 | Одномерный массив типа float | 26 | Одномерный массив типа double |
| 12 | Одномерный массив целых чисел | 27 | Одномерный массив беззнаковых целых чисел |
| 13 | Одномерный массив типа float | 28 | Одномерный массив типа float |
| 14 | Одномерный массив беззнаковых целых чисел | 29 | Одномерный массив беззнаковых целых чисел |
| 15 | Одномерный массив коротких целых чисел | 30 | Одномерный массив коротких целых чисел |
Таблица 2
|
|
|
| № | Алгоритмы сортировки | № | Алгоритмы сортировки |
| 1 | Пузырьковая | 16 | Пузырьковая |
| 2 | Посредством выбора | 17 | Вставкой . |
| 3 | Пузырьковая | 18 | Посредством выбора |
| 4 | Вставкой | 19 | Вставкой |
| 5 | Вставкой | 20 | Посредством выбора |
| 6 | Посредством выбора | 21 | Посредством выбора |
| 7 | Пузырьковая | 22 | Пузырьковая |
| 8 | Вставкой | 23 | Пузырьковая |
| 9 | Вставкой. | 24 | Посредством выбора. |
| 10 | Посредством выбора | 25 | Пузырьковая |
| 11 | Вставкой | 26 | Посредством выбора |
| 12 | Посредством выбора | 27 | Посредством выбора |
| 13 | Пузырьковая | 28 | Пузырьковая |
| 14 | Вставкой | 29 | Пузырьковая |
| 15 | Вставкой. | 30 | Посредством выбора. |
2.2 Разработать функции последовательного и бинарного поиска в массиве вводимого с клавиатуры значения. Сравнить количество шагов, за которое осуществляется поиск необходимых данных при каждом способе.
2.3 Выполнить задание для самостоятельной работы по варианту из приложения А, оформив подпрограммы заполнения, подсчета нужного числового значения (по заданию) и вывода массива в виде отдельных функций. В основной программе произвести вызов нужных функций для двух матриц и выдать в качестве результата наибольшее из полученных значений.
Все необходимые данные должны передаваться подпрограммам в качестве параметров; все величины, используемые только внутри подпрограмм, должны быть описаны как локальные. Заполнение массивов следует производить с помощью датчика случайных чисел:
randomize - инициализирует генератор случайных чисел;
random (int num); - генератор случайных чисел.
Например, для заполнения матрицы случайными числами от -20 до 20 можно создать следующую функцию:
int RandomMas(int **a, const int n, const int m) {
randomize;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
a[i][j] = -20+random(41);
}
2.4 Сохранить все результаты в файлы и оформить отчет.
Требования к отчету
Отчет по работе должен содержать:
· название, цель, задачи работы;
· номер и условие своего варианта;
· текст (листинг) программ;
· полученные численные результаты;
· ответы на контрольные вопросы по указанию преподавателя.
Контрольные вопросы
1. При передачи массивов в функции используется передача по...?
2. Что такое «сортировка»? Сколько существует групп алгоритмов сортировки?
3. Сколько существует алгоритмов сортировки?
4. По каким признакам характеризуются алгоритмы сортировки?
5. Что нужно учитывать при выборе алгоритма сортировки?
6. Какой алгоритм сортировки считается самым простым?
7. Какой алгоритм сортировки считается самым эффективным?
8. Что означает понятие «скорость сортировки»?
9. В чем заключается метод пузырьковой сортировки?
10. В чем заключается метод сортировки посредством выбора?
11. В чем заключается метод сортировки вставками?
12. В чем заключается метод сортировки слиянием?
13. В чем заключается метод быстрой сортировки?
14. Что такое поиск?
15. Что называется ключом поиска?
16. Какие известны методы поиска?
17. Какой алгоритм поиска является наиболее эффективным?
18. Какое требование предъявляется к структуре данных, в которой выполняется бинарный поиск?
21. В чем заключается метод линейного поиска?
22. В чем заключается метод бинарного поиска?
Приложение А
Дата добавления: 2018-05-13; просмотров: 415; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!