- •Обработка одномерных массивов
- •1. Цель работы
- •2. Указание к работе
- •3. Оформление отчета
- •4. Требования к работе
- •5. Теоретический материал Инициализация массива случайными числами
- •Измерение времени работы программы
- •Сортировка пузырьком
- •Сортировка выбором
- •Сортировка вставками
- •Сортировка подсчетом
- •Сортировка слиянием
- •Линейный поиск в массиве
- •Двоичный поиск в массиве
- •7. Варианты индивидуальных заданий
Линейный поиск в массиве
Линейным поиском называется обычный просмотр всего массива на предмет нахождения отдельного элемента, отвечающего заданному условию.
Линейный поиск – простейшая разновидность алгоритмов поиска данных.
Например, если нам требуется найти число 5 в массиве из 15 элементов, то мы начинаем поиск с элемента с номером 0 и последовательно проверяем каждый элемент на равенство числу 5. Если совпадение найдено – необходимо запомнить номер элемента и завершить цикл поиска.
Ввиду простоты алгоритма его псевдокод и реализация не приводятся и предлагаются для самостоятельной работы.
Двоичный поиск в массиве
Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск.
Переменные lowerBound и upperBound содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением upperBound становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.
Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.
Алгоритм двоичного поиска приведен ниже:
lowerBound = 0
upperBound = size
Повторять бесконечно
M = (lowerBound + upperBound) / 2
Если K < A[M], то
upperBound = M – 1
Иначе Если K > A[M], то
lowerBound = M + 1
Иначе
Сообщить «Элемент найден, его индекс: », M
Выход из цикла
Все если
Если lowerBound > upperBound, то
Сообщить «Элемент не найден»
Выход из цикла
Все если
Все повторять
В описанном выше алгоритме приняты следующие условия:
size – размер массива
K – число, которое нужно найти
М – индекс найденного элемента.
7. Варианты индивидуальных заданий
|
Задание |
Сложность |
Алгоритм сортировки |
Алгоритм поиска |
|
|
элементы, присутствующие в обоих массивах А и В |
1 |
Пузырьком |
Линейный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
1 |
Пузырьком |
Линейный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
1 |
Пузырьком |
Линейный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
1 |
Пузырьком |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
1 |
Пузырьком |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
1 |
Пузырьком |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
1 |
Пузырьком |
Линейный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
1 |
Пузырьком |
Линейный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
1 |
Пузырьком |
Линейный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
1 |
Пузырьком |
Линейный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
1 |
Пузырьком |
Линейный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
1 |
Пузырьком |
Линейный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
1 |
Пузырьком |
Линейный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
1 |
Пузырьком |
Линейный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
1 |
Пузырьком |
Линейный |
|
|
элементы, присутствующие в обоих массивах А и В |
2 |
Выбором |
Линейный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
2 |
Выбором |
Линейный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
2 |
Выбором |
Линейный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
2 |
Выбором |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
2 |
Выбором |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
2 |
Выбором |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
2 |
Выбором |
Линейный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
2 |
Выбором |
Линейный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
2 |
Выбором |
Линейный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
2 |
Выбором |
Линейный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
2 |
Выбором |
Линейный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
2 |
Выбором |
Линейный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
2 |
Выбором |
Линейный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
2 |
Выбором |
Линейный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
2 |
Выбором |
Линейный |
|
|
элементы, присутствующие в обоих массивах А и В |
3 |
Вставками |
Линейный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
3 |
Вставками |
Линейный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
3 |
Вставками |
Линейный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
3 |
Вставками |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
3 |
Вставками |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
3 |
Вставками |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
3 |
Вставками |
Линейный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
3 |
Вставками |
Линейный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
3 |
Вставками |
Линейный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
3 |
Вставками |
Линейный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
3 |
Вставками |
Линейный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
3 |
Вставками |
Линейный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
3 |
Вставками |
Линейный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
3 |
Вставками |
Линейный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
3 |
Вставками |
Линейный |
|
|
элементы, присутствующие в обоих массивах А и В |
4 |
Подсчетом |
Линейный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
4 |
Подсчетом |
Линейный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
4 |
Подсчетом |
Линейный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
4 |
Подсчетом |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
4 |
Подсчетом |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
4 |
Подсчетом |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
4 |
Подсчетом |
Линейный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
4 |
Подсчетом |
Линейный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
4 |
Подсчетом |
Линейный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
4 |
Подсчетом |
Линейный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
4 |
Подсчетом |
Линейный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
4 |
Подсчетом |
Линейный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
4 |
Подсчетом |
Линейный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
4 |
Подсчетом |
Линейный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
4 |
Подсчетом |
Линейный |
|
|
элементы, присутствующие в обоих массивах А и В |
5 |
Пузырьком |
Двоичный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
5 |
Пузырьком |
Двоичный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
5 |
Пузырьком |
Двоичный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
5 |
Пузырьком |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
5 |
Пузырьком |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
5 |
Пузырьком |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
5 |
Пузырьком |
Двоичный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
5 |
Пузырьком |
Двоичный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
5 |
Пузырьком |
Двоичный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
5 |
Пузырьком |
Двоичный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
5 |
Пузырьком |
Двоичный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
5 |
Пузырьком |
Двоичный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
5 |
Пузырьком |
Двоичный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
5 |
Пузырьком |
Двоичный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
5 |
Пузырьком |
Двоичный |
|
|
элементы, присутствующие в обоих массивах А и В |
6 |
Выбором |
Двоичный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
6 |
Выбором |
Двоичный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
6 |
Выбором |
Двоичный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
6 |
Выбором |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
6 |
Выбором |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
6 |
Выбором |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
6 |
Выбором |
Двоичный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
6 |
Выбором |
Двоичный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
6 |
Выбором |
Двоичный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
6 |
Выбором |
Двоичный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
6 |
Выбором |
Двоичный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
6 |
Выбором |
Двоичный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
6 |
Выбором |
Двоичный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
6 |
Выбором |
Двоичный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
6 |
Выбором |
Двоичный |
|
|
элементы, присутствующие в обоих массивах А и В |
7 |
Вставками |
Двоичный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
7 |
Вставками |
Двоичный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
7 |
Вставками |
Двоичный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
7 |
Вставками |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
7 |
Вставками |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
7 |
Вставками |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
7 |
Вставками |
Двоичный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
7 |
Вставками |
Двоичный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
7 |
Вставками |
Двоичный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
7 |
Вставками |
Двоичный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
7 |
Вставками |
Двоичный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
7 |
Вставками |
Двоичный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
7 |
Вставками |
Двоичный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
7 |
Вставками |
Двоичный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
7 |
Вставками |
Двоичный |
|
|
элементы, присутствующие в обоих массивах А и В |
8 |
Подсчетом |
Двоичный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
8 |
Подсчетом |
Двоичный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
8 |
Подсчетом |
Двоичный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
8 |
Подсчетом |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
8 |
Подсчетом |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
8 |
Подсчетом |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
8 |
Подсчетом |
Двоичный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
8 |
Подсчетом |
Двоичный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
8 |
Подсчетом |
Двоичный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
8 |
Подсчетом |
Двоичный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
8 |
Подсчетом |
Двоичный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
8 |
Подсчетом |
Двоичный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
8 |
Подсчетом |
Двоичный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
8 |
Подсчетом |
Двоичный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
8 |
Подсчетом |
Двоичный |
|
|
элементы, присутствующие в обоих массивах А и В |
9 |
Слиянием |
Линейный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
9 |
Слиянием |
Линейный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
9 |
Слиянием |
Линейный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
9 |
Слиянием |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
9 |
Слиянием |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
9 |
Слиянием |
Линейный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
9 |
Слиянием |
Линейный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
9 |
Слиянием |
Линейный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
9 |
Слиянием |
Линейный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
9 |
Слиянием |
Линейный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
9 |
Слиянием |
Линейный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
9 |
Слиянием |
Линейный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
9 |
Слиянием |
Линейный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
9 |
Слиянием |
Линейный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
9 |
Слиянием |
Линейный |
|
|
элементы, присутствующие в обоих массивах А и В |
10 |
Слиянием |
Двоичный |
|
|
элементы, которые есть только в массиве А или только в массиве В |
10 |
Слиянием |
Двоичный |
|
|
элементы, которые присутствуют в массиве А, но отсутствуют в массиве В |
10 |
Слиянием |
Двоичный |
|
|
элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах |
10 |
Слиянием |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В |
10 |
Слиянием |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В |
10 |
Слиянием |
Двоичный |
|
|
элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) |
10 |
Слиянием |
Двоичный |
|
|
элементы массива А, повторяющиеся в массиве В несколько раз |
10 |
Слиянием |
Двоичный |
|
|
элементы присутствующие в обоих массивах А и В в одном экземпляре |
10 |
Слиянием |
Двоичный |
|
|
элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В |
10 |
Слиянием |
Двоичный |
|
|
повторяющиеся элементы массива А, которые есть в массиве В |
10 |
Слиянием |
Двоичный |
|
|
повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре |
10 |
Слиянием |
Двоичный |
|
|
неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах |
10 |
Слиянием |
Двоичный |
|
|
элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах |
10 |
Слиянием |
Двоичный |
|
|
повторяющиеся элементы массива А, которых нет в массиве В |
10 |
Слиянием |
Двоичный |