Как отсортировать коллекцию без Comparator и Comparable

# Сортировка коллекции без Comparator и Comparable

Проблема

Тебе нужно отсортировать коллекцию, но ты не можешь:

• Использовать Comparable (не вправе изменять класс)
• Использовать Comparator (сложная логика или её не существует)

Решение 1: Вынуть в массив, отсортировать, вернуть

public class User {
    private String name;
    private int age;
    
    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class SortWithoutComparator {
    
    // Сортировка вручную через пузырьковую сортировку
    public static void bubbleSort(List<User> users, String field) {
        int n = users.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                boolean shouldSwap = false;
                
                if ("age".equals(field)) {
                    shouldSwap = users.get(j).age > users.get(j + 1).age;
                } else if ("name".equals(field)) {
                    shouldSwap = users.get(j).name.compareTo(users.get(j + 1).name) > 0;
                }
                
                if (shouldSwap) {
                    // Меняем местами
                    User temp = users.get(j);
                    users.set(j, users.get(j + 1));
                    users.set(j + 1, temp);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        List<User> users = Arrays.asList(
            new User("Alice", 30),
            new User("Bob", 25),
            new User("Charlie", 35)
        );
        
        System.out.println("До сортировки: " + users);
        bubbleSort(users, "age");
        System.out.println("После сортировки по возрасту: " + users);
        // Bob (25), Alice (30), Charlie (35)
    }
}

Минусы: медленно для больших коллекций (O(n²)), не масштабируемо.

Решение 2: Быстрая сортировка (QuickSort)

public class QuickSortExample {
    
    public static void quickSort(List<Integer> list, int low, int high) {
        if (low < high) {
            int pi = partition(list, low, high);
            quickSort(list, low, pi - 1);
            quickSort(list, pi + 1, high);
        }
    }
    
    private static int partition(List<Integer> list, int low, int high) {
        int pivot = list.get(high);
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (list.get(j) < pivot) {
                i++;
                // Меняем
                int temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);
            }
        }
        
        // Меняем pivot на место
        int temp = list.get(i + 1);
        list.set(i + 1, list.get(high));
        list.set(high, temp);
        
        return i + 1;
    }
    
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6));
        System.out.println("До: " + numbers);
        
        quickSort(numbers, 0, numbers.size() - 1);
        
        System.out.println("После: " + numbers);
        // [1, 1, 2, 3, 4, 5, 6, 9]
    }
}

Производительность: O(n log n) в среднем, намного лучше чем bubble sort.

Решение 3: Merge Sort (стабильная сортировка)

public class MergeSortExample {
    
    public static void mergeSort(List<Integer> list, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(list, left, mid);
            mergeSort(list, mid + 1, right);
            merge(list, left, mid, right);
        }
    }
    
    private static void merge(List<Integer> list, int left, int mid, int right) {
        List<Integer> leftArr = new ArrayList<>(list.subList(left, mid + 1));
        List<Integer> rightArr = new ArrayList<>(list.subList(mid + 1, right + 1));
        
        int i = 0, j = 0, k = left;
        
        while (i < leftArr.size() && j < rightArr.size()) {
            if (leftArr.get(i) <= rightArr.get(j)) {
                list.set(k++, leftArr.get(i++));
            } else {
                list.set(k++, rightArr.get(j++));
            }
        }
        
        while (i < leftArr.size()) {
            list.set(k++, leftArr.get(i++));
        }
        
        while (j < rightArr.size()) {
            list.set(k++, rightArr.get(j++));
        }
    }
    
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6));
        System.out.println("До: " + numbers);
        mergeSort(numbers, 0, numbers.size() - 1);
        System.out.println("После: " + numbers);
    }
}

Решение 4: Поменять используя Stream API (функциональный подход)

Можно создать функцию-сравниватель через reflection (без явного Comparator):

public class DynamicSort {
    
    // Сортировка по полю через reflection
    public static <T> void sortByField(List<T> list, String fieldName, boolean ascending) 
            throws NoSuchFieldException, IllegalAccessException {
        
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = 0; j < list.size() - i - 1; j++) {
                T obj1 = list.get(j);
                T obj2 = list.get(j + 1);
                
                // Получаем значения поля через reflection
                java.lang.reflect.Field field = obj1.getClass().getDeclaredField(fieldName);
                field.setAccessible(true);
                
                Object val1 = field.get(obj1);
                Object val2 = field.get(obj2);
                
                // Сравниваем
                @SuppressWarnings("unchecked")
                int comparison = ((Comparable<Object>) val1).compareTo(val2);
                
                if ((ascending && comparison > 0) || (!ascending && comparison < 0)) {
                    // Меняем
                    T temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
    }
    
    public static void main(String[] args) throws Exception {
        List<User> users = Arrays.asList(
            new User("Alice", 30),
            new User("Bob", 25),
            new User("Charlie", 35)
        );
        
        System.out.println("До: " + users);
        sortByField(users, "age", true); // Сортируем по возрасту по возрастанию
        System.out.println("После: " + users);
    }
}

Решение 5: Создать собственный comparator на лету

Если нельзя использовать встроенный Comparator, сделай свой:

public class CustomComparator<T> {
    private java.util.function.BiFunction<T, T, Integer> comparison;
    
    public CustomComparator(java.util.function.BiFunction<T, T, Integer> comparison) {
        this.comparison = comparison;
    }
    
    public int compare(T a, T b) {
        return comparison.apply(a, b);
    }
    
    public void sort(List<T> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = 0; j < list.size() - i - 1; j++) {
                if (compare(list.get(j), list.get(j + 1)) > 0) {
                    T temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
    }
}

public class CustomComparatorExample {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6);
        
        CustomComparator<Integer> comparator = new CustomComparator<>(
            (a, b) -> Integer.compare(a, b)
        );
        
        comparator.sort(numbers);
        System.out.println(numbers); // [1, 1, 2, 3, 4, 5, 6, 9]
    }
}

Решение 6: Использовать кастомный интерфейс (подобие Comparable)

public interface Sortable {
    int compareWith(Object other);
}

public class SortableUser implements Sortable {
    private String name;
    private int age;
    
    public SortableUser(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public int compareWith(Object other) {
        SortableUser that = (SortableUser) other;
        return Integer.compare(this.age, that.age);
    }
    
    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class BubbleSortWithInterface {
    public static void sort(List<? extends Sortable> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = 0; j < list.size() - i - 1; j++) {
                if (list.get(j).compareWith(list.get(j + 1)) > 0) {
                    Sortable temp = list.get(j);
                    list.set(j, (Sortable) list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        List<SortableUser> users = Arrays.asList(
            new SortableUser("Alice", 30),
            new SortableUser("Bob", 25),
            new SortableUser("Charlie", 35)
        );
        
        sort(users);
        System.out.println(users);
    }
}

Сравнение всех подходов

Практический совет

Если ты на собеседовании:

1. Первый ответ: "Обычно используют Collections.sort() с Comparator"
2. Если интервьюер запрещает: "Можно реализовать собственную сортировку через Bubble/Quick/Merge Sort"
3. Покажи реализацию Quick Sort или Merge Sort
4. Объясни временную сложность: O(n log n) в среднем

Не забудь:

• Bubble Sort O(n²) - медленно, но просто
• Quick Sort O(n log n) - быстрее, но может быть худший случай
• Merge Sort O(n log n) - гарантированная скорость, но требует доп памяти

Знание этих алгоритмов сортировки показывает понимание основ CS.