🏗️ Внедрение зависимостей (Dependency Injection)

❓ Что такое Dependency Injection?

Dependency Injection (DI) — паттерн проектирования, который позволяет сделать код более модульным, тестируемым и гибким за счёт управления зависимостями извне.

💡 Ключевые концепции:
- Инверсия управления (IoC)
- Внедрение зависимостей через конструктор
- Слабая связанность компонентов
- Простота тестирования
- Возможность подмены реализаций

// Интерфейс репозитория
type UserRepository interface {
    FindByID(id int) (*User, error)
    Save(user *User) error
}

// Сервис, зависящий от репозитория
type UserService struct {
    repo UserRepository
}

// Конструктор с внедрением зависимости
func NewUserService(repo UserRepository) *UserService {
    return &UserService{repo: repo}
}

// Реальная имплементация репозитория
type PostgresUserRepository struct {
    db *sql.DB
}

func (r *PostgresUserRepository) FindByID(id int) (*User, error) {
    // Реализация поиска
}

// В тестах можно использовать мок
type MockUserRepository struct {
    users map[int]*User
}

func (m *MockUserRepository) FindByID(id int) (*User, error) {
    return m.users[id], nil
}

❗Почему это важно?
- Модульность: Легкая замена компонентов
- Тестируемость: Простое создание mock-объектов
- Гибкость: Независимость компонентов
- Расширяемость: Простое добавление новой функциональности

🎯 DI — ключ к созданию гибких и поддерживаемых систем

🏗️ DDD: Проектирование сложных систем

❓ Что такое DDD?

DDD (Domain-Driven Design) — методология разработки сложных программных систем, фокусирующаяся на бизнес-логике и моделировании предметной области.

💡 Ключевые концепции DDD:
- Сосредоточение на бизнес-правилах и логике предметной области
- Создание общего языка с заказчиком
- Декомпозиция сложной системы на изолированные bounded contexts
- Определение агрегатов, сущностей и доменных событий
- Явное выделение бизнес-логики от технической реализации

// Агрегат в DDD
type Order struct {
    ID        OrderID
    Customer  Customer
    Items     []OrderItem
    Status    OrderStatus
    CreatedAt time.Time
}

// Бизнес-правила внутри агрегата
func (o *Order) AddItem(item Product, quantity int) error {
    // Валидация бизнес-правил
    if quantity <= 0 {
        return errors.New("количество должно быть положительным")
    }
    
    if o.Status != StatusDraft {
        return errors.New("нельзя добавлять товары в завершенный заказ")
    }
    
    // Сложная логика добавления товара
    newItem := OrderItem{
        Product:   item,
        Quantity:  quantity,
        TotalCost: item.Price * quantity,
    }
    
    o.Items = append(o.Items, newItem)
    o.recalculateTotalCost()
    
    return nil
}

// Доменное событие
type OrderCreatedEvent struct {
    OrderID   OrderID
    CreatedAt time.Time
}

❗Почему это важно?
- Управление сложностью: Помогает структурировать сложные многослойные системы
- Коммуникация: Создаёт единый понятный язык между разработчиками и бизнесом
- Гибкость: Позволяет легко адаптировать систему к изменяющимся требованиям

🎯 DDD — методология для создания сложных, эволюционирующих систем с фокусом на бизнес-логике

🏗️ Три слоя бизнес-логики

❓ Что такое три слоя бизнес-логики?

Архитектурный подход, разделяющий приложение на три основных слоя для создания чистой, масштабируемой и поддерживаемой архитектуры.

💡 Характеристики слоёв:
- Слой представления (Presentation Layer):
- Отвечает за взаимодействие с пользователем
- Содержит контроллеры, обработчики HTTP-запросов
- Минимальная бизнес-логика
- Валидация входящих данных
- Преобразование DTO

- Слой бизнес-логики (Business Logic Layer):
- Реализация основных бизнес-процессов
- Сервисы и UseCase
- Сложная логика преобразования данных
- Транзакционное управление
- Бизнес-правила

- Слой данных (Data Access Layer):
- Работа с базами данных
- Репозитории
- ORM-операции
- Абстракция от конкретной базы данных

// Слой представления (Controller)
func CreateUserHandler(w http.ResponseWriter, r *http.Request) {
    var dto UserDTO
    // Валидация входных данных
    if err := json.NewDecoder(r.Body).Decode(&dto); err != nil {
        http.Error(w, err.Error(), http.StatusBadRequest)
        return
    }

    userService := NewUserService()
    user, err := userService.Create(dto)
    if err != nil {
        http.Error(w, err.Error(), http.StatusInternalServerError)
        return
    }

    json.NewEncoder(w).Encode(user)
}

// Слой бизнес-логики (Service)
func (s *UserService) Create(dto UserDTO) (*User, error) {
    // Бизнес-правила
    if err := s.validator.Validate(dto); err != nil {
        return nil, err
    }

    // Сложная логика преобразования
    user := s.mapToUser(dto)
    
    // Транзакционность
    return s.repo.WithTransaction(func(tx *Transaction) (*User, error) {
        return tx.Save(user)
    })
}

// Слой данных (Repository)
func (r *UserRepository) Save(user *User) (*User, error) {
    return r.db.Create(user)
}
  

❗Почему это важно?
- Разделение ответственности: Каждый слой имеет чёткие границы
- Тестируемость: Легко изолировать и тестировать отдельные компоненты
- Масштабируемость: Возможность независимого развития слоёв
- Поддерживаемость: Clear separation of concerns

🎯 Три слоя — фундамент чистой архитектуры приложения

🏗️ 12 Factor App: Облачные приложения

❓ Что такое 12 Factor App?

12 Factor App — методология создания современных веб-приложений, оптимизированных для облачного деплоя, масштабирования и непрерывной поставки.

💡 Подробное описание 12 принципов:

1. Единая кодовая база (Codebase)
- Один репозиторий для каждого приложения
- Возможность деплоя на разные окружения
- Использование систем контроля версий (Git)

2. Явные зависимости (Dependencies)
- Точное объявление и изоляция зависимостей
- Использование менеджеров пакетов
- Никаких системных библиотек

3. Конфигурация через ENV (Config)
- Хранение конфигурации в окружении
- Никаких хардкодов
- Легкая смена конфигурации между средами

4. Backing services как подключаемые ресурсы
- БД, кэши, очереди — внешние сервисы
- Возможность замены без изменения кода

5. Разделение сборки и запуска
- Стадия сборки создает артефакт
- Стадия запуска выполняет этот артефакт

6. Stateless процессы
- Никакого локального стейта
- Персистентность через внешние сервисы

7. Экспорт сервисов через порты
- Полная изоляция сервисов
- Все взаимодействия через сетевые порты

8. Конкурентность
- Горизонтальное масштабирование
- Процессы могут быть запущены в любом количестве

9. Утилизируемость
- Быстрый запуск и остановка
- Грациозное завершение работы

10. Паритет dev/prod
- Максимально близкие окружения
- Непрерывная интеграция

11. Логирование
- Логи как поток событий
- Captures in stdout/stderr

12. Admin-процессы
- Разовые задачи как отдельные процессы

❗Почему это важно?
- Облачная совместимость
- DevOps-практики
- Масштабируемость
- Простота развертывания
- Независимость от инфраструктуры

🎯 12 Factor App — стандарт современных облачных приложений

🏗️ REST: Архитектура веб-сервисов

❓ Что такое REST?

REST (Representational State Transfer) — архитектурный стиль взаимодействия компонентов распределённого приложения в сети.

💡 Принципы REST:

1. Клиент-серверная архитектура
- Четкое разделение ответственности
- Независимое развитие клиента и сервера

2. Отсутствие состояния (Stateless)
- Каждый запрос содержит всю необходимую информацию
- Сервер не хранит информацию о клиенте между запросами
- Каждый запрос — независимая транзакция

3. Кэширование
- Явное указание кэшируемости ресурсов
- Улучшение производительности

4. Единообразие интерфейса
- Стандартизация взаимодействия
- Использование HTTP-методов
- Идентификация ресурсов через URL

5. Многоуровневость
- Возможность размещения посредников
- Прозрачность для клиента
- Балансировка нагрузки

❗Почему это важно?
- Стандартизация API
- Масштабируемость систем
- Независимость компонентов
- Простота интеграции

🎯 REST — фундамент современных веб-сервисов

🛠 Пространственная сложность: что это и как она влияет на производительность?

❓ Что такое пространственная сложность?

Пространственная сложность (space complexity) — это мера объема памяти, необходимого алгоритму для выполнения задачи. Она измеряется в терминах количества используемых ячеек памяти в зависимости от размера входных данных.

💡 Как оценить пространственную сложность?
- О-нотация (Big O notation): Используется для описания асимптотического поведения алгоритма. Например, O(n) указывает на линейное увеличение использования памяти с ростом входных данных.
- Пример:

  func example(n int) {
      arr := make([]int, n) // Пространственная сложность O(n)
      for i := 0; i < n; i++ {
          arr[i] = i
      }
  }
  

⚠️ Почему это важно?
- Оптимизация памяти: Понимание пространственной сложности помогает избежать излишнего использования памяти.
- Производительность: Эффективное использование памяти может улучшить производительность программы, особенно в условиях ограниченных ресурсов.

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

🛠 Временная сложность: что это и как она влияет на производительность?

❓ Что такое временная сложность?

Временная сложность (time complexity) — это мера времени, необходимого алгоритму для выполнения задачи в зависимости от размера входных данных. Она также измеряется с помощью О-нотации.

💡 Как оценить временную сложность?
- О-нотация (Big O notation): Описывает асимптотическое поведение алгоритма. Например, O(n) указывает на линейное увеличение времени выполнения с ростом входных данных.
- Пример:

  func example(n int) {
      sum := 0
      for i := 0; i < n; i++ {
          sum += i
      }
  }
  // Временная сложность O(n)
  

⚠️ Почему это важно?
- Оптимизация времени: Понимание временной сложности помогает выбрать наиболее эффективные алгоритмы.
- Производительность: Эффективное использование времени может значительно улучшить производительность программы, особенно при работе с большими объемами данных.

🎯 Временная сложность — это ключевой показатель, который помогает оптимизировать время выполнения и улучшить производительность алгоритмов.

🛠 Красно-черное дерево: что это и как оно работает?

❓ Что такое красно-черное дерево?

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

💡 Как работает красно-черное дерево?
- Свойства:
1. Каждая нода либо красная, либо черная.
2. Корень всегда черный.
3. Все листья (NIL-ноды) черные.
4. Красная нода не может иметь красных детей.
5. Любой путь от ноды до листьев содержит одинаковое количество черных нод.
- Операции:
- Вставка: Новая нода всегда красная. После вставки выполняются ротации и перекраски для восстановления свойств.
- Удаление: После удаления ноды выполняются ротации и перекраски для восстановления свойств.

❗️Почему это важно?
- Сбалансированность: Красно-черное дерево обеспечивает логарифмическое время выполнения для основных операций.
- Производительность: Эффективное использование памяти и времени делает его популярным выбором для реализации структур данных, таких как словари и множества.

🎯 Красно-черное дерево — это мощная структура данных, которая обеспечивает высокую производительность для операций поиска, вставки и удаления.

🛠 Сортировка пузырьком: что это и как она работает?

❓ Что такое сортировка пузырьком?

Сортировка пузырьком (Bubble Sort) — это простой алгоритм сортировки, который многократно проходит по списку, сравнивая и обменивая соседние элементы, если они находятся в неправильном порядке.

💡 Как работает сортировка пузырьком?
- Процесс:
1. Проходим по списку от начала до конца.
2. Сравниваем каждую пару соседних элементов.
3. Если элементы находятся в неправильном порядке, меняем их местами.
4. Повторяем процесс до тех пор, пока список не будет отсортирован.
- Временная сложность: O(n^2) в худшем и среднем случае, O(n) в лучшем случае (если список уже отсортирован).

⚠️ Пример:

func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

❗️Почему это важно?
- Образовательная ценность: Сортировка пузырьком — это отличный пример для изучения основ алгоритмов сортировки.
- Простота: Алгоритм легко реализовать и понять, но неэффективен для больших объемов данных.

🎯 Сортировка пузырьком — это простой и наглядный алгоритм сортировки, который помогает понять основы работы с массивами.

🛠 Пирамидальная сортировка: что это и как она работает?

❓ Что такое пирамидальная сортировка?

Пирамидальная сортировка (Heap Sort) — это алгоритм сортировки, который использует структуру данных "куча" (heap) для эффективного сортирования элементов.

💡 Как работает пирамидальная сортировка?
- Процесс:
1. Построение кучи: Преобразуем массив в максимальную кучу (max-heap), где каждый родительский узел больше или равен своим дочерним узлам.
2. Извлечение элементов: Поочередно извлекаем максимальный элемент из кучи и перемещаем его в конец массива. После каждого извлечения восстанавливаем свойства кучи.
- Временная сложность: O(n log n) для всех случаев.

⚠️ Пример:

func heapSort(arr []int) {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    for i := n - 1; i >= 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func heapify(arr []int, n int, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

❗️Почему это важно?
- Эффективность: Пирамидальная сортировка обеспечивает логарифмическое время выполнения для всех случаев.
- Производительность: Эффективное использование памяти и времени делает ее популярным выбором для сортировки больших объемов данных.

🎯 Пирамидальная сортировка — это мощный алгоритм, который обеспечивает высокую производительность и эффективность для сортировки данных.

🛠 Односвязный список: что это и как он работает?

❓ Что такое односвязный список?

Односвязный список (Singly Linked List) — это структура данных, состоящая из узлов, где каждый узел содержит данные и ссылку на следующий узел. Последний узел списка указывает на null.

💡 Как работает односвязный список?
- Узел: Состоит из двух частей — данных и ссылки на следующий узел.
- Операции:
- Добавление: Новый узел добавляется в начало или конец списка.
- Удаление: Узел удаляется путем изменения ссылки предыдущего узла.
- Поиск: Проход по списку от начала до конца.

  type Node struct {
      Data int
      Next *Node
  }

  func addToFront(head *Node, data int) *Node {
      newNode := &Node{Data: data, Next: head}
      return newNode
  }
  

⚠️ Почему это важно?
- Простота: Односвязные списки легко реализовать и использовать.
- Динамическое управление памятью: Позволяет эффективно управлять памятью, добавляя и удаляя узлы по мере необходимости.

🎯 Односвязный список — это простая и эффективная структура данных для хранения и управления последовательностями элементов.

🛠 Двусвязный список: что это и как он работает?

❓ Что такое двусвязный список?

Двусвязный список (Doubly Linked List) — это структура данных, состоящая из узлов, где каждый узел содержит данные, ссылку на следующий узел и ссылку на предыдущий узел.

💡 Как работает двусвязный список?
- Узел: Состоит из трех частей — данных, ссылки на следующий узел и ссылки на предыдущий узел.
- Операции:
- Добавление: Новый узел добавляется в начало, конец или середину списка.
- Удаление: Узел удаляется путем изменения ссылок предыдущего и следующего узлов.
- Поиск: Проход по списку в обоих направлениях.

  type Node struct {
      Data int
      Next *Node
      Prev *Node
  }

  func addToFront(head *Node, data int) *Node {
      newNode := &Node{Data: data, Next: head, Prev: nil}
      if head != nil {
          head.Prev = newNode
      }
      return newNode
  }
  

⚠️ Почему это важно?
- Гибкость: Двусвязные списки позволяют эффективно добавлять и удалять узлы в любом месте списка.
- Двусторонний доступ: Возможность прохода по списку в обоих направлениях делает его более удобным для некоторых задач.

🎯 Двусвязный список — это гибкая структура данных, которая обеспечивает эффективное управление последовательностями элементов.

🛠 АВЛ-дерево: что это и как оно работает?

❓ Что такое АВЛ-дерево?

АВЛ-дерево (AVL Tree) — это самобалансирующееся бинарное дерево поиска, которое поддерживает баланс высоты поддеревьев для обеспечения логарифмического времени выполнения операций.

💡 Как работает АВЛ-дерево?
- Свойства:
1. Высота поддеревьев любой ноды отличается не более чем на 1.
2. Каждая нода имеет балансировочный фактор (-1, 0, +1).
- Операции:
- Вставка: После вставки новой ноды выполняются ротации для восстановления баланса.
- Удаление: После удаления ноды выполняются ротации для восстановления баланса.

  type Node struct {
      Key   int
      Left  *Node
      Right *Node
      Height int
  }

⚠️ Почему это важно?
- Сбалансированность: АВЛ-дерево обеспечивает логарифмическое время выполнения для основных операций.
- Производительность: Эффективное использование памяти и времени делает его популярным выбором для реализации структур данных, таких как словари и множества.

🎯 АВЛ-дерево — это мощная структура данных, которая обеспечивает высокую производительность для операций поиска, вставки и удаления.

🛠 k-мерное дерево: что это и как оно работает?

❓ Что такое k-мерное дерево?

k-мерное дерево (k-d Tree) — это структура данных, используемая для организации точек в k-мерном пространстве. Она позволяет эффективно выполнять операции поиска, такие как поиск ближайшего соседа.

💡 Как работает k-мерное дерево?
- Свойства:
1. Каждая нода представляет собой точку в k-мерном пространстве.
2. Дерево разделяет пространство на две половины по одной из координат.
- Операции:
- Построение: Точки рекурсивно разделяются по очереди по каждой координате.
- Поиск: Эффективный поиск ближайшего соседа или точек в заданной области.

  type Point struct {
      Coords []float64
  }

  type Node struct {
      Point  *Point
      Left   *Node
      Right  *Node
  }

⚠️ Почему это важно?
- Эффективность: k-мерные деревья обеспечивают быстрый поиск в многомерных пространствах.
- Применение: Широко используются в задачах машинного обучения, компьютерного зрения и анализа данных.

🎯 k-мерное дерево — это мощная структура данных для организации и поиска точек в многомерных пространствах.

🛠 Timsort: что это и как он работает?

❓ Что такое Timsort?

Timsort — это гибридный алгоритм сортировки. Он сочетает в себе сортировку вставками и слиянием, что позволяет ему эффективно работать с реальными данными.

💡 Как работает Timsort?
- Процесс:
1. Разбиение: Массив разбивается на небольшие подмассивы (runs), которые затем сортируются с помощью сортировки вставками.
2. Слияние: Отсортированные подмассивы сливаются с помощью сортировки слиянием.
- Особенности:
- Адаптивность: Timsort адаптируется к частично отсортированным данным, что делает его очень эффективным для реальных сценариев.
- Стабильность: Алгоритм сохраняет относительный порядок равных элементов.

⚠️ Почему это важно?
- Эффективность: Timsort обеспечивает высокую производительность для сортировки реальных данных.
- Адаптивность: Алгоритм адаптируется к частично отсортированным данным, что делает его очень полезным в практических приложениях.

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

🛠 Сортировка слиянием: что это и как она работает?

❓ Что такое сортировка слиянием?

Сортировка слиянием (Merge Sort) — это алгоритм сортировки, который использует принцип "разделяй и властвуй" для эффективного сортирования элементов.

💡 Как работает сортировка слиянием?
- Процесс:
1. Разделение: Массив делится на две половины до тех пор, пока не останется один элемент или пустой массив.
2. Слияние: Отсортированные половины сливаются обратно в один отсортированный массив.
- Временная сложность: O(n log n) для всех случаев.

⚠️ Пример:

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

❗️Почему это важно?
- Эффективность: Сортировка слиянием обеспечивает логарифмическое время выполнения для всех случаев.
- Стабильность: Алгоритм сохраняет относительный порядок равных элементов.

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

🛠 Быстрая сортировка: что это и как она работает?

❓ Что такое быстрая сортировка?

Быстрая сортировка (Quick Sort) — это алгоритм сортировки, который использует принцип "разделяй и властвуй" для эффективного сортирования элементов.

💡 Как работает быстрая сортировка?
- Процесс:
1. Выбор опорного элемента: Выбирается опорный элемент (pivot) из массива.
2. Разделение: Элементы массива разделяются на две части — меньше и больше опорного элемента.
3. Рекурсия: Процесс повторяется для каждой части массива.
- Временная сложность: O(n log n) в среднем случае, O(n^2) в худшем случае.

⚠️ Пример:

func quickSort(arr []int, low int, high int) {
    if low < high {
        pi := partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

func partition(arr []int, low int, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j <= high-1; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

❗️Почему это важно?
- Эффективность: Быстрая сортировка обеспечивает высокую производительность в среднем случае.
- Простота: Алгоритм прост в реализации и широко используется на практике.

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

🛠 Сортировка вставками: что это и как она работает?

❓ Что такое сортировка вставками?

Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки, который строит отсортированный массив по одному элементу за раз.

💡 Как работает сортировка вставками?
- Процесс:
1. Начало: Первый элемент считается отсортированным.
2. Вставка: Каждый следующий элемент вставляется в правильное место в отсортированной части массива.
- Временная сложность: O(n^2) в худшем и среднем случае, O(n) в лучшем случае.

⚠️ Пример:

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j = j - 1
        }
        arr[j+1] = key
    }
}

❗️Почему это важно?
- Простота: Алгоритм прост в реализации и понимании.
- Эффективность для малых массивов: Сортировка вставками работает хорошо для небольших наборов данных.

🎯 Сортировка вставками — это простой и эффективный алгоритм для сортировки небольших массивов данных.

🛠 Поразрядная сортировка: что это и как она работает?

❓ Что такое поразрядная сортировка?

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

💡 Как работает поразрядная сортировка?
- Процесс:
1. Разделение: Числа разделяются на разряды (цифры).
2. Сортировка: Числа сортируются по каждому разряду, начиная с младшего.
- Временная сложность: O(nk), где n — количество элементов, k — количество разрядов.

⚠️ Пример:

func radixSort(arr []int) {
    max := getMax(arr)
    exp := 1
    for max/exp > 0 {
        countingSort(arr, exp)
        exp *= 10
    }
}

func getMax(arr []int) int {
    max := arr[0]
    for _, v := range arr {
        if v > max {
            max = v
        }
    }
    return max
}

func countingSort(arr []int, exp int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10)
    for i := 0; i < n; i++ {
        index := (arr[i] / exp) % 10
        count[index]++
    }
    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }
    for i := n - 1; i >= 0; i-- {
        index := (arr[i] / exp) % 10
        output[count[index]-1] = arr[i]
        count[index]--
    }
    for i := 0; i < n; i++ {
        arr[i] = output[i]
    }
}

❗️Почему это важно?
- Эффективность: Поразрядная сортировка работает быстро для больших наборов данных с фиксированной длиной чисел.
- Стабильность: Алгоритм сохраняет относительный порядок равных элементов.

🎯 Поразрядная сортировка — это мощный алгоритм для сортировки больших наборов данных с фиксированной длиной чисел.

🛠 Блочная сортировка: что это и как она работает?

❓ Что такое блочная сортировка?

Блочная сортировка (Bucket Sort) — это алгоритм сортировки, который распределяет элементы по "ведрам" (buckets) и сортирует их отдельно.

💡 Как работает блочная сортировка?
- Процесс:
1. Распределение: Элементы распределяются по ведрам на основе их значений.
2. Сортировка: Каждое ведро сортируется отдельно, затем все ведра объединяются.
- Временная сложность: O(n + k) в среднем случае, где n — количество элементов, k — количество ведер.

⚠️ Пример:

func bucketSort(arr []float64) []float64 {
    var buckets [][]float64
    for i := 0; i < len(arr); i++ {
        buckets = append(buckets, []float64{})
    }
    for _, v := range arr {
        index := int(v * float64(len(arr)))
        buckets[index] = append(buckets[index], v)
    }
    for i := range buckets {
        insertionSortFloat(buckets[i])
    }
    index := 0
    for i := range buckets {
        for j := range buckets[i] {
            arr[index] = buckets[i][j]
            index++
        }
    }
    return arr
}

func insertionSortFloat(arr []float64) {
    for i := 1; i < len(arr); i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && arr[j] > key {
            arr[j+1] = arr[j]
            j = j - 1
        }
        arr[j+1] = key
    }
}

❗️Почему это важно?
- Эффективность: Блочная сортировка работает быстро для равномерно распределенных данных.
- Простота: Алгоритм прост в реализации и понимании.

🎯 Блочная сортировка — это мощный алгоритм для сортировки равномерно распределенных данных.

🌳 Декартово дерево (Treap): идеальный баланс между деревом и кучей

❓ Что такое декартово дерево?
Декартово дерево (Treap) — это структура данных, которая сочетает в себе бинарное дерево поиска и бинарную кучу, где каждый узел имеет ключ и приоритет.

💡 Как работает декартово дерево?
- Принцип работы:
1. По ключам строится бинарное дерево поиска
2. По приоритетам поддерживается структура кучи
3. Балансировка происходит автоматически благодаря случайным приоритетам

⚠️ Пример:

type Node struct {
    Key       int
    Priority  int
    Left     *Node
    Right    *Node
}

func Merge(l, r *Node) *Node {
    if l == nil {
        return r
    }
    if r == nil {
        return l
    }
    if l.Priority > r.Priority {
        l.Right = Merge(l.Right, r)
        return l
    }
    r.Left = Merge(l, r.Left)
    return r
}

❗️Почему это важно?
- Эффективность: Ожидаемая высота дерева O(log n)
- Простота реализации базовых операций
- Устойчивость к вырождению благодаря случайным приоритетам

🎯 Декартово дерево — это элегантная структура данных, сочетающая преимущества деревьев поиска и куч.