Раздел 7. Алгоритмы

Глава 3: Алгоритмы сортировки и подготовка данных

Назначение и стоимость сортировки: стратегическая инвестиция в данные

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

Ускорение поиска

Главное практическое применение сортировки — обеспечение быстрого поиска. Неотсортированные данные допускают только линейный поиск с временной сложностью O(n). После сортировки становится возможным бинарный поиск, сокращающий время до O(log n). Это преобразует поиск из линейной в логарифмическую операцию, что для миллиона элементов означает сокращение с миллиона сравнений до всего 20.

// Демонстрация разницы в поиске
public class SearchComparison {
    // Линейный поиск в неотсортированном массиве
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) return i;
        }
        return -1;
    }
    
    // Бинарный поиск в отсортированном массиве
    public static int binarySearch(int[] sortedArray, int target) {
        int left = 0, right = sortedArray.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (sortedArray[mid] == target) return mid;
            if (sortedArray[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

Улучшение представления данных

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

Обеспечение группировки и агрегации

Сортировка является предварительным шагом для многих алгоритмов анализа данных.

После сортировки идентичные или схожие элементы располагаются рядом, что упрощает:
Удаление дубликатов за один проход
Построение гистограмм и частотных распределений
Выполнение операций слияния (как в MergeSort)
Реализацию алгоритмов слияния интервалов или поиска пересечений


Сортировка как стратегическая инвестиция

Сортировку можно рассматривать как инвестицию с отложенной выгодой. Мы платим относительно высокую первоначальную цену — O(n log n) операций — чтобы получить ускорение в будущих операциях. Эта модель окупается, когда количество операций поиска значительно превышает единицу.

Рассмотрим математическую модель:
Стоимость сортировки: C₁ × n log n
Стоимость одного линейного поиска: C₂ × n
Стоимость одного бинарного поиска: C₃ × log n

Точка безубыточности наступает, когда k операций бинарного поиска после сортировки становятся выгоднее k операций линейного поиска без сортировки:
C₁ × n log n + k × C₃ × log n < k × C₂ × n
Для типичных значений (n=1000, C₁≈C₂≈C₃) получаем, что уже при 10-15 операциях поиска сортировка окупается.


Оптимизация для повторного использования

Отсортированные данные становятся активом, который можно многократно использовать для различных целей.

Один раз отсортировав массив сотрудников по фамилии, мы получаем возможность:
Быстрого поиска конкретного сотрудника
Генерации алфавитного списка
Поиска сотрудников в заданном алфавитном диапазоне
Объединения с другим отсортированным списком
Это преобразует данные из пассивного состояния в активную структуру, поддерживающую множество операций.


#Java #для_новичков #beginner #algorithm #sorted

Кэш-дружественность отсортированных данных

Современные процессоры сильно зависят от кэш-памяти. Отсортированные данные обладают лучшей пространственной локальностью: последовательные обращения к памяти с высокой вероятностью попадают в кэш. Это особенно важно для итеративных алгоритмов, где каждый проход по отсортированным данным выполняется на 20-40% быстрее благодаря уменьшению количества кэш-промахов.


Устойчивость сортировки: концепция и практическая ценность

Сортировка называется устойчивой (stable), если она сохраняет относительный порядок элементов с одинаковыми ключами. Формально: если до сортировки элемент A предшествовал элементу B, и их ключи сортировки равны, то после сортировки A останется перед B.

Практический пример: многоуровневая сортировка

Рассмотрим каталог книг с полями: автор, год издания, название. Требуется отсортировать книги по автору, а внутри каждого автора — по году издания.

Без устойчивой сортировки задача требует сложной логики:

// Сложный компаратор для неустойчивой сортировки
Comparator<Book> complexComparator = Comparator
    .comparing(Book::getAuthor)
    .thenComparing(Book::getYear);
books.sort(complexComparator); // Работает, но если сортировка неустойчива,
                               // порядок внутри автора может нарушиться

С устойчивой сортировкой решение элегантно:

// Сначала сортируем по вторичному ключу
books.sort(Comparator.comparing(Book::getYear));

// Затем сортируем по основному ключу
books.sort(Comparator.comparing(Book::getAuthor));

// После второй сортировки порядок годов сохранится для каждого автора
// благодаря устойчивости

Устойчивость гарантирует, что результат двух последовательных сортировок эквивалентен сортировке составным ключом.

Где устойчивость критически важна

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

Цена устойчивости

Устойчивость обычно достигается за счет:
Дополнительной памяти (как в MergeSort)
Более сложных алгоритмов сравнения
Незначительного увеличения времени выполнения
Неустойчивые алгоритмы (как QuickSort или HeapSort) часто быстрее и используют меньше памяти, но требуют осторожности при работе с составными ключами.


Количественная оценка стоимости сортировки

Стоимость сортировки можно амортизировать на все последующие операции.

Для коллекции из n элементов, над которой выполняется m операций поиска:
Без сортировки: Суммарная стоимость = m × O(n) = O(m × n)
С сортировкой: Суммарная стоимость = O(n log n) + m × O(log n)
Разница становится существенной при m > log n. Для n=1000 (log n ≈ 10) уже при 11 поисках сортировка окупается.

Влияние на системную архитектуру

Решение о предварительной сортировке влияет на проектирование систем:
Пакетная обработка: Сортировка выполняется один раз при загрузке данных, затем используется для множества запросов.
Интерактивные системы: Для часто изменяющихся данных поддерживается индексированная структура (как B-дерево), которая обеспечивает и сортировку, и быстрый поиск.
Распределенные системы: Данные распределяются между узлами уже отсортированными (shard-ключи), что позволяет выполнять параллельный поиск.


#Java #для_новичков #beginner #algorithm #sorted

Компромисс: сортировка vs индексация

Сортировка — не единственный способ ускорить поиск. Альтернатива — построение индекса (например, хеш-таблицы).

Сравнение:
Сортировка: O(n log n) времени, O(1) дополнительной памяти (in-place), поддерживает диапазонные запросы
Хеширование: O(n) времени, O(n) дополнительной памяти, точечный доступ O(1), нет поддержки диапазонов
Выбор зависит от паттерна доступа: частые диапазонные запросы требуют сортировки, точечные — хеширования.


Практические рекомендации

Когда сортировать данные
Предварительная сортировка: Когда известно, что данные будут многократно использоваться для поиска или анализа.
Кэширование отсортированных представлений: Хранить данные в основной форме, но создавать отсортированные копии для частых запросов.
Ленивая сортировка: Откладывать сортировку до первого запроса, требующего порядка.

Когда избегать сортировки
Единичные операции: Если требуется одна операция поиска, линейный поиск может быть эффективнее.
Частые модификации: При постоянных добавлениях/удалениях поддержание отсортированного состояния требует дополнительных затрат.
Ограниченные ресурсы: На устройствах с ограниченной памятью in-place сортировка предпочтительнее, но может быть слишком дорогой по времени.

Выбор алгоритма сортировки

Критерии выбора:
Устойчивость: Нужна ли сохранение относительного порядка?
Память: Доступна ли дополнительная память O(n)?
Время: Важна ли гарантия O(n log n) в худшем случае?
Данные: Частично отсортированы ли данные?

#Java #для_новичков #beginner #algorithm #sorted

Раздел 7. Алгоритмы

Глава 3: Алгоритмы сортировки и подготовка данных

Квадратичные сортировки: фундамент понимания

Классические алгоритмы O(n²)
Квадратичные сортировки представляют собой интеллектуальную основу для понимания более сложных алгоритмов. Их простота позволяет ясно увидеть фундаментальные принципы упорядочивания данных.

Пузырьковая сортировка (Bubble Sort)
Принцип работы: алгоритм последовательно сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке. За каждый проход наибольший "всплывающий" элемент занимает свою окончательную позицию.

public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Обмен элементов
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Характеристики:
Временная сложность: O(n²) в худшем и среднем случае
Пространственная сложность: O(1) (in-place)
Устойчивость: да (не меняет порядок равных элементов)
Особенность: после k итераций последние k элементов находятся на своих местах
Оптимизация: добавление флага прекращает выполнение, если на проходе не было обменов. Для уже отсортированного массива это дает O(n).

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

Принцип работы: алгоритм делит массив на отсортированную и неотсортированную части. На каждом шаге он находит минимальный элемент в неотсортированной части и перемещает его в конец отсортированной.

public class SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            // Обмен текущего элемента с минимальным
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}

Характеристики:
Временная сложность: всегда O(n²) независимо от исходных данных
Количество сравнений: n(n-1)/2
Количество обменов: n-1 (минимальное среди квадратичных алгоритмов)
Устойчивость: нет (может менять порядок равных элементов)
Преимущество: минимальное количество операций записи, что важно для устройств с ограниченным ресурсом записи (например, флеш-память)

Сортировка вставками (Insertion Sort)

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

public class InsertionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // Сдвигаем элементы, большие key, вправо
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

Характеристики:
Временная сложность: O(n²) в худшем случае, O(n) в лучшем (уже отсортированный массив)
Количество сравнений: от n-1 до n(n-1)/2
Количество обменов: от 0 до n(n-1)/2
Устойчивость: да
Особенность: эффективен на небольших наборах данных (n < 50) и почти отсортированных массивах


Адаптивность сортировки вставками

Эффективность на почти отсортированных данных
Сортировка вставками обладает свойством адаптивности: ее время выполнения зависит от степени упорядоченности входных данных. Для массива, в котором каждый элемент находится не более чем на k позиций от своего окончательного места, сложность составляет O(nk).

На практически отсортированных данных (k мало) алгоритм приближается к линейному времени.

#Java #для_новичков #beginner #algorithm #sorted

Это делает его идеальным для:
Досортировки результатов предыдущих частичных сортировок
Поддержания порядка в динамически изменяемых коллекциях
Обработки потоковых данных, где новые элементы добавляются к уже отсортированной последовательности

Механизм адаптации

Алгоритм эффективен благодаря двум свойствам:
Локальность: при вставке нового элемента перемещения происходят только в его окрестности
Инкрементальность: каждая итерация поддерживает частично отсортированное состояние
Для уже отсортированного массива внутренний цикл while никогда не выполняется, и алгоритм делает ровно n-1 сравнение.


Применение в современных гибридных алгоритмах

Timsort: промышленный стандарт

Timsort — гибридный алгоритм, используемый в Python, Java (для массивов объектов), Android и V8. Он сочетает сортировку вставками и слиянием, демонстрируя эволюцию простых алгоритмов в промышленные решения.

В Timsort сортировка вставками применяется для:
Создания минимальных упорядоченных сегментов (run)
Досортировки мелких подмассивов (обычно до 32-64 элементов)

// Упрощенная концепция Timsort
public class TimsortConcept {
    private static final int RUN = 32;
    
    public static void timsort(int[] arr) {
        // 1. Разбиваем на маленькие сегменты
        for (int i = 0; i < arr.length; i += RUN) {
            insertionSort(arr, i, Math.min(i + RUN - 1, arr.length - 1));
        }
        
        // 2. Сливаем сегменты попарно
        // ... (реализация слияния)
    }
    
    // Оптимизированная сортировка вставками для диапазона
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // Используем бинарный поиск для нахождения позиции
            int pos = binarySearch(arr, key, left, j);
            
            // Сдвигаем элементы
            while (j >= pos) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

Причины выбора сортировки вставками для мелких массивов

Низкие константы: У сортировки вставками небольшие накладные расходы по сравнению с рекурсивными алгоритмами
Кэш-дружественность: Последовательный доступ к памяти хорошо работает с кэшем процессора
Адаптивность: На почти отсортированных данных она работает быстрее теоретически более быстрых алгоритмов

Другие гибридные применения

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

Педагогическая ценность квадратичных алгоритмов

Квадратичные сортировки служат идеальной точкой входа в изучение алгоритмов по нескольким причинам:
Наглядность: Принципы работы можно понять без сложной математики
Полнота: Охватывают основные стратегии: сравнение соседей (пузырьковая), поиск минимума (выбором), вставка в упорядоченную последовательность (вставками)
Естественность: Сортировка вставками соответствует тому, как люди обычно упорядочивают карты в руке

Нижняя планка эффективности

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

Для n=1000:
Квадратичная сортировка: ~1,000,000 операций
Эффективная сортировка (n log n): ~10,000 операций
Разница в 100 раз становится критичной при масштабировании


Развитие алгоритмического мышления

Анализ квадратичных алгоритмов учит важным навыкам:
Анализ сложности: Понимание вложенных циклов и их стоимости
Оптимизация: Как небольшие изменения (флаг в пузырьковой) влияют на производительность
Адаптивность: Почему одни алгоритмы лучше работают на определенных данных


#Java #для_новичков #beginner #algorithm #sorted

Раздел 7. Алгоритмы

Глава 3: Алгоритмы сортировки и подготовка данных

Эффективные сортировки O(n log n): парадигмы и компромиссы

Парадигма «Разделяй и властвуй»

Алгоритмическая парадигма «Разделяй и властвуй» (Divide and Conquer) основана на рекурсивном разбиении задачи на подзадачи меньшего размера, решении этих подзадач и комбинировании результатов.

Три ключевых этапа:
Разделение: Разбиение исходной задачи на меньшие независимые подзадачи
Покорение: Рекурсивное решение подзадач
Объединение: Комбинирование результатов подзадач в решение исходной задачи

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


Быстрая сортировка (QuickSort): скорость с оговорками

QuickSort выбирает опорный элемент (pivot) и разделяет массив на три части: элементы меньше pivot, равные pivot, и больше pivot. Затем рекурсивно сортирует части до и после pivot.

public class QuickSort {
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Разделение массива
            int pivotIndex = partition(arr, low, high);
            
            // Рекурсивная сортировка двух частей
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        // Выбор опорного элемента (последний)
        int pivot = arr[high];
        int i = low - 1; // Индекс меньшего элемента
        
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
}

Критические особенности

Неустойчивость: Меняет относительный порядок равных элементов
Зависимость от выбора pivot: Качество разделения определяет эффективность
Худший случай O(n²): При неудачном выборе pivot (уже отсортированный массив + выбор крайнего элемента)
Средний случай O(n log n): При случайных данных или хорошей стратегии выбора pivot

Стратегии выбора pivot
Случайный элемент: Устраняет худший случай для предсказуемых данных
Медиана трех: Выбор из первого, среднего и последнего элементов
Introsort: Переключение на HeapSort при глубокой рекурсии

// Улучшенный выбор pivot
private static int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    // Упорядочиваем три элемента
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[low] > arr[high]) swap(arr, low, high);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    
    return mid; // Медиана в середине
}

Практическое применение

QuickSort доминирует в стандартных библиотеках благодаря:
Отличной средней производительности
Кэш-дружественности (последовательный доступ при partition)
Возможности оптимизаций (интроспективная сортировка)

#Java #для_новичков #beginner #algorithm #sorted #QuickSort

Сортировка слиянием (MergeSort): стабильность и гарантии

MergeSort рекурсивно делит массив пополам до подмассивов размером 1, затем сливает упорядоченные подмассивы в большие упорядоченные массивы.

public class MergeSort {
    public static void sort(int[] arr) {
        if (arr.length <= 1) return;
        
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        
        sort(left);
        sort(right);
        merge(arr, left, right);
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            // Стабильность: сохраняем порядок равных элементов из левой части
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
    }
}

Ключевые характеристики

Устойчивость: Сохраняет относительный порядок равных элементов
Гарантированная сложность: Всегда O(n log n) независимо от входных данных
Дополнительная память O(n): Требует временного массива для слияния
Параллелизуемость: Легко распараллеливается благодаря независимости подзадач

Компромиссы

Память vs Стабильность: За стабильность и гарантии платим дополнительной памятью
Время vs Предсказуемость: Худший случай лучше, чем у QuickSort, но средний часто медленнее

Применение

Сортировка связанных списков (требует O(1) доп. памяти)
Внешняя сортировка больших файлов (слияние отсортированных блоков)
Там, где важна стабильность (многоуровневая сортировка)


#Java #для_новичков #beginner #algorithm #sorted #MergeSort

Сортировка кучей (HeapSort): баланс памяти и производительности

Куча (heap) — двоичное дерево, удовлетворяющее свойству кучи: родитель всегда больше (max-heap) или меньше (min-heap) своих потомков.

public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // Построение max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // Извлечение элементов из кучи
        for (int i = n - 1; i > 0; i--) {
            // Перемещаем корень (максимум) в конец
            swap(arr, 0, i);
            
            // Восстанавливаем кучу для уменьшенного массива
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;        // Инициализируем корень как наибольший
        int left = 2 * i + 1;   // Левый потомок
        int 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) {
            swap(arr, i, largest);
            heapify(arr, n, largest); // Рекурсивно heapify затронутое поддерево
        }
    }
}

Особенности HeapSort

Неустойчивость: Перестановки элементов нарушают исходный порядок
Дополнительная память O(1): Работает на месте (in-place)
Гарантированная сложность O(n log n): Худший случай не хуже
Кэш-недружественность: Случайный доступ к элементам при heapify

Применение в гибридных алгоритмах

HeapSort используется как защитный механизм:
Introsort: Быстрая сортировка + HeapSort при глубокой рекурсии
Heapsort для малых n: В некоторых реализациях для небольших массивов
Реализация приоритетных очередей: Структура кучи — основа PriorityQueue

Сравнительный анализ: три подхода к эффективности

По устойчивости
Устойчивые: MergeSort (сохраняет порядок равных)
Неустойчивые: QuickSort, HeapSort (меняют порядок)

По использованию памяти
O(1) дополнительной памяти: HeapSort (in-place)
O(log n) стековой памяти: QuickSort (рекурсия)
O(n) дополнительной памяти: MergeSort (временный массив)

По гарантиям времени
Всегда O(n log n): MergeSort, HeapSort
O(n²) в худшем, O(n log n) в среднем: QuickSort

По практической производительности
QuickSort: Самый быстрый в среднем случае, лучшая локальность кэша
HeapSort: Гарантии без доп. памяти, но медленнее из-за плохой локальности
MergeSort: Стабильность и параллелизуемость, но требует памяти


Применение парадигмы «Разделяй и властвуй»

Оба основных алгоритма следуют парадигме:

QuickSort:
Разделение: Partition по pivot (O(n))
Покорение: Рекурсивная сортировка двух частей
Объединение: Уже отсортировано на месте

MergeSort:
Разделение: Пополам (O(1))
Покорение: Рекурсивная сортировка половин
Объединение: Merge двух отсортированных массивов (O(n))

Анализ сложности

Рекуррентное соотношение для обоих алгоритмов (в среднем для QuickSort):
T(n) = 2T(n/2) + O(n)
По основной теореме о рекуррентных соотношениях это дает O(n log n).

Почему это эффективно
Разделение задачи размером n на две подзадачи размером n/2 уменьшает общий объем работы. Если бы разделение было линейным (например, на задачи размером n-1 и 1), сложность оставалась бы квадратичной.


#Java #для_новичков #beginner #algorithm #sorted #HeapSort

Раздел 7. Алгоритмы

Глава 3. Алгоритмы сортировки и подготовка данных

Практика : Реализовать сортировку выбором и сортировку слиянием для книг по году издания. Убедиться, что слияние сохраняет относительный порядок (устойчивость). Использовать Collections.sort() и исследовать, какой алгоритм применяется (Timsort — гибрид вставок и слияния).

Анализ: В каком случае для библиотечного приложения важна устойчивость сортировки? Когда можно пожертвовать памятью (MergeSort) ради гарантии, а когда важна экономия памяти (HeapSort)?

Мы реализуем две классические сортировки вручную:
Сортировка выбором (Selection Sort) — простой, понятный, но неэффективный алгоритм O(n²)
Сортировка слиянием (Merge Sort) — устойчивый алгоритм с гарантированной сложностью O(n log n) и дополнительной памятью O(n)


Подготовка к уроку

Перед началом убедитесь, что в проекте есть:
Класс Book с полями title, author, year (все поля должны иметь геттеры)
Класс Library с полем List<Book> books = new ArrayList<>()
Метод printAllBooks() или аналогичный для вывода списка книг с номерами

Рекомендуемые импорты в Library.java:
Javaimport java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


Шаг 1. Подготовка тестовых данных

Перед реализацией алгоритмов добавьте в main или в метод инициализации библиотеки набор книг с намеренными дубликатами годов и авторов, чтобы можно было проверить устойчивость сортировки.
Пример набора данных, который вы должны создать самостоятельно:

"1984", "Оруэлл", 1949
"Скотный двор", "Оруэлл", 1945
"Война и мир", "Толстой", 1869
"Анна Каренина", "Толстой", 1877
"Мастер и Маргарита", "Булгаков", 1967
"Собачье сердце", "Булгаков", 1925
"Преступление и наказание", "Достоевский", 1866
"Идиот", "Достоевский", 1869
"Братья Карамазовы", "Достоевский", 1880

Обратите внимание: два автора имеют одинаковый год (Оруэлл не имеет дублей, Достоевский имеет два произведения в 1869 году).


Шаг 2. Реализация сортировки выбором (Selection Sort) по году

Создайте в классе Library метод:public void selectionSortByYear()

Внутри метода:
Переберите массив/список внешним циклом от 0 до books.size()–2
Для каждого i найдите индекс минимального года в подмассиве [i … end]
Если найденный минимум не равен i — поменяйте местами элементы i и minIndex
После окончания внешнего цикла список должен быть отсортирован по году

После сортировки вызовите printAllBooks() — чтобы увидеть результат

Важные моменты для самостоятельной реализации:
Работайте с индексами (не создавайте новый список)
Сравнивайте book.getYear()
Обменяйте объекты целиком (не отдельные поля)


#Java #для_новичков #beginner #algorithm #sorted #HeapSort #Практика

Шаг 3. Реализация сортировки слиянием (Merge Sort) по году

Создайте метод: public void mergeSortByYear()

Реализуйте классический рекурсивный Merge Sort:
Создайте вспомогательный метод mergeSort(List<Book> list, int left, int right)

Если left < right:
mid = (left + right) / 2
Рекурсивно сортируйте левую половину
Рекурсивно сортируйте правую половину
Слейте две отсортированные половины в методе merge()

Реализуйте метод merge(List<Book> list, int left, int mid, int right):
Создайте временный список temp нужного размера
Два указателя i = left, j = mid+1
Пока обе половины не закончились — сравнивайте и копируйте меньший элемент
Докопируйте остаток левой или правой половины
Скопируйте temp обратно в исходный список на позиции left..right

Ключевой момент устойчивости:
Merge Sort устойчив — при равных ключах сохраняется относительный порядок исходных элементов.
После сортировки вызовите printAllBooks() и убедитесь, что книги Достоевского 1869 года остались в исходном порядке (Преступление → Идиот).
Шаг 4. Использование встроенной сортировки (Collections.sort и List.sort)

Создайте метод sortWithCollections():
Вызовите Collections.sort(books) — поскольку Book реализует Comparable по названию (из предыдущего урока), отсортирует по названию
Затем вызовите books.sort(Comparator.comparingInt(Book::getYear)) — сортировка по году
Затем вызовите books.sort(Comparator.comparing(Book::getAuthor).thenComparingInt(Book::getYear)) — по автору, затем по году

После каждой сортировки выводите список и наблюдайте порядок.

Исследование Timsort:

Начиная с Java 7, Collections.sort() и List.sort() используют Timsort — гибридный алгоритм:
Сортировка вставками для малых подмассивов (run ≤ 32)
Слияние (merge) для больших
Очень эффективен на реальных данных (частично отсортированных)
Устойчив — сохраняет относительный порядок равных элементов

Анализ: Когда важна устойчивость сортировки?

Устойчивость (stable sort) — когда при равных ключах сохраняется исходный относительный порядок элементов.

В библиотечном приложении устойчивость важна в следующих случаях:
Сортировка по году, но хочется сохранить алфавитный порядок авторов при одинаковом годе
→ Если два произведения Достоевского вышли в 1869 году — после сортировки по году они должны остаться в порядке появления в каталоге или по алфавиту названий.
Сортировка по рейтингу, но при равном рейтинге важен порядок добавления
→ Пользователь добавил книги в определённом порядке — при равном рейтинге хочется видеть их в этом же порядке.
Многоуровневая сортировка
→ Сначала по автору, затем по году — устойчивость гарантирует, что внутри одного автора книги останутся в порядке добавления или по названию.

Когда устойчивость не критична:
Сортировка по уникальному полю (ISBN, ID) — равных элементов нет
Когда порядок внутри группы не имеет значения (например, только по жанру)
Когда важна максимальная скорость и экономия памяти, а не порядок

Сравнение по памяти и устойчивости:

Прогноз при росте данных:
100 книг → любой алгоритм за миллисекунды
100 000 книг → Selection Sort — секунды, остальные — десятки миллисекунд
1 000 000 книг → Selection Sort — часы, Timsort/Merge — секунды, HeapSort — чуть быстрее MergeSort за счёт меньшей памяти

Вывод для библиотеки:
Основной выбор — List.sort() (Timsort): устойчивый, быстрый, адаптивный
Merge Sort вручную — только если нужно изучить алгоритм или требуется явный контроль
HeapSort — если память критична (очень редкий случай)
Selection Sort — исключительно для обучения


Практическое задание (объёмное)

Реализуйте selectionSortByYear() вручную.
Реализуйте рекурсивный mergeSortByYear() с вспомогательным merge.

Добавьте методы:
sortByTitleUsingCollections()
sortByAuthorThenYearUsingComparator()
sortByYearUsingLambda()

В main добавьте 10+ книг с дубликатами годов и авторов.
Выполните все сортировки подряд и выводите список после каждой.
Сравните порядок книг Достоевского 1869 года до и после сортировки по году — убедитесь в устойчивости Timsort и MergeSort.

#Java #для_новичков #beginner #algorithm #sorted #HeapSort #Практика

Глава 4: Эффективный поиск. Бинарный и не только

Бинарный поиск — принцип и реализация

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

Метод применим не только к книгам. Любая структура данных, допускающая индексный доступ (мгновенное обращение к элементу по его порядковому номеру) и поддерживающая отношение полного порядка (возможность сравнить два элемента и сказать, какой «меньше»), может стать кандидатом для бинарного поиска. Массивы, ArrayList, сегменты файлов на диске — типичные носители.


Аксиома: данные должны быть отсортированы

Прежде чем разбирать сам алгоритм, зафиксируем ключевое требование: исходная коллекция должна быть упорядочена относительно ключа поиска. Это не формальность, а математическая необходимость.

Представьте отсортированный массив как монотонную функцию f(i) = array[i], где при увеличении индекса i значение не убывает. Это свойство монотонности гарантирует, что если array[mid] > target, то искомый элемент (если он вообще присутствует) не может находиться правее позиции mid. Аналогично для случая array[mid] < target. Это утверждение выполняется только в отсортированной последовательности.

Когда мы говорим о сортировке в контексте бинарного поиска, имеем в виду строгий порядок, поддерживаемый на всем диапазоне от array[0] до array[n-1]. Любое нарушение этого правила — и алгоритм начнет отбрасывать правильные ответы вместе с «плохими» половинами, возвращая ложные отрицательные результаты.


Ядро алгоритма: принцип деления пополам

Бинарный поиск работает по схеме «разделяй и властвуй», но в отличие от сортировки слиянием здесь мы не комбинируем результаты подзадач.

Алгоритм состоит из циклически повторяющихся шагов:
Инициализация: Задаем два указателя — left, охватывающий начало рабочей области (обычно индекс 0), и right, обозначающий конец (последний допустимый индекс или размер массива в зависимости от вариации реализации).
Итерация: Пока область поиска не схлопнулась (left <= right или эквивалентное условие):
Вычисляем середину: mid = left + (right - left) / 2. Эта формула защищает от целочисленного переполнения, которое могло бы случиться при более прямолинейном (left + right) / 2 на очень больших массивах.

Сравниваем array[mid] с целевым значением target.
Если array[mid] == target — поиск успешен, возвращаем mid.
Если array[mid] < target — искомый элемент, если существует, находится строго правее. Сдвигаем left = mid + 1.
Иначе (array[mid] > target) — сдвигаем right = mid - 1.
Завершение: Если выход из цикла произошел без нахождения элемента, возвращаем индикатор отсутствия (обычно -1 или Optional.empty()).

Важный момент: способ вычисления mid и обновления границ формирует два семейства реализаций — с включенной правой границей (right указывает на последний допустимый индекс) и с исключенной (right указывает на первый индекс за пределами области). Оба подхода рабочие, но условия цикла и обновления границ меняются зеркально. Мы разберем вариант с включенной границей, как более интуитивный для начального понимания.


#Java #для_новичков #beginner #algorithm #sorted #binary

Итеративная реализация: фундамент

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

public class BinarySearch {

    /**
     * Выполняет бинарный поиск целевого значения в отсортированном массиве.
     * 
     * @param array отсортированный массив целых чисел (по возрастанию)
     * @param target искомое значение
     * @return индекс target в array или -1, если элемент не найден
     * @throws IllegalArgumentException если array равен null
     */
    public static int search(int[] array, int target) {
        if (array == null) {
            throw new IllegalArgumentException("Array cannot be null");
        }
        
        // left и right задают замкнутый интервал [left, right], в котором может находиться target
        int left = 0;
        int right = array.length - 1;

        // Пока интервал не схлопнулся (не стал пустым)
        while (left <= right) {
            // Вычисляем середину, защищаясь от переполнения
            // Эквивалентно (left + right) / 2, но без риска overflow
            int mid = left + (right - left) / 2;
            
            // Получаем значение по среднему индексу
            int midValue = array[mid];

            // Сравниваем с целевым
            if (midValue == target) {
                // Нашли! Возвращаем позицию.
                return mid;
            } else if (midValue < target) {
                // Искомое значение больше, чем midValue.
                // Отбрасываем левую половину, включая mid.
                // Новый поиск в (mid + 1, right).
                left = mid + 1;
            } else { // midValue > target
                // Искомое значение меньше, чем midValue.
                // Отбрасываем правую половину, включая mid.
                // Новый поиск в (left, mid - 1).
                right = mid - 1;
            }
        }

        // Цикл завершился, left > right. Это значит, что интервал поиска пуст.
        // Следовательно, target в массиве отсутствует.
        return -1;
    }
}

Ключевые детали реализации:
Переполнение безопасность: Формула left + (right - left) / 2 критична на массивах длиной более Integer.MAX_VALUE / 2. Хотя в Java массив не может иметь такой размер из-за ограничений JVM и индексов типа int, эта привычка переносится в языки с беззнаковыми индексами (C++, Rust) и показывает профессиональный уровень кодирования.
Инвариант цикла: Перед каждой итерацией выполняется условие — все элементы левее left гарантированно меньше target, все элементы правее right гарантированно больше target. Сохранение этого инварианта — залог корректности.
Точка выхода: Условие left <= right означает, что даже когда left == right, у нас остался один кандидат на проверку. Если его проверка не дает совпадения, на следующей итерации left станет больше right и цикл завершится.


#Java #для_новичков #beginner #algorithm #sorted #binary

Рекурсивная реализация: элегантность и цена

Рекурсия выражает бинарный поиск более декларативно: «Поиск в массиве — это поиск в середине, иначе поиск в подмассиве». Код становится лаконичнее, но мы платим за это вызовами функций и расходом стековой памяти.

public class BinarySearchRecursive {

    /**
     * Публичный метод-обертка, скрывающий детали рекурсивной реализации.
     * 
     * @param array отсортированный массив целых чисел
     * @param target искомое значение
     * @return индекс target или -1
     */
    public static int search(int[] array, int target) {
        if (array == null) {
            throw new IllegalArgumentException("Array cannot be null");
        }
        // Запускаем рекурсию с полным диапазоном
        return searchRecursive(array, target, 0, array.length - 1);
    }

    /**
     * Приватный рекурсивный вспомогательный метод.
     * 
     * @param array исходный массив (не меняется)
     * @param target искомое значение
     * @param left левая граница поиска (включительно)
     * @param right правая граница поиска (включительно)
     * @return индекс target или -1
     */
    private static int searchRecursive(int[] array, int target, int left, int right) {
        // Базовый случай: интервал поиска пуст
        // Это аналог выхода из цикла while (left <= right)
        if (left > right) {
            return -1;
        }

        // Вычисляем середину
        int mid = left + (right - left) / 2;
        int midValue = array[mid];

        // Базовый случай: нашли элемент
        if (midValue == target) {
            return mid;
        }

        // Рекурсивный шаг: выбираем половину и вызываем себя
        if (midValue < target) {
            // Искомое значение больше — ищем в правой половине
            return searchRecursive(array, target, mid + 1, right);
        } else {
            // Искомое значение меньше — ищем в левой половине
            return searchRecursive(array, target, left, mid - 1);
        }
    }
}

Анализ рекурсивной версии:
Чистота: Нет изменяемых переменных в цикле. Алгоритм читается как математическая рекуррентная формула.
Стоимость вызовов: Каждый рекурсивный шаг добавляет фрейм в стек вызовов. Фрейм содержит локальные переменные mid, midValue и параметры left, right. Глубина рекурсии составляет ⌈log₂n⌉ + 1 (включая первый вызов). На массиве из миллиона элементов глубина не превысит 20 уровней. Звучит безопасно, но...
Проблема переполнения стека: Стандартный размер стека в Java потоке — 1 МБ. 20 фреймов занимают крошечную часть. Однако в средах с ограниченным стеком (встроенные системы, агрессивные настройки JVM -Xss) или при поиске в коллекциях, эмулируемых через рекурсивные структуры, риск существует. Теоретически, на массиве размером 2³⁰ (~1 миллиард) элементов глубина достигла бы 31, что все еще безопасно, но практические ограничения JVM на размер массива не позволят такой эксперимент.
Оптимизация хвостовой рекурсии: Java не гарантирует оптимизацию хвостовой рекурсии (TCE), в отличие от языков функциональной парадигмы (Scala, Haskell). Каждый вызов будет реализован полностью. Поэтому итеративная версия всегда предпочтительнее с точки зрения производительности.


#Java #для_новичков #beginner #algorithm #sorted #binary

Асимптотический анализ: время и память

Временная сложность: O(log n)
Логарифмическая сложность означает, что с каждой итерацией мы отбрасываем половину оставшихся кандидатов. Формально: пусть T(n) — время поиска в массиве размера n. Тогда T(n) = T(n/2) + O(1), где O(1) — это сравнение и вычисление mid. Решая это рекуррентное соотношение по методу мастера, получаем T(n) = Θ(log n). В худшем случае нам потребуется ⌊log₂n⌋ + 1 сравнение.
Для системы масштабирования: увеличение коллекции в 1024 раз (2¹⁰) добавит только 10 итераций. Это волшебство логарифма: поиск в миллионе записей требует максимум 20 шагов, в миллиарде — 30.

Пространственная сложность:
Итеративная версия: O(1) дополнительной памяти. Используем фиксированный набор переменных (left, right, mid, midValue), не зависящий от размера входных данных. Масштабирование идеальное.
Рекурсивная версия: O(log n) из-за стековых фреймов. Каждый вызов создает фрейм (~24-32 байта на локальные переменные, указатель на return address и т.д.). При глубине log n общий объем стека линейно зависит от log n. На практике это означает: если ваша JVM позволяет глубину стека 1000 вызовов, вы безопасно ищете в массивах до 2¹⁰⁰⁰ элементов (число с 300 знаками), что в цифровом виде превышает количество атомов во Вселенной.


Границы применимости: когнитивный диссонанс производительности

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

1. При малых n (n < 50-100)
Константы в алгоритмах имеют значение. Бинарный поиск требует деления, сложения, ветвления, что накладывает фиксированный налог в несколько процессорных циклов. Линейный поиск для n = 10 может выполниться за 10 простых сравнений, тогда как бинарный — за 4-5 сложных операций. Разница в наносекундах настолько мала, что не компенсирует накладные расходы на предварительную сортировку (если она не была сделана заранее).
Точка окупаемости зависит от архитектуры процессора, языка и стоимости операции сравнения. Для примитивов в Java порог может лежать в диапазоне 50-100 элементов. Для объектов, где сравнение требует дорогого Comparator или метода compareTo, порог смещается влево.

2. При динамических данных с частой вставкой
Если ваша библиотека пополняется новыми книгами каждые 10 минут, а поиск пользователей идет каждую секунду, поддержание отсортированности становится болью. Вставка в отсортированный массив стоит O(n) (сдвиг всех правых элементов). Для n = 10⁶ каждая вставка — это миллион операций копирования. Даже если вы используете сбалансированные структуры вроде TreeSet или PriorityQueue, где вставка O(log n), константы выше, чем в HashSet, и скорость поиска по индексу теряется.
В таких сценариях часто используют гибридный подход: данные хранятся в неотсортированном виде, периодически (например, раз в час) накопленное за период сортируется и сливается с основным отсортированным массивом методом сортировки слиянием. Или используются блочные структуры (bucketed arrays), где каждый блок отсортирован внутри, а новые элементы собираются в буфере.

3. Когда стоимость сравнения доминирует
В бинарном поиске мы всегда делаем log n сравнений. В линейном — в среднем n/2. Если n = 1000, бинарный поиск сделает ~10 сравнений, линейный — 500. Но что если каждое сравнение — это взятие блока данных с диска или сеть RPC? Тогда log n vs n/2 не имеет значения: оба варианта требуют одного дискового доступа (если данные кешированы), и разница в 490 сравнений — просто CPU-циклы в памяти. Бинарный поиск выигрывает в вычислительной сложности, но не в I/O.

4. Когда данные не помещаются в память, но отсортированы
Если массив лежит на диске и доступ к нему происходит через постраничную загрузку (paging), бинарный поиск становится врагом локальности. Итерация 0 читает страницу с середины. Итерация 1 читает страницу с четвертью или тремя четвертями — совершенно другая страница. Для дисковых массивов может быть выгоднее использовать B-деревья или интерполяционный поиск, учитывающий вероятность расположения данных на носителе.

#Java #для_новичков #beginner #algorithm #sorted #binary

Глава 4: Эффективный поиск. Бинарный и не только

Модификации и родственные методы

Ранее мы рассмотрели классический бинарный поиск, который эффективно отвечает на вопрос «есть ли элемент X в массиве?» и возвращает случайную позицию в случае дубликатов. Но реальные задачи редко сводятся к такому простому запросу. Что делать, если вам нужно найти все книги с заданным названием в каталоге, где дубликаты вполне закономерны (например, несколько экземпляров одного издания)? А как насчет поиска диапазона — всех книг, выпущенных между 2020 и 2023 годом включительно? Или если вы знаете, что данные распределены не просто монотонно, а равномерно, и хотите использовать это свойство для ускорения?
Эти вопросы приводят нас к модификациям классического алгоритма и его альтернативам. Каждая модификация сохраняет логарифмическую природу, но меняет инварианты и условия завершения.


Поиск границ в массиве с дубликатами

Проблема неоднозначности стандартной реализации

Представьте массив книг, отсортированных по названию:

String[] titles = {
    "Война и мир", "Война и мир", "Война и мир", 
    "Гарри Поттер", "Гарри Поттер", 
    "Мастер и Маргарита"
};

Вызываем Arrays.binarySearch(titles, "Война и мир"). Результат? Не определен. Javadoc гарантирует лишь, что будет возвращен какой-то индекс из диапазона дубликатов, если они существуют. Это недопустимо, когда вам нужен первый экземпляр для отображения в UI или последний для расчета границ диапазона.

Инвариант для поиска первого вхождения

Чтобы гарантированно найти самую левую позицию элемента, мы меняем логику завершения. Классический поиск завершается при точном совпадении array[mid] == target. Мы же должны продолжать поиск в левой половине даже после нахождения совпадения, потому что там может скрываться еще более ранний дубликат.

Новый инвариант: алгоритм поддерживает две зоны — переднюю, где все элементы строго меньше target, и заднюю, где элементы больше или равны target. Когда цикл завершается, указатель left будет указывать на первый элемент, равный target, или на позицию вставки, если target отсутствует.


#Java #для_новичков #beginner #algorithm #sorted #binary

public class BinarySearchBounds {

    /**
     * Поиск первого вхождения целевого значения.
     * Если элемент отсутствует, возвращает индекс, где он должен быть вставлен.
     * 
     * @return индекс первого вхождения target или potential insertion point
     */
    public static int findFirst(int[] array, int target) {
        if (array == null) throw new IllegalArgumentException("Array cannot be null");
        
        int left = 0;
        int right = array.length - 1;
        int result = -1; // Потенциальная позиция вставки
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = array[mid];
            
            if (midValue < target) {
                // Цель строго правее
                left = mid + 1;
            } else if (midValue > target) {
                // Цель строго левее
                right = mid - 1;
            } else {
                // Нашли совпадение, но продолжаем искать в левой половине
                result = mid; // Запомнили потенциальный ответ
                right = mid - 1; // Сдвинули границу влево
            }
        }
        
        // Если result остался -1, target не найден. Можно вернуть left как точку вставки.
        return result != -1 ? result : left;
    }
    
    /**
     * Поиск последнего вхождения целевого значения.
     */
    public static int findLast(int[] array, int target) {
        if (array == null) throw new IllegalArgumentException("Array cannot be null");
        
        int left = 0;
        int right = array.length - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = array[mid];
            
            if (midValue < target) {
                left = mid + 1;
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                result = mid; // Запомнили потенциальный ответ
                left = mid + 1; // Ключевое отличие: сдвигаемся вправо
            }
        }
        
        return result != -1 ? result : left - 1; // left указывает после последнего <= target
    }
}

Ключевые отличия от классического поиска:
Сохранение состояния: Переменная result запоминает последнюю удачную позицию. Это нарушает чистоту инварианта, но необходимо для корректности.
Асимметричные действия: При нахождении target мы не выходим, а сдвигаем границу в сторону, противоположную от искомой границы. Для findFirst — влево, для findLast — вправо.
Выходное значение: В отсутствие элемента метод возвращает не -1, а точку вставки. Это делает API более универсальным для построения диапазонных запросов.
Поиск последнего вхождения: симметричная логика

Метод findLast зеркально отражает findFirst. Когда находится совпадение, мы продолжаем поиск в правой половине, потому что там может быть еще один дубликат. После завершения цикла left указывает на первый элемент строго больше target, поэтому left - 1 — это последний элемент, меньший или равный target.

#Java #для_новичков #beginner #algorithm #sorted #binary

Поиск диапазона

От границ к диапазону: композиция операций

Теперь, когда у нас есть инструменты для поиска границ, задача «найти все книги, изданные в 2020-2023 годах» решается композицией:

public class LibraryRangeSearch {

    static class Book implements Comparable<Book> {
        String title;
        int year;
        
        // Конструктор, геттеры...
        
        @Override
        public int compareTo(Book other) {
            return Integer.compare(this.year, other.year);
        }
    }
    
    /**
     * Поиск всех книг в заданном диапазоне лет [startYear, endYear].
     * Возвращает подмассив (views) для экономии памяти.
     */
    public static List<Book> findBooksByYearRange(Book[] library, int startYear, int endYear) {
        if (library == null || startYear > endYear) {
            return Collections.emptyList();
        }
        
        // Создаем фиктивные книги-границы для поиска
        Book startDummy = new Book("", startYear);
        Book endDummy = new Book("", endYear);
        
        // Находим первую книгу с year >= startYear
        int leftIndex = findFirstIndex(library, startDummy);
        
        // Находим последнюю книгу с year <= endYear
        int rightIndex = findLastIndex(library, endDummy);
        
        if (leftIndex == -1 || rightIndex == -1 || leftIndex > rightIndex) {
            return Collections.emptyList();
        }
        
        // Возвращаем view для избежания копирования
        return Arrays.asList(library).subList(leftIndex, rightIndex + 1);
    }
    
    // Адаптер для работы с Comparable объектами
    private static int findFirstIndex(Book[] array, Book target) {
        int left = 0, right = array.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = array[mid].compareTo(target);
            if (cmp < 0) left = mid + 1;
            else if (cmp > 0) right = mid - 1;
            else { result = mid; right = mid - 1; }
        }
        return result != -1 ? result : left;
    }
    
    private static int findLastIndex(Book[] array, Book target) {
        int left = 0, right = array.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int cmp = array[mid].compareTo(target);
            if (cmp < 0) left = mid + 1;
            else if (cmp > 0) right = mid - 1;
            else { result = mid; left = mid + 1; }
        }
        return result != -1 ? result : left - 1;
    }
}

Анализ производительности: Поиск диапазона требует двух бинарных поисков — O(log n) + O(log n) = O(log n). После этого мы получаем непосредственный доступ к результату за O(1). Если результатов много (k элементов), итоговая сложность O(log n + k). Это намного эффективнее линейного сканирования всей библиотеки O(n).

Важное замечание: Метод возвращает subList, который является view исходного массива. Изменения в исходном массиве отразятся в результате. Для защиты нужно скопировать: new ArrayList<>(Arrays.asList(...).subList(...)).


#Java #для_новичков #beginner #algorithm #sorted #binary

Альтернативный подход: поиск нижней границы + линейное сбирание

Если вы знаете, что диапазон редко содержит много элементов (например, книги за конкретный год в библиотеке с редкими изданиями), можно оптимизировать:

public static List<Book> findBooksByYearRangeOptimized(Book[] library, int startYear, int endYear) {
    int startIdx = findFirstIndex(library, new Book("", startYear));
    if (startIdx == -1 || startIdx >= library.length) return Collections.emptyList();
    
    List<Book> result = new ArrayList<>();
    for (int i = startIdx; i < library.length && library[i].year <= endYear; i++) {
        result.add(library[i]);
    }
    return result;
}

Этот подход имеет сложность O(log n + k) в худшем случае, но с меньшими константами, потому что второй бинарный поиск заменен на последовательное чтение (кэш-приятно).


Интерполяционный поиск — когда данные говорят сами за себя

Интуиция: зачем всегда делить пополам?

Представьте телефонный справочник, где фамилии распределены равномерно по алфавиту. Ищете «Иванов». Классический бинарный поиск откроет справочник ровно посередине — на букве «М», затем на «Г», затем на «Д»... Вместо этого можно интерполировать: поскольку «И» находится примерно на 10% алфавита, сразу открыть страницу на 10% от общего объема.

Интерполяционный поиск заменяет слепое деление пополам на адресный расчет вероятной позиции на основе значений границ.

Математическая формула интерполяции

Если array[left] и array[right] известны, и target лежит между ними, то при равномерном распределении его позиция должна быть пропорциональна:

mid = left + (target - array[left]) * (right - left) / (array[right] - array[left])

Это формула линейной интерполяции. Она вычисляет, насколько далеко target находится от левой границы в долях от общего диапазона значений, и применяет этот же коэффициент к индексам.


#Java #для_новичков #beginner #algorithm #sorted #binary

Реализация и инварианты

public class InterpolationSearch {
    
    /**
     * Интерполяционный поиск для равномерно распределенных целочисленных данных.
     * ВНИМАНИЕ: требует, чтобы array[left] < array[right] и данные были равномерными!
     */
    public static int search(int[] array, int target) {
        if (array == null) throw new IllegalArgumentException("Array cannot be null");
        
        int left = 0;
        int right = array.length - 1;
        
        // Условие array[left] <= target <= array[right] критично для формулы
        while (left <= right && target >= array[left] && target <= array[right]) {
            // Если диапазон схлопнулся, переходим к линейному поиску
            if (array[left] == array[right]) {
                if (array[left] == target) return left;
                break; // Не найден
            }
            
            // Интерполяция позиции
            // Предотвращаем деление на ноль проверкой выше
            int mid = left + (target - array[left]) * (right - left) / (array[right] - array[left]);
            
            // Защита от выхода за границы (возможна при неравномерных данных)
            mid = Math.max(left, Math.min(mid, right));
            
            int midValue = array[mid];
            
            if (midValue < target) {
                left = mid + 1;
            } else if (midValue > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        
        // Пост-проверка границ
        if (left <= right && array[left] == target) return left;
        return -1;
    }
}

Критические условия применимости:
Равномерное распределение: Формула работает, если разность между соседними элементами примерно постоянна. Если данные сгущаются в некоторых зонах (например, 90% книг изданы в 2020-х, а остальные — растянуты на 50 лет), интерполяция будет постоянно ошибаться, откатываясь к бинарному поведению или хуже.
Отсутствие повторений на границах: Если array[left] == array[right], формула приводит к делению на ноль. В этом случае алгоритм должен деградировать к линейному поиску в этом поддиапазоне.
Целочисленное переполнение: Выражение (target - array[left]) * (right - left) может переполнить int при больших значениях. Для production-кода рекомендуется использовать long для промежуточных расчетов.


Анализ сложности и парадоксы

Средний случай: При равномерном распределении интерполяционный поиск достигает O(log log n). Это практически константа: для массива из 1 миллиарда элементов потребуется ~5 итераций. Это достигается за счет того, что каждый шаг не просто делит диапазон пополам, а приближается к цели экспоненциально быстро.

Худший случай: Если данные неравномерны (например, [1, 2, 3, 4, 5, 1000, 1001, 1002, 1003]), интерполяция может снова и снова попадать в «пустые» зоны, требуя O(n) сравнений. Это хуже бинарного поиска.

Практический вывод: Интерполяционный поиск имеет смысл применять только тогда, когда вы точно знаете характер распределения данных и уверены в его равномерности. В остальных случаях бинарный поиск более надежен. В Java стандартная библиотека не содержит интерполяционного поиска из-за его узкой применимости и риска деградации.


#Java #для_новичков #beginner #algorithm #sorted #binary

Глава 4: Эффективный поиск. Бинарный и не только

Практика

Сегодня мы применим знания о эффективном поиске на проекте «Библиотека».

Мы отсортируем список книг по названию, реализуем бинарный поиск для нахождения первой книги заданного автора (в отсортированном списке), и проведём сравнение времени выполнения линейного и бинарного поиска на коллекциях разных размеров. Это поможет наглядно увидеть преимущества логарифмического поиска O(log n) над линейным O(n), понять предпосылки (сортировка данных) и границы применимости (когда сортировка окупается).

Подготовка к уроку

Перед началом убедитесь, что проект готов, и вспомните ключевые концепции:
Бинарный поиск работает только на отсортированных данных, делит интервал пополам.
Линейный поиск — перебор O(n), всегда работает.
Сортировка O(n log n) — предпосылка для бинарного.

Откройте проект «Библиотека»: Убедитесь, что List<Book> books содержит достаточно книг (добавьте метод для генерации тестовых данных).
Импортируйте пакеты: java.util.Arrays (для бинарного поиска), java.util.Random (для генерации данных).
Генерация больших данных: Создайте метод generateBooks(int size) для создания списков размером 100, 10 000, 1 000 000 (используйте Random для title/author/year).


Отсортировать книги по названию

Обновите Book для Comparable (если не сделано): Реализуйте compareTo по title (this.title.compareTo(other.title)).
Создайте метод sortByTitle(): Используйте Collections.sort(books) — сортирует по Comparable (названию).
Вывод: После сортировки вызовите printAllBooks() для проверки.


Реализовать бинарный поиск для нахождения первой книги заданного автора

Отсортируйте по автору: Создайте Comparator<Book> byAuthor = Comparator.comparing(Book::getAuthor);, затем books.sort(byAuthor).

Реализуйте метод findFirstBookByAuthor(String author):
Используйте Arrays.binarySearch, но поскольку books — List, преобразуйте в массив или реализуйте вручную.

Вручную:

int low = 0, high = books.size() - 1; 

while (low <= high) {
        mid = (low + high) / 2; cmp = books.get(mid).getAuthor().compareTo(author);

        if (cmp < 0) low = mid + 1; 
        else if (cmp > 0) high = mid - 1;
        else { // Найден, найти первый: 
                  while (mid > 0 && books.get(mid-1).getAuthor().equals(author)) 
                  mid--; 
                  return books.get(mid); 
                } 
}

Если не найден — return null.

Проверка: После сортировки вызовите метод, выведите найденную книгу.


Сравнить время линейного и бинарного поиска на разных размерах

Реализуйте линейный поиск: Метод linearSearchByAuthor(String author) — for-each, если совпадение — return book.
Измерение времени: Используйте System.nanoTime() before/after.

Тест на размерах:
Для 100: generateBooks(100), sortByAuthor, time linear vs binary (поиск рандомного автора).
Для 10 000 и 1 000 000: Аналогично, усредните по 100 запускам.
Выводите: "Для n=[size]: Линейный: [time ns], Бинарный: [time ns]".

Анализ: Точка окупаемости сортировки + бинарный поиск vs множественный линейный поиск
Точка окупаемости — момент, когда стоимость сортировки + m бинарных поисков становится меньше m линейных поисков.

Расчёт:
Линейный: O(n) per search → m * n
Бинарный: O(n log n) sort + m * log n
Окупаемость: n log n + m log n < m n → m > (n log n) / (n - log n) ≈ log n (для больших n)
Пример: n = 1000, log n ≈ 10 — окупаемость после ~10 поисков.
n = 1 млн, log n ≈ 20 — после ~20 поисков.
Граница: Для малого m или n — линейный дешевле (нет сортировки).
В библиотеке: Если поиски редки — линейный; если часты — sort + binary.

#Java #для_новичков #beginner #algorithm #sorted #binary #практика