Алгоритм

1.

Алгоритм
Алгоритм - это набор шагов или инструкций, предназначенных для решения
определенной задачи или выполнения конкретной операции.

2.

Алгоритмы бывают трёх типов:
• Последовательный — действия выполняются по
порядку друг за другом.
• Разветвляющийся — содержит одно или несколько
логических условий и имеет несколько ветвей
обработки.
• Циклический — алгоритм, в котором действия
повторяются определенное количество.

3.

«O» большое
Понятие "O большое" помогает нам понять насколько
быстро или медленно будет работать алгоритм в
зависимости от количества входных данных.
На рисунке показаны разные временные сложности.

4.

Бинарный поиск
- Это один из самых эффективных алгоритмов поиска который использует метод
решения задач “Разделяй и властвуй” (Divide and Conquer), в заранее
отсортированном массиве. У него логарифмическое время O(logn), и с
возрастанием входных данных становится только быстрее и эффективнее.

5.

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

6.

7.

Bubble sort
Один из самых простых алгоритмов сортировки
но не самых эффективных, имеет квадратичную
временную сложность O(n^2).

8.

9.

Selection sort
Еще один простой метод сортировки который также
выполняется за квадратичное время.

10.

11.

Quick sort
Одна из наиболее эффективных сортировок. У сортировки Хоара
линейно – логарифмическая сложность O(nlogn), которая также как и
бинарный поиск использует метод “Разделяй и властвуй”.

12.

Рекурсия
Данная сортировка основана на рекурсии,
то есть метод постоянно будет вызывать
самого себя пока не дойдет до
определенного результата.

13.

Для начала создадим два перегруженных метода:
• Один из них публичный и принимает
в себя неотсортированный массив и
возвращает уже метод в которой мы
передаем еще и границы массива.
• Он же в свою очередь
рекурсивно вызывает самого
себя пока high больше чем low.
• В нем так же есть метод partition
в котором и происходит вся
работа

14.

partition
• Приватный метод который делит массив на два под
массива на основе опорного элемента (pivot-а). То есть
все числа которые меньше опорного будут слева от него,
а числа которые больше справа соответственно.
• В самом конце возвращает опорный индекс.

15.

16.

Метод partition возвращает индекс опорного элемента что бы
дальнейшем понимать откуда ему начинать последующую
рекурсию.

17.

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