Примеры алгоритмов обработки массивов

Сортировка элементов в массиве

Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений. Например, массив X из n элементов будет отсортирован в порядке возрастания значений его элементов, если X₁ ≤ X₂ ≤...≤ X_n, и в порядке убывания, если X₁ ≥ X₂ ≥ ... ≥ X_n.

Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:

сортировка обменом;
сортировка выбором;
сортировка вставкой.

Представим, что нам необходимо разложить по порядку карты в колоде. Для сортировки карт обменом можно разложить карты на столе лицевой стороной вверх и менять местами те карты, которые расположены в неправильном порядке, делая это до тех пор, пока колода карт не станет упорядоченной.

Для сортировки выбором из разложенных на столе карт выбирают самую младшую (старшую) карту и держат ее в руках. Затем из оставшихся карт вновь выбрать наименьшую (наибольшую) по значению карту и помещают ее позади той карты, которая была выбрана первой. Этот процесс повторяется до тех пор, пока вся колода не окажется в руках. Поскольку каждый раз выбирается наименьшая (наибольшая) по значению карта из оставшихся на столе карт, по завершению такого процесса карты будут отсортированы по возрастанию (убыванию).

Для сортировки вставкой из колоды берут две карты и располагают их в необходимом порядке по отношению друг к другу. Каждая следующая карта, взятая из колоды, должна быть установлена на соответствующее место по отношению к уже упорядоченным картам.

Итак, решим следующую задачу. Задан массив Y из n целых чисел. Расположить элементы массива в порядке возрастания их значений.

Сортировка методом "пузырька"

Сортировка пузырьковым методом является наиболее известной. Ее популярность объясняется запоминающимся названием, которое происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень, и простотой алгоритма.

Сортировка методом "пузырька" использует метод обменной сортировки и основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Рассмотрим алгоритм пузырьковой сортировки более подробно.

Сравним первый элемент массива со вторым, если первый окажется больше второго, то поменяем их местами. Те же действия выполним для второго и третьего, третьего и четвертого, i-го и (i+ 1)-го, (n- 1)-го и n-го элементов. В результате этих действий самый большой элемент станет на последнее n-е место. Теперь повторим данный алгоритм сначала, но последний n-й элемент, рассматривать не будем, так как он уже занял свое место. После проведения данной операции самый большой элемент оставшегося массива станет на (n- 1)-е место. Так повторяем до тех пор, пока не упорядочим весь массив.

В табл.3.2 подробно расписан процесс упорядочивания элементов в массиве. Нетрудно заметить, что для преобразования массива, состоящего из n элементов, необходимо просмотреть его n- 1 раз, каждый раз уменьшая диапазон просмотра на один элемент. Блок-схема описанного алгоритма приведена на рис. 3.8. Обратите внимание на то, что для перестановки элементов (блок 4) используется буферная переменная b, в которой временно хранится значение элемента, подлежащего замене.

Таблица 3.2. Процесс упорядочивания элементов в массиве по возрастанию
Номер элемента	1	2	3	4	5
Исходный массив	7	3	5	4	2
Первый просмотр	3	5	4	2	7
Второй просмотр	3	4	2	5	7
Третий просмотр	3	2	4	5	7
Четвертый просмотр	2	3	4	5	7

Совет. Для перестановки элементов в массиве по убыванию их значений необходимо при сравнении элементов массива заменить знак > на <.


Рис. 3.8. Сортировка массива пузырьковым методом	Рис. 3.9. Сортировка массива выбором наибольшего элемента

Сортировка выбором

Алгоритм сортировки выбором приведен в виде блок-схемы на рис. 3.9. Найдем в массиве самый большой элемент (блоки 3-7) и поменяем его местами с последним элементом (блок 8). Повторим алгоритм поиска максимального элемента, уменьшив количество просматриваемых элементов на единицу (блок 9), и поменяем его местами с предпоследним элементом (блоки 3-7). Описанную выше операцию поиска проводим до полного упорядочивания элементов в массиве. Так как в блоке 9 происходит изменение переменной n, то в начале алгоритма ее значение необходимо сохранить (блок 1).

Совет. Для упорядочивания массива по убыванию необходимо перемещать минимальный элемент.

Сортировка вставкой

Сортировка вставкой заключается в том, что сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Четвертый элемент помещают в список из уже упорядоченных трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.

Прежде чем приступить к составлению блок-схемы рассмотрим следующий пример. Пусть известно, что в массиве из восьми элементов первые шесть уже упорядочены, а седьмой элемент нужно вставить между вторым и четвертым. Сохраним седьмой элемент во вспомогательной переменной, так как показано на рисунке 3.10, а на его место запишем шестой. Далее пятый переместим на место шестого, четвертый на место пятого, а третий на место четвертого, тем самым, выполнив сдвиг элементов массива на одну позицию вправо. Записав содержимое вспомогательной переменной в третью позицию, достигнем нужного результата.

Рис. 3.10. Процесс вставки элемента в массив

Составим блок-схему алгоритма (рис. 3.11), учитывая, что возможно описанные выше действия придется выполнить неоднократно.

Организуем цикл для просмотра всех элементов массива, начиная со второго (блок 4). Сохраним значение текущего i-го элемента во вспомогательной переменной X, так как оно может быть потеряно при сдвиге элементов (блок 5) и присвоим переменной j значение индекса предыдущего (i- 1)-го элемента массива (блок 6). Далее движемся по массиву влево в поисках элемента меньшего, чем текущий и пока он не найден сдвигаем элементы вправо на одну позицию. Для этого организуем цикл (блок 7), который прекратиться, как только будет найден элемент меньше текущего. Если такого элемента в массиве не найдется и переменная j станет равной нулю, то это будет означать, что достигнута левая граница массива, и текущий элемент необходимо установить в первую позицию. Смещение элементов массива вправо на одну позицию выполняется в блоке 8, а изменение счетчика j в блоке 9. Блок 10 выполняет вставку текущего элемента в соответствующую позицию.

Рис. 3.11. Сортировка массива вставкой

Удаление элемента из массива

Необходимо удалить из массива X, состоящего из n элементов, m-й по номеру элемент. Для этого достаточно записать элемент (m+ 1) на место элемента m , (m+ 2)- на место (m+ 1) и т.д., n - на место (n- 1) и при дальнейшей работе с этим массивом использовать n- 1 элемент (рис. 3.12).

Рис. 3.12. Процесс удаления элемента из массива

Алгоритм удаления из массива Х размерностью n элемента с номером m приведен на рис. 3.13.

Рис. 3.13 Алгоритм удаления элемента из массива

Примеры алгоритмов обработки массивов

ПРИМЕР 1. Дан массив А состоящий из k целых положительных чисел. Записать все четные по значению элементы массива А в массив В.

Решение задачи заключается в следующем. Последовательно перебираются элементы массива А. Если среди них находятся четные, то они записываются в массив В. На рисунке 3.14 видно, что первый четный элемент хранится в массиве А под номером три, второй и третий под номерами пять и шесть соответственно, а четвертый под номером восемь. В массиве В этим элементам присваиваются совершенно иные номера. Поэтому для их формирования необходимо определить дополнительную переменную. В блок-схеме приведенной на рисунке 3.15 роль такой переменной выполняет переменная m. Операция, выполняемая в блоке 2, означает, что в массиве может не быть искомых элементов. Если же условие в блоке 5 выполняется, то переменная m увеличивается на единицу, а значение элемента массива А записывается в массив В под номером m (блок 6). Условный блок 7 необходим для того, чтобы проверить выполнилось ли хотя бы раз условие поиска (блок 5).

Рис. 3.14 Процесс формирование массива В из элементов массива А

Рис. 3.15 Формирование массива В из соответствующих элементов массива А

ПРИМЕР 2. Задан массив Y из n целых чисел. Сформировать массив Z таким образом, чтобы в начале шли отрицательные элементы массива Y, затем положительные и, наконец, нулевые. Блок-схема представлена на рис. 3.16.

ПРИМЕР 3. Переписать элементы массива X в обратном порядке. Блок-схема представлена на рис. 3.17. Алгоритм состоит в следующем: меняем местами 1-й и n-й элементы, затем 2-й и n-1-й элементы, и т.д. до середины массива (элемент с номером i следует обменять с элементом n+ 1-i).

ПРИМЕР 4. Задан массив из n элементов. Сформировать массивы номеров положительных и отрицательных элементов. Блок-схема представлена на рис. 3.18.

Рис. 3.16. Алгоритм примера 3.2

Рис. 3.17. Фрагмент блок-схемы к примеру 3.3

Рис. 3.18. Алгоритм примера 3.4

ПРИМЕР 5. Удалить из массива X, состоящего из n элементов, первые четыре нулевых элемента.

Вначале количество нулевых элементов равно нулю (k=0). Последовательно перебираем все элементы массива. Если встречается нулевой элемент, то количество нулевых элементов увеличиваем на 1 (k=k+1). Если количество нулевых элементов меньше или равно 4, но удаляем очередной нулевой элемент, иначе аварийно выходим из цикла (встретился пятый нулевой элемент и дальнейшая обработка массива бесполезна). Блок-схема представлена на рис. 3.19.

ПРИМЕР 6. Массив целых чисел С состоит из N элементов, найти сумму простых чисел, входящих в него.

Идея алгоритма состоит в следующем. Сначала сумма равна 0. Последовательно перебираем все элементы, если очередной элемент простой, то добавляем его к сумме. Блок-схема алгоритма изображена на рис. 3.20.


Рис. 3.19. Алгоритм примера 3.5	Рис. 3.20. Алгоритм примера 3.6

ПРИМЕР 7. Определить есть ли в заданном массиве серии элементов, состоящих из знакочередующихся чисел (рис. 3.21). Если есть, то вывести на экран количество таких серий.

Рис. 3.21. Рисунок к примеру 3.7

На рис. 3.22 изображена блок-схема решения поставленной задачи.

Здесь переменная k - количество элементов, попадающих в серию, kol - количество знакочередующихся серий в массиве.

Дата добавления: 2021-01-20; просмотров: 988; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!