Слайд 1: Алгоритмы сортировки

Основные алгоритмы сортировки

1. Пузырьковая сортировка (Bubble Sort):

Сложность: O(n²) для любого случая

def bubble_sort(artifacts):
    """
    Сортировка артефактов по крит урону
    """
    n = len(artifacts)
    for i in range(n):
        for j in range(0, n - i - 1):
            if artifacts[j].crit_dmg > artifacts[j + 1].crit_dmg:
                artifacts[j], artifacts[j + 1] = artifacts[j + 1], artifacts[j]

2. Сортировка выбором (Selection Sort):

Сложность: O(n²), но меньше обменов чем в пузырьковой

def selection_sort(characters):
    """
    Сортировка персонажей по базовой атаке
    """
    n = len(characters)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if characters[j].base_atk < characters[min_idx].base_atk:
                min_idx = j
        characters[i], characters[min_idx] = characters[min_idx], characters[i]

3. Быстрая сортировка (Quick Sort):

Сложность: O(n log n) в среднем, O(n²) в худшем случае

def quick_sort(weapons):
    """
    Быстрая сортировка оружия по базовой атаке
    """
    if len(weapons) <= 1:
        return weapons
        
    pivot = weapons[len(weapons) // 2]
    left = [x for x in weapons if x.base_atk < pivot.base_atk]
    middle = [x for x in weapons if x.base_atk == pivot.base_atk]
    right = [x for x in weapons if x.base_atk > pivot.base_atk]
    
    return quick_sort(left) + middle + quick_sort(right)

4. Встроенная сортировка Python (Timsort):

Сложность: O(n log n), оптимизирована для частично отсортированных данных

# Сортировка с использованием key function
artifacts.sort(key=lambda x: x.crit_dmg)

# Сортировка по нескольким критериям
characters.sort(key=lambda x: (x.rarity, -x.base_atk))

# Обратная сортировка
weapons.sort(key=lambda x: x.base_atk, reverse=True)

Важно помнить:

В Python лучше использовать встроенную сортировку (sort или sorted)
Пузырьковая сортировка неэффективна для больших наборов данных
Быстрая сортировка может быть нестабильной
sort изменяет список, sorted создаёт новый

Задача: Сортировка артефактов

Реализуйте систему сортировки артефактов с разными критериями:

Основные требования:
- Сортировка по любой характеристике
- Возможность сортировки по нескольким критериям
- Поддержка обратной сортировки
Критерии сортировки:
- Основная характеристика
- Количество нужных доп. статов
- Общая эффективность артефакта

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

# Пример оценки артефакта
def evaluate_artifact(artifact):
    score = 0
    desired_stats = ["crit_rate", "crit_dmg", "atk_percent"]
    
    # Оценка доп. статов
    for stat in artifact.substats:
        if stat.name in desired_stats:
            score += 1

    # Бонус за основной стат
    if artifact.main_stat in desired_stats:
        score += 2
        
    return score

# Пример использования:
artifacts.sort(key=evaluate_artifact, reverse=True)