11. Алгоритмы и их сложность Flashcards
Что такое сортировка?
Глупая сортировка
Самая (наверное) простая сортировка. Суть - идешь по массиву, сравниваешь пары. Меняешь в них элементы местами. Если поменял - начинаешь заново. С начала массива. O(n^3)
———————————————————————————-
Сортировка пузырьком:
Суть. Пузырек (как правило - наибольший элемент) - всплывает. Далее его не трогаем и движемся по массиву с начала, пока все “пызурьки” не всплывут.
Алгоритм просматривает массив и сравнивает каждую пару соседних элементов (это считай 1 цикл, внутренний). Когда он встречает пару элементов, расположенных не по порядку, происходит замена двух элементов местами. (плюс эту операцию надо сделать по количеству пар, т.е. массива длина -1)
O(n^2)
for (int i = 0; i < arr2.length - 1; i++) { //so we need to swap all elements pairs
for (int j = 0; j < arr2.length - 1 - i; j++) { //we or reduce length by i, since the biggest el is "bubbled up"
// every time we will reduce Q of internal iterations by i (and i increases)
if (arr2[j] > arr2[j + 1]) {
int tmp = arr2[j];
arr2[j] = arr2[j + 1];
arr2[j + 1] = tmp;
}
}
}
----------------------------------------------------------------------------------
Сортировка вставками:
Этот алгоритм разделяет оригинальный массив на сортированный и несортированный подмассивы.
Длина сортированной части равна 1 в начале и соответствует первому (левому) элементу в массиве. После этого остается итерировать массив и расширять отсортированную часть массива одним элементом с каждой новой итерацией.
После расширения новый элемент помещается на свое место в отсортированном подмассиве. Это происходит путём сдвига всех элементов вправо, пока не встретится элемент, который не нужно двигать.
((т.е. запоминаем индексы))
O(n ^ 2).
———————————————————————————-
Сортировка выбором:
Запоминаем значение и индекс 0 элемента и во втором цикле ищем минимальное значение в остальном списке (запоминаем индекс и значение) - потом меняем их местами. O(n^2) - но чуть быстрее пузырьковой в общем.
static Integer findSmallestEl(List list) {
int el = list.get(0);
int smallestInd = 0;
for (int i = 0; i < list.size(); i++) {
if (list.get(i) < el) {
el = list.get(i);
smallestInd = i;
}
}
return smallestInd;
}
static List selectionSort(List list) {
List sortedList = new ArrayList<>();
int listSize = list.size();
for (int i = 0; i < listSize; i++){
int smallestElInd = findSmallestEl(list);
sortedList.add(list.get(smallestElInd));
list.remove(smallestElInd); //no way to get concurrent since we jsut remove elements from stand-alone list, not changing it's internal structure, say by add or anything else
//this way, list.size() is reducing too
}
return sortedList;
} ---------------------------------------------------------------------------------- Сортировка слиянием: Сортировка слиянием эффективнее, чем примеры алгоритмов сортировки, представленные выше, благодаря использованию рекурсии и подходу «разделяй и властвуй».
Массив делится на два подмассива, а затем происходит:
1) Сортировка левой половины массива (рекурсивно)
2) Сортировка правой половины массива (рекурсивно)
3) Слияние
O(nlogn)
———————————————————————————-
Быстрая сортировка - см. далее, но основана она также на “разделяй и влавствуй алгоритме”
Расскажите об интерфейсах Comparable и Comparator?
Для того, чтобы объекты можно было сравнить и сортировать, они должны применять интерфейс Comparable. При применении интерфейса он типизируется текущим классом.
public interface Comparable {
public int compareTo(T o);
}
Интерфейс Comparable содержит один единственный метод int compareTo(E item), который сравнивает текущий объект с объектом, переданным в качестве параметра. Если этот метод возвращает отрицательное число, то текущий объект будет располагаться перед тем, который передается через параметр. Если метод вернет положительное число, то, наоборот, после второго объекта. Если метод возвратит ноль, значит, оба объекта равны.
Например TreeSet мы не сможем типизировать классом, который не реализует интерфейс, поскольку в случае добавления объектов TreeSet не будет знать, как их сравнивать.
Но, в-общем виде TreeSet и TreeMap построены на дереве поиска (элементов с одинаковыми ключами быть не может). Элементы хранимые в этой структуре (без определения внешнего контракта сравнения) обязаны реализовывать интерфейс Comparable.
equals здесь - не используется.
Arrays.sort(), Collections.sort() - сравниваемые элементы должны
реализовывать этот интерфейс.
Это - ЕСЛИ мы (или тот класс, что к нам пришел) может реализовать данный интерфейс
class ComparableUser implements Comparable { //with Comparable
String name;
int age;
public ComparableUser(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(ComparableUser o) {
int compare = Integer.compare(this.age, o.age);
if (compare != 0) {
return compare;
}
return this.name.compareTo(o.name); //String already implements comparable!
}
@Override
public String toString() {
return "ComparableUser{" +
"name='" + name + '\'' +
" age=" + age +
'}';
}
}
Однако перед нами может возникнуть проблема, что если разработчик не реализовал в своем классе, который мы хотим использовать, интерфейс Comparable, либо реализовал, но нас не устраивает его функциональность, и мы хотим ее переопределить? Либо этот класс просто пришел со сторонней библиотеки ?
На этот случай есть еще более гибкий способ, предполагающий применение интерфейса Comparator.
Интерфейс Comparator содержит ряд методов, ключевым из которых является метод compare()
Метод compare также возвращает числовое значение - если оно отрицательное, то объект a предшествует объекту b, иначе - наоборот. А если метод возвращает ноль, то объекты равны. Для применения интерфейса нам вначале надо создать класс компаратора, который реализует этот интерфейс.
Начиная с JDK 8 в механизм работы компараторов были внесены некоторые дополнения. В частности, теперь мы можем применять сразу несколько компараторов по принципу приоритета. Интерфейс компаратора определяет специальный метод по умолчанию thenComparing, который позволяет использовать цепочки компараторов для сортировки набора
Comparator pcomp = new PersonNameComparator().thenComparing(new PersonAgeComparator());
TreeSet people = new TreeSet(pcomp);
Но в целом, если не трогать лямбда выражения и анонимные классы (т.е. реализовывать по-старинке с помощью отдельного класса, будет выглядеть как-то так:
class User2 { //external class
String name;
int age;
public User2(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "ComparableUser{" +
"name='" + name + '\'' +
" age=" + age +
'}';
}
}
class UserComparator implements Comparator {//without Comparable (User from…. outside), but with Comparator
@Override
public int compare(User2 o1, User2 o2) {
int compare = Integer.compare(o1.age, o2.age);
if (compare != 0) {
return compare;
}
return o1.name.compareTo(o2.name);
} }
и вызов: Arrays.sort(comparableUsers, new UserComparator());
С J.8:
Comparator byRanking =
(Player player1, Player player2) -> Integer.compare(player1.getRanking(), player2.getRanking());
OR:
Comparator byRanking = Comparator
.comparing(Player::getRanking);
Comparator byAge = Comparator
.comparing(Player::getAge);
Что такое бинарное дерево?
Деревья призваны сочетать в себе плюсы массива и связного списка (т.е. быстрый доступ к элементу и быстрое добавление). Есть разные деревья. Например, дерево где более двух потомков - многопутевое.
Распространенный пример дерева — иерархическая файловая структура в ком-
пьютерной системе. Корневой каталог устройств является корнем дерева. Каталоги, непосредственно вложенные в корневой каталог, являются его потомками. Количество уровней вложения подкаталогов может быть сколь угодно большим. Файлы соответствуют листьям, так как они не имеют потомков.
Конечно, иерархическая файловая структура не является двоичным деревом,
потому что каталог может иметь много потомков.
Бинарное дерево представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух дочерних узлов (т.е. ДВА, один, или ноль). Как правило, первый называется родительским узлом или корнем дерева (root), а дочерние узлы называются левым и правым наследниками.
Бинарное дерево либо является пустым, либо состоит из данных и двух поддеревьев, каждое из которых может быть пустым. Каждое поддерево в свою очередь тоже является деревом. Узлы без наследников принято называть листьями.
Для такого дерева должны выполняться следующие условия:
Левое и правое поддерево так же являются бинарными деревьями;
У всех узлов левого поддерева произвольного узла xx значения ключей данных меньше значения ключа данных самого узла xx;
У всех узлов правого поддерева произвольного узла xx значения ключей данных больше либо равны значению ключа данных самого узла xx.
Как можно отсортировать с помощью обхода бинарного дерева?
Варианты обхода двоичных деревьев:
Два подхода:
Поиск в глубину (Depth-first search DFS)
Поиск в ширину (Breadth-first search BFS)
DFS: pre-order: Посетить узел Обойти левое поддерево Обойти правое поддерево 8 3 1 6 4 7 10 14 13 in-order: Обойти левое поддерево Посетить узел Обойти правое поддерево 1 3 4 6 7 8 10 13 14 post-order: Обойти левое поддерево Обойти правое поддерево Посетить узел 1 4 7 6 3 13 14 10 8
Собственно, видно, что нас интересует in-order.
При условии, что у всех узлов дерева значение левого потомка меньше значения родителя, а правого больше - рекурсивно обойти левое поддерево, вывести значение узла, потом обойти правое поддерево. Т.е. в порядке in-order.
TreeSet и TreeMap основаны на BST(binary search tree)
public class Task02 {
public static void main(String[] args) {
List arrList = new ArrayList<>();
arrList.add(50);
arrList.add(25);
arrList.add(75);
arrList.add(40);
arrList.add(30);
arrList.add(88);
arrList.add(40); //same value
System.out.println(arrList);
Tree theTree = new Tree<>();
for (int i = 0; i < arrList.size(); i++) {
theTree.insert(arrList.get(i), Math.random());
}
System.out.println("treeSearch+inorder for non-root");
theTree.inOrder(theTree.search(40));
System.out.println();
theTree.inOrder(theTree.getRoot());
Set integerSet = new TreeSet<>();
integerSet.addAll(arrList);
System.out.println("TreeSet: ");
for (Integer integer : integerSet) {
System.out.println(integer);
}
} }
class Tree, E extends Number> {
private Node root;
private int length;
public Node getRoot() {
return root;
}
public int getLength() {
return length;
}
public Node search(T key) {
Node curr = root;
while (key.compareTo(curr.key) != 0) { //if not, just return root
if (key.compareTo(curr.key) < 0) {
curr = curr.leftChild;
} else {
curr = curr.rightChild;
}
if (curr == null) {
System.out.println("no Node with such key is found");
return null;
}
}
System.out.println("found the node with " + key + " key");
return curr;
}
public void insert(T key, E data) {
Node aNode = new Node();
aNode.key = key;
aNode.data = data;
if (root == null) {
root = aNode;
length++;
} else {
Node curr = root;
Node lastNode;
while (true) {
lastNode = curr;
if (key.compareTo(curr.key) < 0) {
curr = curr.leftChild; //if have child from node above, just continue; if NO child from the Node above... curr will be null
if (curr == null) {
lastNode.leftChild = aNode; //and if it's null, we cannot say "null.variable"... we need to use node saved beforehand
length++;
return;
}
} else {
curr = curr.rightChild;
if (curr == null) {
lastNode.rightChild = aNode;
length++;
return;
}
}
}
}
}
public void inOrder(Node aNode) {
if (aNode != null) {
inOrder(aNode.leftChild);
printNode(aNode);
inOrder(aNode.rightChild);
}
}
private void printNode(Node aNode) {
System.out.println("aNode.key: " + aNode.key + "; aNode.data: " + aNode.data);
} }
class Node {
T key;
E data;
Node leftChild;
Node rightChild;
}
Опишите быструю сортировку?
Быстрая сортировка происходит рекурсивно. Сначала мы сортируем массив относительно значения опорного элемента, те что меньше перемещаются в левую часть, те что больше в правую. Затем рекурсивно сортируем левый подмассив и правый. Сложность O(nlogn)
На вход приходит массив, начало и конец.
- Выбрать опорный элемент (в задаче - конечный, но вообще может быть любым - начальным, рандомным и пр.).
- Пройтись по массиву, если значение элемента меньше опорника, свапнуть соседние элементы местами (или не трогать, если условие не выполняется)… таким орбазом дойти до конца массива и в конечном итоге, выйдя из цикла, свапнуть теперь уже опорник на место последнего элемента. Т.е. в итоге, справа будут элементы меньше, слева - больше опорного.
- Пройтись рекурсивно по подмассиву слева и справа - тем же методом (т.е. с выделением опорника уже у них).
class QuickSort {
public void quickSort(int[] arr, int beginning, int end) {
if (beginning < end) { //same as arr.length < 2 (if beginning = end, we have 1 element which we don't need to sort)
int pivotSpot = partition(arr, beginning, end);
quickSort(arr, beginning, pivotSpot - 1);
quickSort(arr, pivotSpot + 1, end);
}
}
public int partition(int[] arr, int beginning, int end) {
int pivot = arr[end];
int j = beginning;
for (int i = j; i < end; i++) {
if (arr[i] <= pivot) {
swap(arr, j, i);
j++;
}
}
swap(arr, j, end);
return j;
}
private void swap(int[] arr, int j, int i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
