Поиск и сортировка

Question 1

Перечислите алгоритмические и емкостные сложности сортировки: пузырек, слияния, быстрая

Answer 1

Пузырек - O(nn) и O(1)
Слиянием - O(nlog(n)) и O(n)
Быстрая - O(n*n) и O(n)

Question 2

Опишите идею сортировки:

• пузырек
• слияния
• быстрая

Answer 2

Пузырек: каждое значение в массиве всплывает до нужной позиции

Слияния:массив разбивается на две части, каждая сортируется этим же алгоритмом, затем отсортированные части объединяются

Быстрая: выбрать некоторый элемент и разделить массив на часть, которая строго меньше и все остальные, затем отсортировать полученные части