СОРТИРОВКА, ДВУМЕРНЫЕ СПИСКИ, РЕКУРСИЯ.

Урок 5

Сортировка.

В языке Python сортировка производится встроенным методом списков sort() или функцией sorted().

Рассмотрим на примере сортировки через встроенный метод sort().

>>> a = [1,-45,3,2,100,-4]
>>> a.sort()
# получаем измененный список
[-45,-4,1,2,3,100]

Как мы можем увидеть сортировка идет по возрастанию.

Для сортировки кортежей используют функцию sorted()

>>> b = ("ab", "bc", "wd", "gf")
>>> sorted(b)
# на выходе получим упорядочный список
["ab","bc","gh","wd"]

Функция sorted() не меняет исходные коллекции b, она возвращает новый список с отсортированными данными. В то время как метод sort() для списка меняет этот список. Вот на это следует также обращать внимание. То есть, если нам нужно сохранить результат сортировки в переменной.

res = sorted(b)

И res будет ссылаться на список:

["ab","bc","gf","wd"]

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

a = [1,-45,3,2,100,-4,"b"]

Но если убрать последний элемент то все будет работать.

reverse = True/False этот параметр определяет порядок сортировки: по возрастанию (False) или по убыванию (True). По умолчанию стоит значение reverse=False.

>>>a = sorted(a, reverse=True)
[100,3,2,1,-4,-45]

Мы получили сортировку по убыванию и тоже самое с методом sort().

Сортировка пузырьком - при этом методе осуществляется сравнение соседних элементов. Они меняются местами в том случае, если порядок неправильный. Так продолжается до тех пор, пока все элементы не расположатся в нужном порядке.

Пример такой сортировки:

>>>a=[4,9,0,13,17,23,4,1,0]
>>>n=len(a)
>>>for i in range(n):
       for j in range(n-i-1): #убираем последние значение после прохода по циклу
          if a[j]>a[j+]:
              a[j],a[j+1] = a[j+1], a[j] # замена местами
print(a)

Сортировка через функцию:

def cmp(x):
     return x%10
a=[4,9,0,13,17,23,4,1,0]
print(a)
a.sort(key=cmp)
print(a)

Key=cmp - выполняем сортировку по значению возвращения функции то есть ссылается на return

Return - это оператор который используется для возврата значения из функции.

Во время сортировки используются такие функции как:

min() - вычисляет минимальное значение

max() - вычисляет максимальное значение

Пример сортировки с данными функциями:

def proz(x):
     return(x%10 * x//10) # перемножаем первые и вторые цифры
tmp=[12,34,35,12,68,29]
# Сортировка по произведения первой и второй цифры
tmp.sort(key=proz)
print(tmp)
print(max(tmp))

Что такое Кортеж?

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

Кортежи создают с помощью круглых скобок ().

a=(2,4,5,9)
len(a) #длина 
a.count(2) # кол-во одинаковых значений в кортеже

Существует функция tuple() она используется для конвертации данных в кортеж. Например, так можно превратить список в кортеж.

>>> a_list=[1,2,3,4,5]
>>> b_tuple=tuple(a_list)
>>> print(type(b_tuple))

Двумерные списки.

В Python это можно представить в виде списка, элементы которого являются другими списками.

Приведем пример двумерных списков:

tmp=[[1,2,3],[4,5,6],[6,7,8]]
tmp[0][1]=10
print(tmp[0][1]

tmp[0][1] - первое значение показывает в какой список мы будем обращаться, а второе значение показывает к какому значению мы будем обращаться в этом списке.

Можно узнать кол-во значений в списке

tmp=[[1,2,3],[4,5,6],[7,8,9]]
tmp[0]=[13,11,12,14]
print(len(tmp))
print(len(tmp[0])) # кол-во значений в списке

Сделаем таблицу дома с этажами:

def pl(t):
   for i in t:
      print(*i)
x=int(input())#Этажи
y=int(input())#Квартиры
house=[[0 for i in range(y)] for i in range(x)]
cnt=1
for i in range(-1,-x-1,-1):
    if i % 2 ==1:#Проверка на нечетность 
        for j in range(y):
           house[i][j]=cnt
           cnt+=1
    else:# Проверка на четность 
        for j in range(-1,-y-1,-1):
             house[i][j]=cnt
             cnt+=1
pl(house)

Вывод будет выглядеть следующем образом:

6 5 4
1 2 3

Рекурсия.

Рекурсивная функция - это та функция которая вызывает сама себя.

В качестве примера рассмотрим следующий код:

def Factorial_recursive(n):
    if n == 1:
       return n
    else:
        return n*factorial_recursive(n-1)
        

Из этого кода мы видим что с помощью рекурсии можно вычислить факториал числа n

Факториал числа n - это произведение всех натуральных чисел от 1 до n включительно

Так же стоит подметить что рекурсия имеет ограничение в 3000 слоев.