Алгоритм. Сортировка

1.

МОДУЛЬ 3 ЗАНЯТИЕ 2

2.

АЛГОРИТМ
Алгоритм - это последовательность команд, предназначенная
исполнителю, в результате выполнения которой он должен решить
поставленную задачу.

3.

АЛГОРИТМ ЛИНЕЙНОГО (ПОСЛЕДОВАТЕЛЬНОГО) ПОИСКА
Линейный алгоритм — это алгоритм, образуемый командами, которые
выполняются однократно и именно в той последовательности, в которой
записаны.
Алгоритм линейного поиска перебирает все элементы в массиве, сравнивая их
с заданным ключом (из-за полного перебора скорость поиска намного меньше,
чем в других алгоритмах)

4.

Дан массив k из 8 элементов. Найти индекс элементов,
значение которого равно 3

5.

6.

АЛГОРИТМ БИНАРНОГО ПОИСКА

7.

8.

9.

МОДУЛЬ 3 ЗАНЯТИЕ 3

10.

СОРТИРОВКИ
Сортировка данных — это когда мы их упорядочиваем по какому-то признаку.
Например, в школе есть классный журнал, в котором все ученики
отсортированы по фамилии. Или товары в интернет-магазине могут
выводиться сначала дешёвые, потом дорогие. Или бывает сортировка товаров
по популярности: используют внутреннюю переменную «популярность товара»
и смотрят на её значение.

11.

СОРТИРОВКА ВЫБОРОМ
Смысл Сортировки выбором (Selection Sort) состоит в поиске минимального значения элемента в
массиве, и перемещения этого значения в начало массива.
“Начало” в алгоритме Сортировка выбором с каждым шагом цикла смещается в сторону хвоста массива.
Поэтому на первой итерации цикла, найденное минимальное значение меняется местами со значением в
нулевой ячейке массива. На второй итерации “начало” уже будет указывать на следующую (первую)
ячейку и так далее.
Получается простой обмен местами значений ячеек массива. При таком обмене значениями не
нужен сдвиг (перезапись) всех элементов массива, чтобы записать минимальное значение в
соответствующую ячейку. То есть алгоритм Сортировка выбором не требует использования
дополнительной памяти. Перезапись значений происходит сразу после нахождения минимального
значения в массиве.

12.

СОРТИРОВКА ПУЗЫРЬКОМ
Здесь нужно последовательно сравнивать значения соседних элементов и менять числа
местами, если предыдущее оказывается больше последующего.
Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими
остаются в начале.
Принцип работы пузырьковой сортировки можно описать в три пункта:
1.Прохождение по всему массиву;
2.Сравнивание между собой пар соседних ячеек;
3.Если при сравнении оказывается, что значение ячейки i больше, чем значение ячейки i + 1, то мы
меняем значения этих ячеек местами;

13.

Необходимо отсортировать список участников олимпиады по
количеству набранных ими баллов(по убыванию).

14.

МОДУЛЬ 3 ЗАНЯТИЕ 4

15.

СОРТИРОВКА ВСТАВКАМИ
Идём по массиву и как только встречаем нарушение порядка, начинаем перемещать элемент,
который нарушил порядок до тех пор, пока он не встанет на место, где не нарушает порядок.
Таким образом обходим все элементы.
Сортировка вставками отличается от сортировки пузырьком тем, что мы «сопровождаем»
элемент массива и вставляем его на нужное место. В сортировке пузырьком, после обмена
местами двух элементов, даже если этот обмен привёл к опять к нарушению порядка, мы всё
равно двигаемся дальше.

16.

РЕКУРСИЯ