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
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; // Медиана в середине
}

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++];
    }
}

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 затронутое поддерево
        }
    }
}

import java.util.Arrays;
import java.util.Comparator;

public class Task210126 {
    public static void main(String[] args) {
        Integer[] arr = {3, 2, 8, 1, 6};
        Comparator<Integer> comp = Comparator.comparingInt(i -> i % 2);
        Arrays.sort(arr, comp);
        System.out.println(Arrays.toString(arr));
    }
}

import java.util.Random;

public class Task220126 {
    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        Random r1 = new Random(seed);
        Random r2 = new Random(seed);

        int a = r1.nextInt();
        int b = r2.nextInt();

        System.out.println(a == b);
    }
}

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;
    }
}

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);
        }
    }
}

import java.util.*;

public class Task230126 {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("apple", "banana", "grape", "orange");
        int index1 = Collections.binarySearch(list, "grape");
        int index2 = Collections.binarySearch(list, "kiwi");
        System.out.println("Grape: " + index1);
        System.out.println("Kiwi: " + index2);
    }
}