11. Алгоритмы и их сложность Flashcards
Что такое сортировка?
Сортировка пузырьком:
Алгоритм просматривает массив и сравнивает каждую пару соседних элементов. Когда он встречает пару элементов, расположенных не по порядку, происходит замена двух элементов местами. O(n^2)
———————————————————————————-
Сортировка вставками:
Этот алгоритм разделяет оригинальный массив на сортированный и несортированный подмассивы.
Длина сортированной части равна 1 в начале и соответствует первому (левому) элементу в массиве. После этого остается итерировать массив и расширять отсортированную часть массива одним элементом с каждой новой итерацией.
Сортировка выбором:
Запоминаем значение и индекс 0 элемента и во втором цикле ищем минимальное значение в остальном списке(запоминаем индекс и значение) - потом меняем их местами. O(n^2)
———————————————————————————-
Сортировка слиянием:
Сортировка слиянием эффективнее, чем примеры алгоритмов сортировки, представленные выше, благодаря использованию рекурсии и подходу «разделяй и властвуй».
Массив делится на два подмассива, а затем происходит:
1) Сортировка левой половины массива (рекурсивно)
2) Сортировка правой половины массива (рекурсивно)
3) Слияние
O(nlogn)
———————————————————————————-
Расскажите об интерфейсах Comparable и Comparator?
Для того, чтобы объекты можно было сравнить и сортировать, они должны применять интерфейс Comparable. При применении интерфейса он типизируется текущим классом.
Интерфейс Comparable содержит один единственный метод int compareTo(E item), который сравнивает текущий объект с объектом, переданным в качестве параметра. Если этот метод возвращает отрицательное число, то текущий объект будет располагаться перед тем, который передается через параметр. Если метод вернет положительное число, то, наоборот, после второго объекта. Если метод возвратит ноль, значит, оба объекта равны.
Например TreeSet мы не сможем типизировать классом, который не реализует интерфейс, поскольку в случае добавления объектов TreeSet не будет знать, как их сравнивать
———————————————————————————-
Однако перед нами может возникнуть проблема, что если разработчик не реализовал в своем классе, который мы хотим использовать, интерфейс Comparable, либо реализовал, но нас не устраивает его функциональность, и мы хотим ее переопределить? На этот случай есть еще более гибкий способ, предполагающий применение интерфейса Comparator.
Интерфейс Comparator содержит ряд методов, ключевым из которых является метод compare()
Метод compare также возвращает числовое значение - если оно отрицательное, то объект a предшествует объекту b, иначе - наоборот. А если метод возвращает ноль, то объекты равны. Для применения интерфейса нам вначале надо создать класс компаратора, который реализует этот интерфейс.
Начиная с JDK 8 в механизм работы компараторов были внесены некоторые дополнения. В частности, теперь мы можем применять сразу несколько компараторов по принципу приоритета. Интерфейс компаратора определяет специальный метод по умолчанию thenComparing, который позволяет использовать цепочки компараторов для сортировки набора
Comparator pcomp = new PersonNameComparator().thenComparing(new PersonAgeComparator());
TreeSet people = new TreeSet(pcomp);
Что такое бинарное дерево?
Бинарное дерево представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух дочерних узлов. Как правило, первый называется родительским узлом или корнем дерева (root), а дочерние узлы называются левым и правым наследниками.
Бинарное дерево либо является пустым, либо состоит из данных и двух поддеревьев, каждое из которых может быть пустым. Каждое поддерево в свою очередь тоже является деревом. Узлы без наследников принято называть листьями.
Для такого дерева должны выполняться следующие условия:
Левое и правое поддерево так же являются бинарными деревьями;
У всех узлов левого поддерева произвольного узла xx значения ключей данных меньше значения ключа данных самого узла xx;
У всех узлов правого поддерева произвольного узла xx значения ключей данных больше либо равны значению ключа данных самого узла xx.
Как можно отсортировать с помощью обхода бинарного дерева?
При условии, что у всех узлов дерева значение левого потомка меньше значения родителя, а правого больше - рекурсивно обойти левое поддерево, вывести значение узла, потом обойти правое поддерево.Т.е. в порядке in-order.
TreeSet и TreeMap основаны на BST(binary search tree)
Опишите быструю сортировку?
Быстрая сортировка происходит рекурсивно. Сначала мы сортируем массив относительно значения опорного элемента, те что меньше перемещаются в левую часть, те что больше в правую. Затем рекурсивно сортируем левый подмассив и правый. Сложность O(nlogn)
