🫧 Принцип сортировки пузырьком (Bubble Sort)

🔜Сортировка пузырьком — это простой алгоритм сортировки, который многократно проходит по списку, сравнивая пары соседних элементов и меняя их местами, если они идут в неправильном порядке. Таким образом, большие элементы "всплывают" в конец списка, как пузырьки в воде.

📌 Подходит для:

🔵учебных и демонстрационных целей.

🗣️ Алгоритм стабилен и легко понимается, но медленный (O(n²)) — применяется в основном для обучения.

🔵Средняя O(n²)

🔵Худшая O(n²)

🔵Память O(1) — работает на месте

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False  # Флаг для оптимизации
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Меняем элементы местами
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

data = [5, 1, 4, 2, 8]
bubble_sort(data)

@IT_Python_ZheglY | #Сортировки #Python

🔜Radix Sort — поразрядная сортировка

Radix Sort — это нестандартный, но очень мощный алгоритм сортировки. В отличие от большинства алгоритмов, он не использует сравнение элементов. Вместо этого сортирует числа поразрядно: от младшего разряда к старшему (или наоборот).

📌 Плюсы:

🔵Подходит для очень больших массивов чисел

🔵Стабильный способ сортировки (сохраняет порядок равных элементов)

🔵Хорошая скорость сортировки: O(n·k) | k — количество разрядов числа.

❌ Минусы:

🔵Требует дополнительной памяти: O(n + k)

🔵Не подходит для вещественных чисел или отрицательных

🗣️ Этот способ сортировки почти не используется в продакшене из-за выского потребления памяти, но может встречаться на собеседованиях!

@IT_Python_ZheglY | #Сортировки #python

💡 Counting Sort — сортировка подсчётом

🔜Counting Sort — это алгоритм сортировки, который подсчитывает, сколько раз каждое значение встречается, а затем восстанавливает отсортированный массив на основе этих подсчётов.

📌Плюсы:

🔵Высокая скорость при небольшом диапазоне значений

🔵Стабильность (сохраняется порядок равных элементов)

🔵Простая реализация

🚫Минусы:

🔵Требуется дополнительная память

🔵Не работает с вещественными и отрицательными числами

🔵Малоприменим в реальных проектах

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    index = 0

    for i in range(len(count)):
        while count[i] > 0:
            arr[index] = i
            index += 1
            count[i] -= 1

@IT_Python_ZheglY | #сортировки| #python

🔥Задача с LeetCode #647: Palindromic Substrings

🔜Требуется подсчитать количество палиндромных подстрок в заданной строке.
Палиндром - это строка, которая читается одинаково как слева направо, так и справа налево.

Input: s = "aaa"
Output: 6
Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa"

💡Идея решения:

Алгоритм основан на идее, что каждый палиндром в строке имеет центр (или два центра для палиндромов четной длины). Он проходит по всем возможным центрам и "расширяется" в обе стороны, проверяя, образуется ли палиндром.

🔵 В нечетных палиндромах каждый символ рассматриваем как центр

🔵В четных палиндромах каждую пару соседних символов рассматриваем как центр

🖥Подробное видео решение можно посмотреть здесь

@IT_Python_ZheglY | #leetcode #python

🔥Задача с Leetcode #206: Reverse Linked List

🔜Дана голова односвязного списка. Нужно развернуть список и вернуть новую голову.

Исходный список: 1 -> 2 -> 3 -> 4 -> 5
Развёрнутый: 5 -> 4 -> 3 -> 2 -> 1

🔖Разбор кода:

🔵prev (previous) - Хранит предыдущий узел, который станет следующим при развороте.

🔵curr (current) - Текущий узел, который мы обрабатываем.

🔵next_node - Временное хранилище для следующего узла перед разворотом

💡 Идея алгоритма:

🔵 Сохраняем next_node — чтобы не потерять следующий узел после изменения ссылки.

🔵 Разворачиваем ссылку — curr.next теперь указывает на prev.

🔵 Сдвигаем указатели — двигаем prev и curr вперёд.

🖥 Подробное решение можно посмотреть здесь

🧑‍💻@IT_Python_ZheglY | #leetcode #python

🔥 Подкаст "Путь в 1000 шагов". Классы и абстракции

💡 Что такое классы и абстракция? Какие есть способы инкапсуляции и декомпозиции? Как понять логику ООП и эффективно применять ее в проектах?

Все о "подводных камнях" в ООП рассказывают опытные разработчики в этом подкасте

🔖 Таймкоды выпуска:

🔵00:00-05:00 – Что такое класс и абстракция? Инкапсуляция в Python, метод init.

🔵05:50-7:00 – Как правильно объявлять константы?

🔵08:00-10:15 – "Подводные камни" приватных функций. Проектирование и тестирование кода.

🔵11:15-23:00 – Как выбрать имя для класса? Логика кода или как разбивать функциональность кода на классы?

🔵23:00-31:00 – Что такое SRP? Частые ошибки новичков в написании кода.

🔵31:30-35:00 – Декомпозиция при работе с классами.

🔵35:30-45:00 – Связность и согласованность классов и их методов. Как понять логику зависимостей?

🔵47:30-51:00 – Работа с абстракциями и итоги подкаста.

🖥 Ссылка на выпуск 👈

#Python #подкасты

🔥Что такое HTTP Response Codes? Какие основные коды и что о них нужно знать?

HTTP-коды ответов (Status Codes) — это трехзначные числа, которые сервер отправляет клиенту для информирования о результате обработки запроса.

📌 Информационные коды (1xx)

🔵100 Continue — Сервер получил заголовки запроса и ожидает тело запроса. Клиент должен продолжить отправку данных

🔵102 Processing — Сервер обрабатывает запрос, но ответ ещё не готов

💡Успешные коды (2xx)

🟢200 OK — Стандартный ответ для успешных HTTP-запросов.

🟢201 Created Запрос успешно выполнен, и на сервере создан новый ресурс

🟢204 No Content Сервер успешно обработал запрос, но не возвращает тело ответа

📌 Перенаправления (3xx)

🔵301 Moved Permanently Запрошенный ресурс навсегда перемещён на новый URL

🔵302 Found (или 307 Temporary Redirect) Ресурс временно доступен по другому URL

🔵304 Not Modified Сервер сообщает, что ресурс не изменился с момента последнего запроса.

🧑‍💻@IT_Python_ZheglY | #python

💡Http Response Codes 400 / 500

HTTP-коды состояния 400 (Client Error) и 500 (Server Error) — это две основные категории ошибок, которые указывают на проблемы при обработке запроса. Вот их ключевые различия и особенности:

⛔️ Ошибки клиента (4xx)

● 400 Bad Request Сервер не понял запрос из-за синтаксической ошибки

● 401 Unauthorized Требуется аутентификация

● 403 Forbidden Доступ запрещён

● 404 Not Found Сервер не нашёл запрашиваемый ресурс

● 405 Method Not Allowed Используется неподдерживаемый HTTP-метод

🚫 Ошибки сервера (5xx)

● 500 Internal Server Error — Общая ошибка сервера

● 502 Bad Gateway — Проблема с прокси-сервером или API

● 503 Service Unavailable — Сервер временно недоступен.

📚 Доп материалы для прочтения:

1. Полный список кодов с пояснениями от Mozilla
2. QaRocks

🧑‍💻@IT_Python_ZheglY | #python

🌳 Основные деревья в Python и их применение

🗣️ Деревья — иерархические структуры данных, где каждый узел (нода) имеет родителя (кроме корня) и потомков. Используются для представления файловых систем, иерархий данных, оптимизации поиска и сортировки. В Python нет встроенных деревьев, но их реализуют через классы или библиотеки (например, bigtree).

🔵Красно-черное — Самобалансирующееся BST. Основа словарей Python, СУБД.

🔵B+ -дерево — Оптимизировано для дисковых операций. Стандарт для индексов баз данных.

🔵Бинарная куча — Min/Max-куча для приоритетных очередей. Основа для алгоритма Дейкстры.

🔵AVL-дерево — Строго сбалансированное BST. Для систем с гарантированным временем поиска.

🔵Trie (Префиксное) — Хранит строки как цепочки символов. Для автодополнения и словарей.

🔵B-дерево — Многопутевое дерево для файловых систем. Оптимизация чтения/записи блоков.

🔵BST (Бинарное) — Базовое дерево поиска и понимания устройства | Учебные проекты.

🔵Общее дерево — Узлы с произвольным числом потомков. Для XML/JSON и иерархий.

📚 Дополнительные материалы для прочтения:

базовые знание деревьев sky.pro

кратко об обходах и построениях

🔜Далее мы вместе подробнее изучим каждое дерево и разберем код их построения!

🧑‍💻@IT_Python_ZheglY | #python

🌳 Основные деревья в Python |Красно-чёрное дерево (КЧД)

🗣️ Красно-чёрное дерево (КЧД) — это умная структура данных, которая автоматически балансируется при добавлении или удалении элементов. Благодаря этому операции поиска, вставки и удаления работают за O(log n) — быстро даже для больших данных!

🔖 Основные правила:

🔵Цвета — каждый узел красный или чёрный.

🔵Корень и листья — всегда чёрные (листья — это пустые узлы NIL).

🔵Красные узлы — не могут быть родителями красных (нет двух красных подряд).

🔵Чёрная высота — на всех путях от корня до листьев одинаковое число чёрных узлов.

❔ Как оно балансируется?
Если после вставки нарушаются правила, дерево перекрашивает узлы и делает повороты (влево/вправо).

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

💡 Зачем это нужно?
КЧД используется в базах данных, языковых библиотеках и везде, где важен быстрый поиск и динамическое обновление.

📚 Дополнительные материалы для прочтения:

Основные знания Tproger

Код реализации можно посмотреть здесь: https://github.com/ersul4ik/rbt

🧑‍💻@IT_Python_ZheglY | #python #деревья

🌳 Основные деревья в Python | Бинарная куча

Бинарная куча — это специальная древовидная структура данных, которая удовлетворяет свойству кучи

🔵 Min-куча: каждый родительский элемент меньше или равен своим дочерним элементам

🔵 Max-куча: каждый родительский элемент больше или равен своим дочерним элементам.

Это позволяет эффективно добавлять и извлекать элементы с наивысшим приоритетом, используя алгоритмическое время O(log n).

🔜В Python для работы с бинарными кучами используется встроенный модуль heapq, который реализует алгоритм очереди с приоритетами.

📚 Дополнительные материалы для прочтения:

Официальная документация Python

🧑‍💻@IT_Python_ZheglY | #python #деревья

🌳 Основные деревья в Python | B+ дерево ( B+ tree )

Вы когда-нибудь задумывались, как базы данных мгновенно находят нужные записи среди огромного количества данных? Всё дело в эффективной структуре данных — B+ дереве.

🔖Основные особенности дерева:

🔵Все данные — в листьях. Внутренние узлы выступают лишь как «указатели» или «оглавление», что делает поиск по диапазону невероятно быстрым (например, «найти всех пользователей с 10 по 100»).

🔵Листья связаны в список. Это позволяет легко и быстро обходить все данные в отсортированном порядке.

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

🔜Где используется? Практически везде! Это основа индексов в MySQL, PostgreSQL, MongoDB и многих других СУБД. Именно B+-дерево позволяет им работать быстро и стабильно.

📚 Дополнительные материалы для прочтения:

Базовые знания habr.com

Реализация дерева GitHub

🧑‍💻@IT_Python_ZheglY | #python #деревья

⚖️ Что такое балансировка дерева?

Балансировка — это процесс поддержания дерева в «стройной» форме, чтобы не было очень длинных веток и очень коротких.

Зачем это нужно? Балансировка гарантирует, что высота дерева остаётся логарифмической по отношению к числу элементов, а значит, операции поиска, вставки и удаления будут выполняться за O(log n) — то есть, очень быстро.

🔖Основные виды балансировки:

1. Балансировка поворотами |AVL-деревья

🔵Следят за идеальным балансом
🔵После каждого изменения проверяют разницу высот веток
🔵Если разница > 1 — делают повороты для выравнивания
🔵Идеально для частого поиска
❗️ Много поворотов замедляет добавление/удаление

2. Балансировка разделкнием и слиянием | B-деревья и B+-деревья

🔵Хранят несколько ключей в одном узле
🔵При переполнении делятся пополам
🔵При опустошении объединяются с соседом
🔵Идеальны для работы с диском и базами данных
❗️ Сложнее в реализации

3. Красно-чёрные деревья

🔵 Не гонятся за идеальным балансом
🔵 Следят за цветом узлов (красный/чёрный) по простым правилам
🔵Быстрое добавление и удаление
❗️Поиск чуть медленнее, чем в AVL

📚 Дополнительные материалы для прочтения:

Информация по деревьям

Информация по балансировкам

🧑‍💻@IT_Python_ZheglY | #python #деревья

🔍 ОСНОВНЫЕ ОПЕРАЦИИ С ДАННЫМИ: ЧТЕНИЕ, ПОИСК, ВСТАВКА, УДАЛЕНИЕ

📖 ЧТЕНИЕ (Access) Доступ к данным по известному местоположению(индексу или ключу)

🔵Массивы: O(1) — мгновенный доступ по формуле "адрес = начало + индекс × размер"
🔵Связные списки: O(n) — требуется последовательный проход от начала
🔵Хэш-таблицы: O(1) — вычисление хэша и мгновенный доступ к ячейке
🔵Деревья: O(log n) — быстрый спуск по ветвям
🔜Применение: загрузка профилей, отображение товаров, чтение конфигураций

🔍 ПОИСК (Search) Нахождение элемента по значению(а не по позиции)

🔵Линейный поиск: O(n) — последовательная проверка всех элементов (долго)
🔵Бинарный поиск: O(log n) — работает только с отсортированными данными
🔵Хэш-таблицы: O(1) — идеально для поиска по ключу
🔵Деревья: O(log n) — эффективный поиск в сбалансированных структурах
🔜Применение: поиск пользователей, проверка авторизации, фильтрация данных

➕ ВСТАВКА (Insertion) Добавление новых элементов в структуру данных

🔵Массивы: O(n) — требует сдвига элементов (кроме вставки в конец)
🔵Связные списки: O(1) — быстрое изменение указателей
🔵Хэш-таблицы: O(1) — вычисление позиции по хэшу и запись
🔵Деревья: O(log n) — поиск места
и балансировка
🔜Применение: регистрация
пользователей, добавление заказов, логирование

❌ УДАЛЕНИЕ (Deletion) Удаление элементов из структуры данных

🔵Массивы: O(n) — требует сдвига всех последующих элементов
🔵Связные списки: O(1) — быстрое перенаправление указателей
🔵Хэш-таблицы: O(1) — пометка ячейки как удаленной
🔵Деревья: O(log n) — удаление узла с последующей балансировкой
🔜Применение: удаление аккаунтов, очистка кэша, отмена действий

📚 Дополнительные материалы для прочтения:

Основные структуры данных

🧑‍💻@IT_Python_ZheglY | #python
#программирование #алгоритмы #данные #структурыданных

🧠 Что такое энтропия Шеннона и как она измеряет хаос?

Представьте, что вы пытаетесь угадать, что скажет ваш друг. Если он всегда говорит «да» — это скучно и предсказуемо. Если он отвечает случайно — это хаос и неопределенность. Энтропия Шеннона — это число, которое точно измеряет эту самую неопределенность.

📉 Формула:

H = - Σ [p_i * log₂(p_i)]

Где:

H — энтропия (в битах).

p_i — вероятность каждого возможного события.

Σ — сумма по всем событиям.
———————————-————————————————————
Информационная энтропия подчиняется следующим закономерностям:

А) Энтропия события равна 0, если его вероятность равна 1 (100%);

Б) Энтропия двух независимых событий равна сумме энтропий этих событий;

В) Энтропия максимальна, если все события равновероятны.

Получается, чем сложнее предсказать исход события, тем больше информации оно несёт. Если событие редкое и непредсказуемое, мы называем его новостью и наделяем информационной ценностью. Если же оно повторяется часто и о нём постоянно рассказывают, его информационная ценность теряется.
———————————-————————————————————
🎲 Простой пример: Монетка

Честная монетка (орёл/решка по 50%).
Энтропия: H = - [0.5*log₂(0.5) + 0.5*log₂(0.5)] = 1 бит.
Максимальная неопределенность! Памяти на кодирование информации уйдет больше.

Нечестная монетка (орёл — 99%, решка — 1%).
Энтропия: H ≈ 0.08 бита.
Система предсказуема, неопределенность мала. Памяти на кодирование информации уйдет мало.

💡 Где это используется?
Энтропия — не просто теория, она везде в нашей цифровой жизни:

🔵Сжатие данных (ZIP, RAR): Алгоритмы ищут избыточность (низкую энтропию) в данных и упаковывают их меньше.

🔵Криптография: Случайные ключи должны иметь максимальную энтропию, чтобы их было невозможно угадать.

🔵Машинное обучение: С помощью энтропии строят деревья решений, задавая вопросы, которые сильнее всего уменьшают неопределенность.

🔵Связь: Помогает определить максимальную скорость передачи данных без ошибок через зашумленный канал.

Энтропия Шеннона — это фундаментальная мера хаоса и неопределенности, которая позволяет делать наши технологии эффективнее и умнее.

📚 Дополнительные материалы для прочтения:

Информация об информации. Энтропия Шеннона, демон Максвелла и предел Ландауэра

🧑‍💻@IT_Python_ZheglY | #python
#программирование #данные

🔥Задача с Leetcode #392: Is Subsequence

Условие:
Даны две строки s и t. Проверить, является ли s подпоследовательностью t.

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

Примеры:

s = "abc", t = "ahbgdc" → true

s = "axc", t = "ahbgdc" → false

💡Идея решения:

🔵Идем по строке t и ищем символы из s по порядку

🔵Когда находим совпадение - двигаем указатель s на следующий символ.

🔵Если прошли всю s - возвращаем true

Сложность:

⏰ Время: O(n) - проходим по строке t один раз

💾 Память: O(1) - используем только константную память

🖥 Видео разбор задачи NeetCode

🧑‍💻@IT_Python_ZheglY | #leetcode #python