В ходе чтения статей про алгоритмы я натолкнулся на пост "Шпаргалка для технического собеседования" пользователя @Barrayar. Ознакомившись с оригинальной статьёй, я решил написать примеры для иллюстрации приведённых автором алгоритмов и структур данных. Что из этого получилось - читайте под катом. Все приведённые примеры рассчитаны на самых начинающих инженеров.

Оригинальная статья

Для начала импортируем некоторые библиотеки и создадим дата-сет из чисел от 0 до 100 в случайном порядке.

import time
import random

data_sorted = [i for i in range(0, 101)]
data = []
while True:
    if len(data_sorted) == 0:
        break
    how_long = len(data_sorted)
    index = random.randrange(0, how_long)
    data.append(data_sorted[index])
    data_sorted.pop(index)

Линейный массив.

#Линейный массив в python представлен структурой tuple (кортеж)
def line_array(data):
    array = tuple(data)
    print(array)

Динамический массив.

#Динамический массив в данном случае - список list
#data уже отвечает этому требованию
def dynamic_array(data):
    print(data)

Многомерный массив.

#Многомерный массив можно получить, переупаковав его элементы
#в подсписки заданной длины
def multidimensional_array(data):
    array = []
    box = []
    for i in data:
        if len(box) < 4:
            if i != data[-1]:
                box.append(i)
            else:
                box.append(i)
                while len(box) != 4:
                    box.append(None)
                array.append([i for i in box])
        else:
            box.append(i)
            array.append([i for i in box])
            box.clear()
    
    for i in array:
        print(i)

Двусвязанный список.

#Двусвязанный список характеризуется тем, что каждый его элемент
#ссылается на соседние; первый и последний элементы ссылаются на None
def doble_linked_list(data):
    d_l_s = {}
    for i in range(0, len(data)):
        if i == 0:
            d_l_s.update({data[i]: (None, data[i + 1])})
        elif i == len(data)-1:
            d_l_s.update({data[i]: (data[i - 1], None)})
        else:            
            d_l_s.update({data[i]: (data[i - 1], data[i + 1])})
    print(d_l_s)

Кольцевой связанный список.

#Кольцевой свзанный список похож на двусвязанный, но первый и последний элементы
#ссылаются друг на друга
def ring_linked_list(data):
    r_l_s = {}
    for i in range(0, len(data)):
        if i == 0:
            r_l_s.update({data[i]: (data[-1], data[i + 1])})
        elif i == len(data)-1:
            r_l_s.update({data[i]: (data[i - 1], data[0])})
        else:            
            r_l_s.update({data[i]: (data[i - 1], data[i + 1])})
    print(r_l_s)

Стек.

#Стек похож на итеративное прохождение по списку list
#но элемент на первой позиции всегда находится первым в очереди
#на загрузку и удаление
def stack(data):
    stack_massive = []
    for i in data:
        new_massive = [i]
        for j in stack_massive:
            new_massive.append(j)
        stack_massive = new_massive
    print(stack_massive)

Очередь.

#Очередь представлена обычным прохождением по списку
def turn(data):
    turn_massive = []
    for i in data:
        turn_massive.append(i)
    print(turn_massive)

Хеш-таблица.

#Хэш-таблица в python это словарь  
def hash_table(data):
    hash_massive = {i: i for i in data}
    print(hash_massive)

Двоичное дерево.

#Двоичное дерево можно сгенерировать в виде словаря
#в котором ключи являются номарами уровней, а значения - уровнями
#к этому дереву будут обращаться дальнейшие примеры
def binary_tree(data):
    level = 1
    full = []
    tree = []
    ext = {}
    count = 1
    for i in data:
        if len(tree) != level:
            tree.append(i)
            if i == data[-1]:
                while len(tree) != level:
                    tree.append(None)
        if len(tree) == level:
            ext.update({count: [i for i in tree]})
            tree.clear()
            level = level * 2
            count += 1
    print(ext)
    return ext

Поиск в ширину.

#Поиск в ширину выполняет поиск случайного элемента в дереве,
#созданном в предыдущем примере
#Сначала поиск выполняется среди всех значений на одном уровне,
#а потом, если искомое значение не обнаружено - переходит глубже
def width(ext, data):
    target = data[random.randrange(0, len(data))]
    for i in ext:
        count = 0
        for j in ext.get(i):
            if target == j:
                print(i, '-', count)
                break
            else:
                count += 1

Поиск в глубину.

#Поиск в ширину выпоняет поиск случайного элемента в дереве,
#созданном в предыдущем примере
#Поиск выполняется от корня до самой левой вершины, потом - до второй слева,
#и так далее
def width(ext, data):
    target = data[random.randrange(0, len(data))]
    for i in ext:
        count = 0
        for j in ext.get(i):
            if target == j:
                print(i, '-', count)
                break
            else:
                count += 1

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

#Сортировка слиянием требует рекурсивный вызов функций
def merge_sort(data):

    def merge(left, right):
        new_box = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                new_box.append(left[i])
                i += 1
            else:
                new_box.append(right[j])
                j += 1
        if i < len(left):
            new_box += left[i:]
        if j < len(right):
            new_box += right[j:]
        return new_box

    def sort(box):
        if len(box) == 1:
            return box
        mid = len(box) // 2
        left = sort(box[:mid])
        right = sort(box[mid:])
        return merge(left, right)
   
    print(sort(data))

Быстрая сортировка.

#Быстрая сортировка также связана с рекурсией
def quick_sort(data):
    def sort(box):
        if len(box) <= 1:
            return box
        mid = box[-1]
        left = list(filter(lambda x: x < mid, box))
        center = [i for i in box if i == mid]
        right = list(filter(lambda x: x > mid, box))
        return sort(left) + center + sort(right)
    print(sort(data))

Пузырьковая сортировка.

#Пузырьковая сортировка - один из самых простых алгоритмов сортировки
#Данный алгоритм не является эффективным и пригоден, в основном
#для учебных целей
def bubble_sort(data):
    count = 0
    while count < len(data):
        for i in reversed(range(count, len(data))):
            if data[i] < data[i-1]:
                data[i], data[i-1] = data[i-1], data[i]
        count += 1
    print(data)

Рекурсивный алгоритм.

#Рекурсивный алгоритм в python имеет ограниченную вложенность
#чтобы не возникало ошибки - нужно обработать исключение
def recursion():
    try:
        recursion()
    except RecursionError:
        pass

Итеративный алгоритм.

#Итеративный алгоритм - простое прохождение цикла for
def iter(data):
    for i in data:
        print(i)

Декоратор с таймером для анализа эффективности алгоритмов.

def start():
    time_1 = time.time()
    #line_array(data)
    #dynamic_array(data)
    #multidimensional_array(data)
    #doble_linked_list(data)
    #ring_linked_list(data)
    #stack(data)
    #turn(data)
    #hash_table(data)
    #binary_tree(data)
    #width(binary_tree(data), data)
    #depth(binary_tree(data), data)
    #merge_sort(data)
    #quick_sort(data)
    #bubble_sort(data)
    #recursion()
    #iter(data)
    time_2 = time.time()
    print(time_2 - time_1)


if __name__ == '__main__':
    start()