Методы split и join для списка строк в Python

Если элементы списка вводяться в одной строке, разделенные пробелами, то функция input() не поможет разделить строку на слова.

В этом случае строку можно считать функцией input(), после этого использовать метод строки split(), возвращающий список строк, разрезав исходную строку на части по пробелам. Пример:

A = input().split()

Если при запуске этой программы ввести строку 1 2 3, то список A будет равен [‘1’, ‘2’, ‘3’]. Обратите внимание, что список будет состоять из строк, а не из чисел. Если хочется получить список именно из чисел, то можно затем элементы списка по одному преобразовать в числа:

for i in range(len(A)):

A[i] = int(A[i])

Используя функции языка map и list то же самое можно сделать в одну строку:

A = list(map(int, input().split()))

Если нужно считать список действительных чисел, то нужно заменить тип int на тип float.

У метода split есть необязательный параметр, который определяет, какая строка будет использоваться в качестве разделителя между элементами списка. Например, метод split(‘.’) вернет список, полученный разрезанием исходной строки по символам ‘.’.
Используя “обратные” методы можно вывести список при помощи однострочной команды. Для этого используется метод строки join. У этого метода один параметр: список строк. В результате получается строка, полученная соединением элементов списка (которые переданы в качестве параметра) в одну строку, при этом между элементами списка вставляется разделитель, равный той строке, к которой применяется метод. Например, программа

A = ['red', 'green', 'blue']

print(' '.join(A))

print(''.join(A))

print('***'.join(A))

выведет строки ‘red green blue’, redgreenblue и red***green***blue.

Если же список состоит из чисел, то придется использовать еще и функцию map. То есть вывести элементы списка чисел, разделяя их пробелами, можно так:

print(' '.join(map(str, A)))

Списки в Python

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

Раньше мы сталкивались с задачей обработки элементов последовательности, например, вычисляя наибольший элемент последовательности. Но при этом мы не сохраняли всю последовательность в памяти компьютера, однако, во многих задачах нужно именно сохранять всю последовательность, например, если бы нам требовалось вывести все элементы последовательности в возрастающем порядке (“отсортировать последовательность”).

Для хранения таких данных можно использовать структуру данных, называемую в Питоне список (в большинстве же языков программирования используется другой термин “массив”). Список представляет собой последовательность элементов, пронумерованных от 0, как символы в строке. Список можно задать перечислением элементов списка в квадратных скобках, например, список можно задать так:

Primes = [2, 3, 5, 7, 11, 13]

Rainbow = ['Red', 'Orange', 'Yellow', 'Green', 'Blue', 'Indigo', 'Violet']

В списке Primes — 6 элементов, а именно,

Primes[0] == 2, Primes[1] == 3, Primes[2] == 5, Primes[3] == 7, Primes[4] == 11, Primes[5] == 13.

Список Rainbow состоит из 7 элементов, каждый из которых является строкой.

Также как и символы строки, элементы списка можно индексировать отрицательными числами с конца, например,

Primes[-1] == 13, Primes[-6] == 2.

Длину списка, то есть количество элементов в нем, можно узнать при помощи функции len, например, len(A) == 6.

Рассмотрим несколько способов создания и считывания списков. Прежде всего можно создать пустой список (не содержащий элементов, длины 0), в конец списка можно добавлять элементы при помощи метода append. Например, если программа получает на вход количество элементов в списке n, а потом n элементов списка по одному в отдельной строке, то организовать считывание списка можно так:

A = []

for i in range(int(input()):

A.append(int(input())

В этом примере создается пустой список, далее считывается количество элементов в списке, затем по одному считываются элементы списка и добавляются в его конец.

Для списков целиком определены следующие операции: конкатенация списков (добавление одного списка в конец другого) и повторение списков (умножение списка на число). Например:

A = [1, 2, 3]

B = [4, 5]

C = A + B

D = B * 3

В результате список C будет равен [1, 2, 3, 4, 5], а список D будет равен [4, 5, 4, 5, 4, 5]. Это позволяет по-другому организовать процесс считывания списков: сначала считать размер списка и создать список из нужного числа элементов, затем организовать цикл по переменной i начиная с числа 0 и внутри цикла считывается i-й элемент списка:

A = [0] * int(input())

for i in range(len(A)):

A[i] = int(input())

Вывести элементы списка A можно одной инструкцией print(A), при этом будут выведены квадратные скобки вокруг элементов списка и запятые между элементами списка. Такой вывод неудобен, чаще требуется просто вывести все элементы списка в одну строку или по одному элементу в строке. Приведем два примера, также отличающиеся организацией цикла:

for i in range(len(A)):

print(A[i])

Здесь в цикле меняется индекс элемента i, затем выводится элемент списка с индексом i.

for elem in A:

print(elem, end = ' ')

В этом примере элементы списка выводятся в одну строку, разделенные пробелом, при этом в цикле меняется не индекс элемента списка, а само значение переменной (например, в цикле for elem in [‘red’, ‘green’, ‘blue’] переменная elem будет последовательно принимать значения ‘red’, ‘green’, ‘blue’.

Обращение массива

Для того, чтобы переставить элементы массива A длины N в обратном порядке, нужно разбить из на пары первый--последний, второй--предпоследний и т. д. и поменять местами элементы в каждой паре. При этом нужно обратить внимание, что пар не N, а [N/2].

ПРИМЕР КОДА НА ЯЗЫКЕ PYTHON

for i in range(len(A) // 2):
A[i], A[N - i - 1] = A[N - i - 1], A[i]

 

На языке питон можно сделать то же самое короче, воспользовавшись срезами списков:
A = A[::-1]

Циклический сдвиг в массиве

Сдвиг на k элементов влево:

A = A[k:] + A[:k]

Сдвиг на k элементов вправо:

A = A[-k:] + A[:-k]

 

Такой сдвиг требует дополнительную память для хранения срезов, пропорциональную длине массива.

Срезы списков в Python

Со списками, так же как и со строками, можно делать срезы. А именно:

A[i:j] срез из j-i элементов A[i], A[i+1], …, A[j-1].

A[i:j:-1] срез из i-j элементов A[i], A[i-1], …, A[j+1] (то есть меняется порядок элементов).

A[i:j:k] срез с шагом k: A[i], A[i+k], A[i+2*k],…. Если значение k<0, то элементы идут в противоположном порядке.

Каждое из чисел i или j может отсутствовать, что означает “начало строки” или “конец строки”

Списки, в отличии от строк, являются изменяемыми объектами: можно отдельному элементу списка присвоить новое значение. Но можно менять и целиком срезы. Например:

A = [1, 2, 3, 4, 5]

A[2:4] = [7, 8, 9]

Получится список, у которого вместо двух элементов среза A[2:4] вставлен новый список уже из трех элементов. Теперь список стал равен [1, 2, 3, 7, 8, 9, 5].

A = [1, 2, 3, 4, 5, 6, 7]

A[::-2] = [10, 20, 30, 40]

Получится список [40, 2, 30, 4, 20, 6, 10]. Здесь A[::-2] — это список из элементов A[-1], A[-3], A[-5], A[-7], которым присваиваются значения 10, 20, 30, 40 соответственно.

Если не непрерывному срезу (то есть срезу с шагом k, отличному от 1), присвоить новое значение, то количество элементов в старом и новом срезе обязательно должно совпадать, в противном случае произойдет ошибка ValueError.

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

Обратите внимание, A[i] — это операция обращения к одному элементу списка, а не к срезу!

Операции со списками в Python

x in A	Проверить, содержится ли элемент в списке. Возвращает True или False
x not in A	То же самое, что not(x in A)
min(A)	Наименьший элемент списка
max(A)	Наибольший элемент списка
A.index(x)	Индекс первого вхождения элемента x в список, при его отсутствии генерирует исключение ValueError
A.count(x)	Количество вхождений элемента x в список
A.sort()	Сортировка списка (меняет сам список, ничего не возвращает)
sum(A)	Возвращает сумму элементов в списке
A.append(x)	Добавить элемент x в конец списка
A.extend(L)	Добавить все элементы списка L в конец списка A

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

Сортировка массива выбором осуществляется так:

1. находим номер минимального значения в неотсортированной части массива;

2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);

3. продолжаем сортировку оставшегося списка, исключив из рассмотрения еще один элемент.

ПРИМЕР СОРТИРОВКИ ВЫБОРОМ МИНИМУМА НА СИ

void choiseSortFunction(double A[], size_t N)
{
for(size_t tmp_min_index = 0; tmp_min_index < N;
tmp_min_index++) {
//ищем минимум
for(size_t k = tmp_min_index + 1; k < N; k++) {
if (A[k] < A[tmp_min_index]) {
double min_value = A[k];
A[k] = A[tmp_min_index];
A[tmp_min_index] = min_value;
}
}
}
}

 

ПРИМЕР СОРТИРОВКИ ВЫБОРОМ МИНИМУМА НА PYTHON

def SelectionSort(A):
for i in range(0, len(A) - 1):
# Среди элементов A[i:] выбираем наименьший
# Сохраняем его индекс в переменной min_idx
min_idx = i
for j in range(i + 1, len(A)):
if A[j] < A[min_idx]:
min_idx = j
# Теперь поставим A[min_idx] на место A[i]
A[i], A[min_idx] = A[min_idx], A[i]

Можно модифицировать алгоритм — не сохранять индекс наименьшего из просмотренных элементов, а при просмотре элементов в срезе A[i:] обменивать очередной элемент A[j] местами с A[i], если A[j]<A[i]:

def SelectionSort(A):
for i in range(0, len(A) - 1):
for j in range(i + 1, len(A)):
if A[j] < A[i]:
A[i], A[j] = A[j], A[i]

 

ПРИМЕР СОРТИРОВКИ ВЫБОРОМ МИНИМУМА НА PASCAL

var

a: array[1..1000] of longint;

tmp_num, i, j, n, tmp: longint;

begin

readln(n);

for i:= 1 to n do

read(a[i]);

for i:= 1 to n - 1 do begin // n-1 раз проходимся по массиву, ставя "на место" очередной элемент

tmp_num:= i; //номер минимального среди элементов с индексами от i до n

for j:= i + 1 to n do

if a[j] < a[tmp_num] then

tmp_num:= i;

swap(a[i], a[tmp_num]); //ставим найденный минимальный "на место"

end;

for i:= 1 to n do

write(a[i], ' ');

end.

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

Сортировка вставками использует такой инвариант: первые элементы списка, то есть срез A[:i] уже отсортирован. А вот как устроен алгоритм добавления i-го элемента к уже отсортированной части. Здесь берется элемент A[i] и добавляется к уже отсортированной части списка. Например, пусть i = 5 и срез A[:i] = [1, 4, 6, 8, 8], а значение A[i] == 5. Тогда элемент A[i] == 5 нужно поставить после элемента A[1] == 4, а все элементы, которые больше 5, сдвинуть вправо на 1. Получится cрез A[:i + 1] = [1, 4, 5, 6, 8, 8]. Таким образом, при вставке элемента A[i] в срез A[:i] так, чтобы в результате получился упорядоченный срез, все элементы, которые больше A[i] будут двигаться вправо на одну позицию. А в освободившуюся позицию и будет вставлен элемент A[i].
При этом значение A[i] нужно сохранить в переменной, т. к. на место элемента A[i], возможно, будет записан элемент A[i – 1].

Получаем следующий алгоритм:

def InsertionSort(A):
for i in range(1, len(A)):
# В new_elem сохранили значение A[i]
new_elem = A[i]
# Начиная с элемента A[i - 1]
j = i - 1
# все элементы, которые больше new_elem
while j >= 0 and A[j] > new_elem:
# сдвигаем вправо на 1
A[j + 1] = A[j]
j -= 1
# На свободное место записываем new_elem
A[j + 1] = new_elem

Посчитаем сложность алгоритма сортировки вставками. Следует отметить, что если массив уже упорядочен, то все элементы останутся на своем месте и вложенный цикл не будет выполнен ни разу. В этом случае сложность алгоритма сортировки вставками — линейная, т. е. O(n). Аналогично, если массив «почти упорядочен», то есть для превращения его в упорядоченный нужно поменять местами несколько соседних или близких элементов, то сложность также будет линейной.

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

Перед тем, как излагать этот метод сортировки, внимательно прислушаемся к одному небольшому примечанию. Массив упорядочен по возрастанию, если меньшие числа в нем стоят раньше больших. Чем меньше число, тем раньше оно должно стоять в массиве, чем больше число — тем позже. Другими словами, чем больше число, тем больше его номер в массиве (индекс).

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

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

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

4 3 5 8 6 2

Двигаться будем слева направо (хотя это не принципиально).

Шаг 1. Сравним 4 и 3. Число 4 больше (а значит должно стоять правее) - меняем местами эти элементы. Новый массив:

3 4 5 8 6 2

Независимо от того, меняли мы местами элементы или нет — просто переходим к следующей паре.

Шаг 2. Сравним 4 и 5. Числа в паре стоят в «правильном» порядке — меньшее левее большего. Ничего не делаем с этими элементами. Массив остается:

4 3 5 8 6 2

Переходим к следующей паре.

Шаг 3. Сравниваем 5 и 8. Эти числа также стоят в «правильном» порядке, поэтому массив не изменяется:

4 3 5 8 6 2

Берем следующую пару.

Шаг 4. Сравниваем 8 и 6. Здесь большее число стоит левее меньшего, поэтому меняем числа местами, получаем новый массив:

4 3 5 6 8 2

Переходим к следующей паре.

Шаг 5. Сравниваем 8 и 2.Опять большее число левее меньшего — переставляем числа.

4 3 5 6 2 8

Пары закончились.

Правда, массив пока мало похож на отсортированный. Однако, можно сделать одно важное наблюдение: после полного прохода по массиву хотя бы одно число (а именно – самое большое) будет поставлено на свое место. Именно поэтому этот метод носит название «метод пузырька» или просто «пузырек». Наибольшее число, как пузырек из глубины стакана с газировкой, «всплывает» на поверхность (на последнее место в массиве) и остается там.

Теперь, если мы сделаем второй проход по массиву, то еще одно число встанет на свое место (а может быть и не одно, но об этом чуть позже). Значит, чтобы гарантированно получить отсортированный массив, надо сделать столько проходов, сколько элементов в массиве.

Впрочем, достаточно сделать N−1 проход, потому что когда все числа кроме одного будут на своих местах, последнее тоже само собой окажется на своем месте.

Итак, мы выяснили, что для успешной сортировки надо сделать N−1 проход, по N−1 сравнению на каждом проходе. Таким образом структура программы — двойной цикл. Внешний цикл — по количеству проходов, внутренний — по тем парам элементов, которые мы сравниваем.