Skip to content

genai-readme.md

Latest commit

 

History

History
242 lines (183 loc) · 9.09 KB

genai-readme.md

File metadata and controls

242 lines (183 loc) · 9.09 KB

genai-readme.md — Инструкция для Cursor-агента

ВАЖНО: выполняй шаги строго по порядку. Не пропускай ни одного шага. После каждого шага убедись, что результат корректен, прежде чем переходить к следующему.

Контекст

Курс: «Программист на Python с нуля с помощью ChatGPT 2.0» (Zerocoder). Тема 13, урок OD03 — Алгоритмы сортировки. Домашнее задание: реализовать один или несколько алгоритмов сортировки. Результат — GitHub-репозиторий.

Шаг 1 — Создать структуру проекта

Создай следующие файлы и папки (если их ещё нет):

sorting/
    __init__.py
    bubble_sort.py
    quick_sort.py
    selection_sort.py
    insertion_sort.py
    merge_sort.py
tests/
    __init__.py
    test_sorting.py
main.py

Файл sorting/__init__.py должен импортировать все функции сортировки:

from .bubble_sort import bubble_sort
from .quick_sort import quick_sort
from .selection_sort import selection_sort
from .insertion_sort import insertion_sort
from .merge_sort import merge_sort

Файл tests/__init__.py оставь пустым.

Шаг 2 — Реализовать алгоритмы сортировки

Каждый файл в sorting/ должен содержать ровно одну функцию. Сигнатура единая:

def <название>(arr: list) -> list:

Функция принимает список, возвращает новый отсортированный список (не мутирует входной).

2.1 — bubble_sort.py

Алгоритм пузырьковой сортировки. Обязательна оптимизация: на каждом проходе уменьшать диапазон проверки (элемент уже «всплыл»). Используй два вложенных цикла for.

Пример из урока (адаптируй — функция должна возвращать новый список):

def bubble_sort(arr: list) -> list:
    """Пузырьковая сортировка (Bubble Sort)."""
    result = arr.copy()
    n = len(result)
    for run in range(n - 1):
        for i in range(n - 1 - run):
            if result[i] > result[i + 1]:
                result[i], result[i + 1] = result[i + 1], result[i]
    return result

2.2 — quick_sort.py

Быстрая сортировка. Рекурсивная. Опорный элемент — первый элемент списка. Разделение на left, center, right с помощью filter и lambda.

Пример из урока:

def quick_sort(arr: list) -> list:
    """Быстрая сортировка (Quick Sort)."""
    if len(arr) <= 1:
        return arr.copy()
    element = arr[0]
    left = list(filter(lambda i: i < element, arr))
    center = [i for i in arr if i == element]
    right = list(filter(lambda i: i > element, arr))
    return quick_sort(left) + center + quick_sort(right)

2.3 — selection_sort.py

Сортировка выбором. Два вложенных цикла for. Внутренний цикл ищет индекс минимального элемента, затем происходит обмен.

def selection_sort(arr: list) -> list:
    """Сортировка выбором (Selection Sort)."""
    result = arr.copy()
    for i in range(len(result)):
        min_index = i
        for j in range(i + 1, len(result)):
            if result[j] < result[min_index]:
                min_index = j
        result[i], result[min_index] = result[min_index], result[i]
    return result

2.4 — insertion_sort.py

Сортировка вставками. Цикл for начинается с индекса 1. Внутренний цикл while сдвигает элементы вправо.

def insertion_sort(arr: list) -> list:
    """Сортировка вставками (Insertion Sort)."""
    result = arr.copy()
    for i in range(1, len(result)):
        key = result[i]
        j = i - 1
        while j >= 0 and result[j] > key:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
    return result

2.5 — merge_sort.py

Сортировка слиянием. Рекурсивная. Делит список пополам, рекурсивно сортирует каждую половину, затем сливает.

def merge_sort(arr: list) -> list:
    """Сортировка слиянием (Merge Sort)."""
    if len(arr) <= 1:
        return arr.copy()
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)


def _merge(left: list, right: list) -> list:
    """Вспомогательная функция слияния двух отсортированных списков."""
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Шаг 3 — Создать main.py

Файл main.py демонстрирует работу всех алгоритмов. Выводит название алгоритма и результат сортировки для тестового массива.

"""Демонстрация алгоритмов сортировки из урока OD03."""

from sorting import (
    bubble_sort,
    quick_sort,
    selection_sort,
    insertion_sort,
    merge_sort,
)


def main():
    test_array = [5, 7, 4, 3, 8, 2]
    print(f"Исходный массив: {test_array}")
    print()

    algorithms = [
        ("Пузырьковая сортировка (Bubble Sort)", bubble_sort),
        ("Быстрая сортировка (Quick Sort)", quick_sort),
        ("Сортировка выбором (Selection Sort)", selection_sort),
        ("Сортировка вставками (Insertion Sort)", insertion_sort),
        ("Сортировка слиянием (Merge Sort)", merge_sort),
    ]

    for name, func in algorithms:
        result = func(test_array)
        print(f"{name}: {result}")


if __name__ == "__main__":
    main()

Шаг 4 — Создать тесты

Файл tests/test_sorting.py. Используй только стандартную библиотеку (unittest). Не используй pytest как зависимость — только как раннер.

Обязательные тест-кейсы для КАЖДОГО алгоритма:

  1. Массив из урока: [5, 7, 4, 3, 8, 2] → [2, 3, 4, 5, 7, 8].
  2. Пустой список: [] → [].
  3. Один элемент: [42] → [42].
  4. Уже отсортированный: [1, 2, 3, 4, 5] → [1, 2, 3, 4, 5].
  5. Обратный порядок: [5, 4, 3, 2, 1] → [1, 2, 3, 4, 5].
  6. Дубликаты: [5, 2, 9, 0, 1, 5, 3] → [0, 1, 2, 3, 5, 5, 9].
  7. Отрицательные числа: [-3, 5, 0, -8, 1, 10] → [-8, -3, 0, 1, 5, 10].
  8. Проверка, что исходный массив НЕ изменился (immutability).

Используй unittest.TestCase и параметризуй через цикл или отдельные методы.

Шаг 5 — Запустить тесты

Выполни команду:

python -m pytest tests/ -v

Если pytest не установлен, используй:

python -m unittest discover -s tests -v

ВСЕ тесты должны пройти. Если есть ошибки — исправь код и запусти тесты повторно.

Шаг 6 — Проверить .md файлы линтером

Убедись, что файлы README.md и все .md файлы соответствуют правилам:

  • MD009 — нет trailing spaces.
  • MD022 — пустые строки до и после заголовков.
  • MD029 — нумерация ordered lists: 1. для каждого пункта (не 1. 2. 3.).
  • MD032 — пустые строки вокруг списков.

Шаг 7 — Финальная проверка

Перед завершением убедись:

  • Все 5 файлов сортировки существуют и содержат код.
  • main.py запускается без ошибок.
  • Все тесты проходят.
  • Комментарии и docstring написаны на русском языке.
  • Файл README.md существует.
  • Нет лишних файлов (__pycache__, .pyc и т. д.).