2.3. Типовые алгоритмы обработки списков

Типовые алгоритмы можно подразделить на алгоритмы обработки списков, алгоритмы поиска и алгоритмы сортировки. С некоторыми вы уже познакомились в предыдущем разделе.

Обработку - в студию!

Мы пробежимся по основным задачам в обработке массивов. Над ними, обычно, надстраиваются уже более сложные варианты.

Суммирование двух массивов одинакового размера

Дано: список A = (a1, a2, ..., an), список B = (b1,b2,...,bn).
Сформировать: список C =(c1, c2, ..., cn), где ci = ai + bi; i = 1, 2, ..., n.
Решение: Задача сводиться к организации цикла, в котором выполняется операция.
Пример:

A=[1,2,3]
B=[4,5,6]
C=[]
for i in range(3):
   C.append(A[i]+B[i])
print(C)

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

Суммирование двух списоков одинакового размера

Дано: список A = (a1, a2, ..., an)
Определить: сумму элементов.
Пример:

res=0
A=[1,2,3]
for i in range(3):
   res=res+A[i]
print(res)

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

Условная обработка

Часто необходимо найти определённый элемент в списке и выпонить какое-то действие. Для этого используется просто комбинация цикла и условия. Например для определения минимального элемента в списке:

A=[3,2,1]
min=A[0]
for i in range(3):
   if min < A[i]:
       min = A[i]
print(min)

Важно помнить, что для изменения элемента в списке обязательно нужно использовать индекс.

Как искать то, что не терял

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

A=['one','two','three']
i=A.index('two')
print(i)

Любите ванну с пузырьками?

Сортировка в былые времена - дело хлопопотное. Существует ряд алгоритмов сортировки более эффективных в завивисимости от объема. Взгляните на код самой популярной сортировки - методом пузырька. На многих собеседованиях просят отсортировать именно так:

#функция пузырьковой сортировки
def bubble_sort(arr): 
    n = len(arr) 
    #Обходим все элементы, кроме последнего, он нам не нужен
    for i in range(n-1):  
        # Последние i элементов уже на своих местах 
        for j in range(0, n-i-1): 
            # Меняем местами если найденный элемент больше предыдущего
            if arr[j] > arr[j+1]: 
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp

#тестирование функции пузырька
arr = [64, 34, 25, 12, 22, 11, 90] 

bubble_sort(arr) 

print ("Sorted array is: " + str(arr)) 

Для большинства задач, конечно, лучше использовать встроенную функцию sort для списка.

Краткое содержание

- Со списками типовыми алгоритмами считается обработка, поиск и сортировка.
- Обработка списка выполняется с применением цикла по всем элементам и условных конструкций.
- Для поиска лучше пользоваться встроенными методами, такими как index
- Сортировку следует выполнять встроенной функцией sort()

Самостоятельная работа

Изучите сортировку с ключем на сайте habr.

Задачи