Файл: Учебное пособие по изучению языка программировани Python Л. Самыкбаева, А. Беляев, А. Палитаев, И. Ташиев, С. Маматов.pdf

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PY THON
64
a =
range
(1, 20)
m = a[0]
for
i
in
range
(1, 20):
if
a[i] > m:
m = a[i]
print
(m)
Вот еще один вариант:
a =
range
(1, 20)
m = a[0]
for
x
in
a:
if
x > m:
m = x
print
(m)
Он отличается тем, что не использует переменную-индекс, но зато дважды просматривается элемент a[0] (второй раз – в цикле, где выполняется пере- бор всех элементов).
Поскольку операции поиска максимального и минимального элементов нужны очень часто, в Python есть соответствующие встроенные функции
max() и min():
a =
range
(1,20)
m =
max
(a)
print
(m)
Модификация массива
Для работы с массивами и изменения в них данных в Python есть множе- ство различных функций, например:

65
А ЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PY THON
66
Рассмотрим более подробно некоторые из них: реверс массива, сдвиг эле- ментов массива и отбор нужных элементов.
Реверс массива
Реверс массива (reverse) – это перестановка его элементов в обратном по- рядке: первый элемент становится последним, а последний – первым.
Индекс элементов массива в Python начинаются с 0. Поэтому, если общее количество элементов равно N, то противоположный для i элемент нахо- дится по формуле:

N - i - 1. Например (см.таблицу ниже), чтобы найти ин- декс элемента, который заменит элемент под индексом 2, вычисляем по формуле:
N i
9 – 2 – 1 = 6
Элемент под индексом 2 должен поменяться местами с элементом под индексом 6.
Чтобы найти вторую пару элемента, мы просматриваем индексы только первой половины массива. Это значит, что цикл нужно остановить на сере- дине массива:
a = [16, 29, -5, -11, 23, 14, -7, 23, 18]
n =
len
(a)
#вычисляем количество элементов в массиве
for
i
in
range
(n//2):
#только индексы первой половины массива
a[i], a[n-i-1] = a[n-i-1],
a[i]
#переставляем элементы
print
(a)
>>>
[18, 23, -7, 14, 23, -11, -5,
29, 16]
Операция реверс массива может быть выполнена и с помощью стандартного метода reverse():
a.reverse ()
Значения индексов в Python могут быть отрицательными.
В этом случае нумерация бу- дет идти с конца. Например, индекс самого последнего элемента массива равен -1, предпоследнего -2 и т.д.
ЗАПОМНИ

67
А ЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ
Сдвиг элементов массива
При удалении и вставке элементов необходимо выполнять сдвиг части или всех элементов массива в ту или другую сторону. Массив часто рису- ют в виде таблицы, где первый элемент расположен слева. Поэтому сдвиг влево – это перемещение всех элементов на одну ячейку, при котором a[1]
переходит на место a[0], a[2] – на место a[1] и т.д.
Последний элемент остается на своем месте, то есть дублируется, посколь- ку новое значение для него взять неоткуда – массив кончился.
Запишем алгоритм:
a = [16, 29, -5, -11, 23, 14, -7, 23, 18]
n =
len
(a)
for
i i
n
range
(n-1):
a[i] = a[i+1]
print
(a)
>>>
[
29, -5, -11, 23, 14, -7, 23, 18, 18]
Как видим, первый элемент пропал, а последний – повторился 2 раза. Мож- но старое значение первого элемента записать на место последнего. Такой сдвиг называется циклическим. Для этого предварительно (до начала цик- ла) первый элемент нужно запомнить во вспомогательной переменной (с), а после завершения цикла записать его в последнюю ячейку массива:
a = [16, 29, -5, -11, 23, 14, -7, 23, 18]
n =
len
(a)
c = a[0]
for
i
in
range
(n-1):
a[i] = a[i+1]
a[n-1] = c
print
(a)
>>>
[29, -5, -11, 23, 14, -7, 23, 18, 16]
Обратите внимание, что цикл заканчивается при a = [n-1], чтобы не было вы- хода за границы массива, то есть обращения к несуще- ствующему элементу a[n].

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PY THON
68
Можно выполнить сдвиг, используя встроенные возможности Python:
a = a[1:n] + [a[0]]
Здесь первый элемент a[0] ставится в конец к обрезанному массиву a[1:n], который теперь начинается не с нуля, а с единицы.
На рисунке справа мы видим, что срез a[0:2] включает все элементы между 0 и 2, то есть элементы a[0] и a[1].
Отбор нужных элементов
Требуется отобрать все элементы массива a, удовлетворяющие некоторому условию, в новый массив b. Для этого перебираем все элементы исходного массива и, если очередной элемент нам подходит, добавляем его в новый мас- сив, используя второй счетчик. Н-р, соберем во второй список четные числа:
a = [16, 29, -5, -11, 23, 14, -7, 23, 18]
b = []
for
x
in
a:
if
x % 2 == 0:
b.append(x)
print
(b)
>>>
[16, 14, 18]
Второй вариант решения – использование генератора с условием
a = [16, 29, -5, -11, 23, 14, -7, 23, 18]
b = [x
for
x
in
a
if
x % 2 == 0]
print
(b)
Здесь в новый список b отбираются только элементы, делящиеся на 2.
КОМПЬЮТЕРНЫЙ ПРАКТИКУМ:
1) Заполните массив случайными числами в интервале (0,20). Вве­
дите число x и найдите все значения, равные x.
2) Дан одномерный массив числовых значений, насчитывающий n элементов. Выполните перемещение элементов массива по кругу вправо, т.е. a(1) –> a(2); a(2) –> a(3); ... a(n) –> a(1).

69
СОР ТИРОВК А СПИСКОВ
16. Тема:
Сортировка списков
Часто для того чтобы облегчить поиск нужной информации, мы пользуемся сортировкой. Например, сортировка слов по алфавиту облегчает поиск слова в словаре.
В программировании сортировка – это перестановка элементов массива в заданном порядке.
Порядок сортировки может быть любым: для чисел обычно рассматривают сортировку по возрастанию (или убыванию) значений. Например, при сор- тировке по возрастанию из одномерного массива [3 1 0 5 2 7] получается массив [0 1 2 3 5 7]. Символьные данные обычно сортируются в алфавитном порядке.
Было придумано множество способов сортировки. В целом их можно раз- делить на две группы: 1) простые, но медленно работающие (на больших массивах) и 2) сложные, но быстрые.
Рассмотрим один из наиболее наглядных методов сортировки – «метод пузырька».
Метод пузырька (сортировка обменами)
Название этого метода произошло от известного физического явления – пузырек воздуха в воде поднимается вверх. Для сортировки массива таким способом необходимо справа налево пройтись по массиву, попарно срав- нивая соседние элементы, и в том случае, когда левый больше правого, менять их местами. Так самые «тяжелые» элементы падают на дно, а самые
«легкие» (минимальные) элементы поднимаются наверх (к началу массива) подобно пузырькам воздуха.
Далее так же рассматри- ваем следующую пару элементов от конца и т.д. (см. рисунок).

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PY THON
70
Когда мы обработали пару (a[0], a[1]), минимальный элемент стоит на месте a[0]. Это значит, что на следующих этапах его можно не рассматривать. Пер- вый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так:
для i от n-2 до 0 шаг -1
if (a[j] > a[j+1])
поменять местами a[j] и a[j+1]
Переменная i хранит индекс ячейки, в которую записывается минимальный элемент. Сначала это будет первая ячейка. Переменная j используется для обращения к текущим сравниваемым ячейкам массива.
За один проход такой цикл ставит на место один элемент. Чтобы «подтя- нуть» второй элемент, нужно написать еще один почти такой же цикл, кото- рый будет отличаться только конечным значением i в заголовке цикла. Так как верхний элемент уже стоит на месте, его не нужно трогать:
for
i
in
range
(n-1):
#количество переходов
for
j
in
range
(n-i-1):
if
a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
Таких циклов нужно сделать n-1 – на 1 меньше, чем количество элементов массива. Почему не n? Дело в том, что если n-1 элементов поставлены на свои места, то оставшийся автоматически встает на свое место – другого места нет.
Запишем полную программу сортировки методом пузырька:
from
random
import
randint
n = 10
a = [randint (1,99)
for
n
in
range
(n)]
print
(a)
for
i
in
range
(n-1):
#кол-во проходов по списку
for
j
in
range
(n-i-1):
#кол-во
сравнений
уменьшается
на
величину
i
if
a [j]
> a [j+1]:
#вложенный
цикл
сравнивает
эл-т
j
c
j+1
a[j], a [j+1] = a[j+1], a[j]
#при необходимости
меняет местами
print
(a)
>>>
[5, 84, 90, 37, 30, 32, 29, 62, 17, 99]
[5, 17, 29, 30, 32, 37, 62, 84, 90, 99]

71
СОР ТИРОВК А СПИСКОВ
Метод выбора
Еще один популярный и простой метод сортировки – метод выбора. Сна- чала просматривается весь массив, находится минимальный элемент и переставляется в самое начало массива. Во втором проходе, среди всех оставшихся, то есть со второго по последний элемент, снова находится наи- меньший элемент и переставляется местом со 2-м. Далее среди элементов, начиная с 3-го, также находится наименьший и меняется с 3-м и так далее до (n-1)-го элемента.
Запишем алгоритм для сортировки списка методом выбора, где перемен- ная i хранит индекс ячейки, в которую записывается минимальный элемент, а переменная j – просматриваемый элемент:
for
i
in
range
(n-1):
n_min = i
for
j
in
range
(i+1,n):
if
a[j] < a[n_min]:
n_min = j
if
i != n_min:
a[i], a[n_min] = a[n_min], a[i]
Здесь перестановка происходит только тогда, когда найденный минималь- ный элемент стоит не на своем месте, то есть i != n_min. Поскольку поиск номера минимального элемента выполняется в цикле, этот алгоритм сор- тировки также представляет собой вложенный цикл.
«Быстрая сортировка» или quicksort
Пузырьковая сортировка и метод выбора работают медленно для больших массивов данных (более 10000 элементов). Поэтому для сортировки боль- ших массивов часто используется рекурсивный алгоритм «быстрой сорти- ровки» (англ. quicksort).
Идея такой сортировки состоит в том, что сначала массив разбивается где-то посередине, затем из элементов левой части выбираются те, кото- рые больше или равны значению «среднего элемента» и переставляются в правую часть. Далее левая и правая части рассматриваются как отдельные массивы и снова делятся на два.

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PY THON
72
Чтобы понять сущность метода, рассмотрим пример. Пусть задан массив:
Выберем в качестве X средний элемент массива, то есть 67. Найдем первый слева элемент массива, который больше или равен X и должен стоять во второй части. Это число 78. Обозначим индекс этого элемента через L. Те- перь находим самый правый элемент, который меньше X и должен стоять в первой части. Это число 34. Обозначим его индекс через R.
Теперь поменяем местами два этих элемента. Сдвигая переменную L впра- во, а R – влево, находим следующую пару, которую надо переставить. Это числа 82 и 44.
Следующая пара элементов для перестановки – числа 67 и 55.
После этой перестановки дальнейший поиск приводит к тому, что перемен- ная L становится больше R, то есть массив разбит на две части. В результате все элементы массива, расположенные левее A[L], меньше или равны X, а все правее A[R] – больше или равны X.
Таким образом, сортировка исходного массива свелась к двум сортиров- кам частей массива, то есть к двум задачам того же типа, но меньшего размера. Теперь нужно применить тот же алгоритм к двум полученным частям массива: первая часть – с 1-го до R-го элемента, вторая часть – с L-го до последнего элемента.
Как мы уже говорили, скорость сортировки важна при работе с большими массивами. Ниже в таблице сравнивается время сортировки (в секундах)

73
СОР ТИРОВК А СПИСКОВ
массивов разного размера, заполненных случайными значениями, с ис- пользованием трех изученных алгоритмов.
Как видно из таблицы, при обработке массива, к примеру, с 15 тысячами элементов, быстрая сортировка работает в 500 раз быстрее, чем при мето- де пузырька.
Из предыдущей темы мы также знаем, что в Python есть встроенная функция для сортировки массивов sorted, которая использует гибридный алгоритм
timesort и легко справляется с обработкой большинства известных данных.
Необходимо также помнить, что при записи:
a.sort ()
#сортируется сам список a.
b = sorted (a)
#в массив b переносится отсортированный в по-
рядке возрастания массив a.
По умолчанию сортировка выполняется по возрастанию или точнее «неу- быванию», когда каждый следующий элемент больше или равен предыду- щему. Для того чтобы отсортировать массив по убыванию (невозрастанию – каждый следующий элемент меньше или равен предыдущему), нужно в функции сортировки указать reverse = True:
b = sorted (a, reverse =
True
)
#или
a.sort (reverse =
True
)
КОМПЬЮТЕРНЫЙ ПРАКТИКУМ:
1) Дан одномерный массив числовых значений, насчитывающий n элементов. Из элементов исходного массива построить два новых. В первый должны входить только числа, которые делятся на 3, а во второй числа, которые делятся на 5.
2) Продолжите программу из первого вопроса и допишите алго­
ритм, который сортирует числа, делящиеся на 3 по возраста­
нию, а все числа делящиеся на 5 – по убыванию.