Сортировки. Двоичный поиск

Август 4, 2022

Главная
Информатика
Сортировки. Двоичный поиск

Содержание

2. Быстрая сортировка (Ч. Хоар, 1962)
3. Пример: 1) 4 9 7 6 2 3 8 2) 4 3 2 6 7 9
4. Сортировка слиянием (Дж. Фон Нейман, 1945)
5. Пример: 2 4 7 6 2 3 8 - [0;6] 2 4 7 6 2 3
6. Пирамидальная сортировка
7. Сортировка подсчётом Идея: использование конечной длины сортируемых чисел Время работы – O(n) Сортировка устойчива
9. Двоичный поиск Двоичный поиск — алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по
10. Задача Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется найти позицию, на которой
11. Принцип работы Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две
13. Задача
16. Некоторые полезные советы при работе с вещественными числами
17. Когда имеешь дело с вещественными числами в первую очередь нужно подумать нельзя ли от них избавиться
18. Неправильный выбор: If ((double)a/b Правильный выбор: If (a * d Исключение: Когда a * d или
19. Пример 2: Нам нужен цикл до sqrt(n) включительно. Неправильный выбор: for(int i = 0; i Правильный
20. Пример 3: Сравнить расстояния между точками a,b и c,d int d1 = sqr(a.x-b.x) + sqr(a.y-b.y); int
21. Если всё-таки приходится работать с вещественными числами, то всегда нужно стараться уменьшить погрешность вычислений Пример 1:
22. Пример 2: У нас есть прямоугольный треугольник, мы знаем длины его сторон a,b,c и один из
23. Если у нас возможно равенство вещественных чисел, то их всегда нужно сравнивать по eps abs(a -
24. При работе с бинпоиском, если нам нужно найти число с какой-то точностью, то почти всегда лучше
26. Скачать презентацию

Слайд 2

Быстрая сортировка (Ч. Хоар, 1962)

Слайд 3

Пример:
1) 4 9 7 6 2 3 8
2) 4

3 2 6 7 9 8
3) 2 3 4 6 7 9 8
4) 2 3 4 6 7 8 9

Слайд 4

Сортировка слиянием (Дж. Фон Нейман, 1945)

Слайд 5

Пример:
2 4 7 6 2 3 8 - [0;6]
2 4 7

6 2 3 8 - [0;3]
2 4 7 6 2 3 8 - [0;1]
2 4 7 6 2 3 8 - [2;3]
2 4 6 7 2 3 8 - [4;6]
2 4 6 7 2 3 8 - [4;5]
Итог: 2 2 3 4 6 7 8

Слайд 6

Пирамидальная сортировка

Слайд 7

Сортировка подсчётом
Идея: использование конечной длины сортируемых чисел
Время работы – O(n)
Сортировка устойчива

Слайд 8

Слайд 9

Двоичный поиск
Двоичный поиск — алгоритм поиска объекта по заданному признаку в

множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время.

Слайд 10

Задача
Пусть нам дан упорядоченный массив, состоящий только из целочисленных элементов. Требуется

найти позицию, на которой находится заданный элемент или сказать, что такого элемента нет.

Слайд 11

Принцип работы
Двоичный поиск заключается в том, что на каждом шаге множество

объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект.

Слайд 12

Слайд 13

Задача

Слайд 14

Слайд 15

Слайд 16

Некоторые полезные советы при работе с вещественными числами

Слайд 17

Когда имеешь дело с вещественными числами в первую очередь нужно подумать

нельзя ли от них избавиться и перейти к целым.
Пример 1:
Нам нужно сравнить два числа вида a/b, где а и b целые числа

Слайд 18

Неправильный выбор:
If ((double)a/b < (double)с/d)
Правильный выбор:
If (a * d < c

* b)
Исключение:
Когда a * d или c * b не помещаются в целочисленный тип

Слайд 19

Пример 2:
Нам нужен цикл до sqrt(n) включительно.
Неправильный выбор:
for(int i =

0; i <= sqrt(n); i++)
Правильный выбор:
for(int i = 0; i * i <= n; i++)

Слайд 20

Пример 3:
Сравнить расстояния между точками a,b и c,d
int d1 = sqr(a.x-b.x)

+ sqr(a.y-b.y);
int d2 = sqr(c.x-d.x) + sqr(c.y-d.y);
Вместо:
if (sqrt(d1) < sqrt(d2))
Лучше:
if (d1 < d2)

Слайд 21

Если всё-таки приходится работать с вещественными числами, то всегда нужно стараться

уменьшить погрешность вычислений
Пример 1:
b/a + c/a + … = (b + c + …)/a;

Слайд 22

Пример 2:
У нас есть прямоугольный треугольник, мы знаем длины его сторон

a,b,c и один из углов A. Нужно найти sin(B)
Не лучший выбор:
sinb = sin(pi - A);
Можно так:
sinb = b/c;

Слайд 23

Если у нас возможно равенство вещественных чисел, то их всегда нужно

сравнивать по eps
abs(a - b) < eps <=> a == b
Eps должен быть меньше требуемой точности, но больше лучшей точности.
Обычно выбирают eps = 1e-9;
А вообще вопрос точности при работе с вещественными типами это философский вопрос ☺

Слайд 24

При работе с бинпоиском, если нам нужно найти число с какой-то

точностью, то почти всегда лучше это делать итерационно
Пример:
Нам нужно найти корень функции с заданной точностью
Не правильный выбор:
while((r – l) < eps)
Правильный выбор:
for (int i = 0; i < 100; i++)