1. Сортировка выбором Пояснения:

1. #include : Подключает библиотеку для ввода/вывода (cout, cin).
2. #include : Подключает библиотеку для работы с динамическими массивами (vector).
3. using namespace std;: Упрощает код, позволяя использовать элементы из пространства имен std без префикса std::.
4. void selectionSort(vector& arr): Функция, выполняющая сортировку выбором. Принимает вектор arr по ссылке, чтобы изменения внутри функции отражались на исходном массиве.
5. int n = arr.size();: Получает размер массива.
6. for (int i = 0; i < n - 1; i++): Внешний цикл. Проходит по всем элементам массива, кроме последнего (потому что последний элемент автоматически будет на своем месте после сортировки предыдущих).
7. int min_index = i;: Предполагаем, что текущий элемент (arr[i]) - минимальный. Запоминаем его индекс.
8. for (int j = i + 1; j < n; j++): Внутренний цикл. Начинается с элемента, следующего за текущим (i + 1), и ищет минимальный элемент в оставшейся части массива.
9. if (arr[j] < arr[min_index]): Если нашли элемент (arr[j]) меньше, чем текущий минимальный (arr[min_index]).
10. min_index = j;: Запоминаем индекс нового минимального элемента.
11. if (min_index != i): Если индекс минимального элемента изменился (то есть мы нашли меньший элемент, чем arr[i]).
12. swap(arr[i], arr[min_index]);: Меняем местами текущий элемент (arr[i]) и минимальный элемент (arr[min_index]). Используется функция swap из библиотеки .
13. int main(): Основная функция программы.
14. vector arr = {64, 25, 12, 22, 11};: Создает и инициализирует вектор с данными.
15. Вывод массива до и после сортировки: Выводит элементы массива на экран до и после вызова функции selectionSort. Как работает скрипт:

Сортировка выбором работает следующим образом:

1. Находим минимальный элемент в неотсортированной части массива/списка.
2. Меняем местами этот минимальный элемент с первым элементом неотсортированной части.
3. Повторяем шаги 1 и 2 для оставшейся неотсортированной части массива/списка.

Временная сложность:

Временная сложность алгоритма сортировки выбором всегда O(n^2), где n - количество элементов в массиве/списке. Это связано с тем, что всегда есть два вложенных цикла: один для поиска минимального элемента, а другой для перебора элементов. Не имеет значения, отсортирован ли массив/список изначально, или нет. Сортировка выбором всегда выполняет примерно одно и то же количество операций.

• Лучший случай: O(n^2) • Средний случай: O(n^2) • Худший случай: O(n^2)

Пространственная сложность: O(1) - сортировка выполняется на месте (in-place), то есть не требует дополнительной памяти (кроме небольшого количества для хранения переменных).

2. Сортировка вставками Пояснения:

1. #include : Подключает библиотеку для ввода/вывода.
2. #include : Подключает библиотеку для работы с динамическими массивами.
3. using namespace std;: Используем пространство имен std для удобства.
4. void insertionSort(vector& arr): Функция сортировки вставками. Принимает вектор arr по ссылке.
5. int n = arr.size();: Получаем размер массива.
6. for (int i = 1; i < n; i++): Внешний цикл. Начинается со второго элемента (индекс 1), так как считается, что первый элемент уже является "отсортированной" частью массива (размером 1).
7. int key = arr[i];: key - это текущий элемент, который мы будем вставлять в правильное место в отсортированной части массива.
8. int j = i - 1;: j - индекс последнего элемента в отсортированной части массива.
9. while (j >= 0 && arr[j] > key): Внутренний цикл. Сдвигаем элементы отсортированной части массива вправо (на одну позицию), пока не найдем место для key (то есть пока не встретим элемент, который меньше или равен key, или не достигнем начала массива).
10. arr[j + 1] = arr[j];: Сдвигаем элемент arr[j] вправо (на позицию j + 1).
11. j = j - 1;: Переходим к предыдущему элементу в отсортированной части массива.
12. arr[j + 1] = key;: После завершения внутреннего цикла вставляем key на правильное место (после сдвига элементов). j + 1 - это индекс, куда нужно вставить key.
13. int main(): Главная функция программы. Создает массив, выводит его, сортирует и снова выводит. Как работает скрипт:

Сортировка вставками работает подобно тому, как вы сортируете карты в руке.

1. Проходим по элементам массива/списка, начиная со второго.
2. Для каждого элемента (key) находим его правильное место в уже отсортированной части массива/списка (слева от текущего элемента).
3. Сдвигаем элементы отсортированной части вправо, чтобы освободить место для key.
4. Вставляем key на освободившееся место.

Временная сложность:

• Лучший случай: O(n) - Когда массив/список уже отсортирован. В этом случае внутренний цикл почти не выполняется. • Средний случай: O(n^2) • Худший случай: O(n^2) - Когда массив/список отсортирован в обратном порядке. В этом случае внутренний цикл выполняется для каждого элемента.

Сортировка вставками эффективна для небольших массивов/списков и для массивов/списков, которые почти отсортированы.

Пространственная сложность: O(1) - Сортировка выполняется на месте (in-place). 3) Сортировка слиянием Как работает скрипт:

1. merge_sort(arr): • Проверяет базовый случай: если длина массива меньше или равна 1, он уже отсортирован, и функция возвращает его. • Находит середину массива и разделяет его на две половины: left и right. • Рекурсивно вызывает merge_sort для каждой половины, чтобы отсортировать их. • Вызывает функцию merge(left, right) для слияния двух отсортированных половин в один отсортированный массив.

2. merge(left, right): • Создает пустой список result для хранения отсортированного результата. • Использует два указателя (i и j) для итерации по left и right соответственно. • Сравнивает элементы left[i] и right[j] и добавляет наименьший из них в result. Увеличивает соответствующий указатель (i или j). • После того, как один из списков (left или right) закончился, добавляет все оставшиеся элементы из другого списка в result. • Возвращает отсортированный список result.

3. main.py: • Импортирует функцию merge_sort из файла merge_sort.py. • Создает пример массива arr. • Вызывает merge_sort для сортировки массива. • Выводит исходный и отсортированный массивы.

Временная сложность:

Сортировка слиянием имеет временную сложность O(n log n) в лучшем, среднем и худшем случаях. Это делает её одним из наиболее эффективных алгоритмов сортировки для больших наборов данных.

• O(log n) представляет собой количество уровней рекурсии (разбиений) в алгоритме. • O(n) представляет собой время, необходимое для слияния двух отсортированных половин на каждом уровне рекурсии.

Пространственная сложность:

Сортировка слиянием требует дополнительной памяти для хранения временных массивов, создаваемых при слиянии. Таким образом, пространственная сложность составляет O(n). Это считается недостатком сортировки слиянием по сравнению с некоторыми алгоритмами сортировки на месте (например, быстрая сортировка), которые требуют меньше дополнительной памяти (хотя быстрая сортировка в худшем случае также может потребовать O(n) дополнительной памяти из-за рекурсии). 4) Сортировка Шелла Пояснения:

1. #include : Подключает библиотеку для ввода/вывода.
2. #include : Подключает библиотеку для работы с динамическими массивами.
3. using namespace std;: Используем пространство имен std.
4. void shellSort(vector& arr): Функция сортировки Шелла. Принимает массив arr по ссылке.
5. int n = arr.size();: Получаем размер массива.
6. for (int gap = n / 2; gap > 0; gap /= 2): Внешний цикл. Определяет шаг (gap) между элементами, которые сравниваются. Начинаем с шага, равного половине размера массива, и уменьшаем его вдвое на каждой итерации. Это позволяет сортировать элементы, находящиеся далеко друг от друга, на ранних этапах, что делает массив более "почти отсортированным" для последующих итераций с меньшим шагом.
7. for (int i = gap; i < n; i++): Средний цикл. Проходит по элементам массива, начиная с индекса, равного шагу gap.
8. int temp = arr[i];: temp - текущий элемент, который мы будем вставлять в правильное место.
9. int j = i;: j - индекс текущего элемента.
10. while (j >= gap && arr[j - gap] > temp): Внутренний цикл. Сдвигаем элементы на шаг gap вправо, пока не найдем место для temp. Условие j >= gap проверяет, что мы не вышли за пределы массива. Условие arr[j - gap] > temp проверяет, что элемент на расстоянии gap больше temp.
11. arr[j] = arr[j - gap];: Сдвигаем элемент на расстояние gap вправо.
12. j -= gap;: Переходим к предыдущему элементу на расстояние gap.
13. arr[j] = temp;: Вставляем temp на правильное место.
14. int main(): Главная функция. Как работает скрипт:

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

1. Определяем начальный шаг (gap) - расстояние между сравниваемыми элементами.
2. Выполняем сортировку вставками для подмассивов, образованных элементами с шагом gap.
3. Уменьшаем шаг.
4. Повторяем шаги 2 и 3, пока шаг не станет равен 1. Когда шаг равен 1, выполняется обычная сортировка вставками, но массив уже почти отсортирован, поэтому сортировка проходит быстрее.

Временная сложность:

Временная сложность сортировки Шелла зависит от выбранной последовательности шагов (gap sequence). Не существует единой оптимальной последовательности. В худшем случае сложность может быть O(n^2), но при правильном выборе последовательности шагов можно достичь сложности близкой к O(n log n).

• Лучший случай: Зависит от последовательности шагов, может быть O(n log n) для некоторых последовательностей. • Средний случай: Зависит от последовательности шагов. Обычно лучше, чем O(n^2). • Худший случай: O(n^2)

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

Пространственная сложность: O(1) - Сортировка выполняется на месте (in-place). 5)Пирамидальная сортировка Пояснения:

1. #include : Подключает библиотеку для ввода/вывода.
2. #include : Подключает библиотеку для работы с динамическими массивами.
3. using namespace std;: Используем пространство имен std.
4. void heapify(vector& arr, int n, int i): Функция heapify отвечает за поддержание свойства кучи. Принимает массив arr, его размер n, и индекс i корня поддерева.
5. int largest = i;: Предполагаем, что корень (i) - наибольший элемент.
6. int left = 2 * i + 1;: Вычисляем индекс левого потомка.
7. int right = 2 * i + 2;: Вычисляем индекс правого потомка.
8. if (left < n && arr[left] > arr[largest]): Если левый потомок существует (left < n) и он больше наибольшего элемента (arr[left] > arr[largest]), обновляем largest на индекс левого потомка.
9. if (right < n && arr[right] > arr[largest]): Аналогично для правого потомка.
10. if (largest != i): Если наибольший элемент не является корнем, то нарушено свойство кучи.
11. swap(arr[i], arr[largest]);: Меняем местами корень и наибольший элемент.
12. heapify(arr, n, largest);: Рекурсивно вызываем heapify для поддерева, корень которого был перемещен вниз.
13. void heapSort(vector& arr): Функция пирамидальной сортировки.
14. for (int i = n / 2 - 1; i >= 0; i--): Строим max-кучу из массива. Начинаем с последнего нелистового узла (n/2 - 1) и вызываем heapify для каждого узла, двигаясь к корню.
15. for (int i = n - 1; i > 0; i--): Извлекаем элементы из кучи в отсортированном порядке.
16. swap(arr[0], arr[i]);: Меняем местами корень (максимальный элемент) с последним элементом неотсортированной части массива.
17. heapify(arr, i, 0);: Вызываем heapify на уменьшенной куче (размером i), чтобы восстановить свойство кучи после извлечения максимального элемента. Как работает скрипт:

Пирамидальная сортировка - это алгоритм сортировки, основанный на структуре данных "куча".

1. Построение кучи: Преобразуем входной массив в max-кучу. Max-куча - это двоичное дерево, в котором значение каждого узла больше или равно значению его потомков.
2. Извлечение элементов: • Меняем местами корень кучи (максимальный элемент) с последним элементом массива. • Уменьшаем размер кучи на 1. • Восстанавливаем свойство кучи для оставшейся части массива. • Повторяем шаги, пока в куче не останется один элемент.

Временная сложность:

• Лучший случай: O(n log n) • Средний случай: O(n log n) • Худший случай: O(n log n)

Пирамидальная сортировка имеет гарантированную сложность O(n log n) во всех случаях, что делает ее довольно эффективной.

Пространственная сложность: O(1) - Сортировка выполняется на месте (in-place). 6) Бинарный поиск Пояснения:

1. #include : Подключает библиотеку для ввода/вывода.
2. #include : Подключает библиотеку для работы с динамическими массивами.
3. using namespace std;: Используем пространство имен std.
4. int binarySearch(const vector& arr, int target): Функция бинарного поиска.
   • const vector& arr: Принимает отсортированный массив (вектор) arr по константной ссылке (чтобы избежать копирования массива и не изменять его).
   • int target: Целевое значение, которое нужно найти в массиве.
5. int left = 0;: Инициализируем левую границу поиска индексом первого элемента.
6. int right = arr.size() - 1;: Инициализируем правую границу поиска индексом последнего элемента.
7. while (left <= right): Основной цикл. Продолжаем поиск, пока левая граница не станет больше правой. Если left > right, это означает, что целевое значение не найдено в массиве.
8. int mid = left + (right - left) / 2;: Вычисляем индекс середины между левой и правой границами. Использование left + (right - left) / 2 вместо (left + right) / 2 помогает избежать переполнения, если left и right - очень большие числа.
9. if (arr[mid] == target): Если элемент в середине равен целевому значению, то мы нашли целевое значение.
10. return mid;: Возвращаем индекс найденного элемента.
11. if (arr[mid] > target): Если элемент в середине больше целевого значения, то целевое значение может находиться только в левой половине массива.
12. right = mid - 1;: Сдвигаем правую границу влево на mid - 1.
13. else: Если элемент в середине меньше целевого значения, то целевое значение может находиться только в правой половине массива.
14. left = mid + 1;: Сдвигаем левую границу вправо на mid + 1.
15. return -1;: Если цикл завершился, а целевое значение не было найдено, то возвращаем -1.
16. int main(): Главная функция. Создает массив, задает целевое значение, вызывает функцию binarySearch и выводит результат.

Как работает скрипт:

Бинарный поиск - это эффективный алгоритм поиска элемента в отсортированном массиве. Он работает, разделяя массив пополам на каждой итерации, пока целевой элемент не будет найден или пока массив не станет пустым.

1. Находим середину массива.
2. Сравниваем целевой элемент со средним элементом.
3. Если целевой элемент равен среднему элементу, возвращаем индекс среднего элемента.
4. Если целевой элемент меньше среднего элемента, продолжаем поиск в левой половине массива.
5. Если целевой элемент больше среднего элемента, продолжаем поиск в правой половине массива.
6. Если левая граница поиска превысила правую границу, значит, элемент не найден.

Временная сложность:

• Лучший случай: O(1) - Целевой элемент находится в середине массива. • Средний случай: O(log n) • Худший случай: O(log n) - Целевой элемент находится в конце массива или отсутствует в массиве.

Бинарный поиск имеет логарифмическую временную сложность, что делает его очень эффективным для поиска в больших отсортированных массивах.

Важное условие: Бинарный поиск работает только на отсортированных массивах. 7) Поиск Фибоначчи Пояснения:

1. #include : Подключает библиотеку для ввода/вывода.
2. #include : Подключает библиотеку для работы с динамическими массивами.
3. using namespace std;: Используем пространство имен std.
4. int fibonacciSearch(const vector& arr, int target): Функция поиска Фибоначчи.
   • const vector& arr: Принимает отсортированный массив arr по константной ссылке.
   • int target: Целевое значение для поиска.
5. int n = arr.size();: Получаем размер массива.
6. int fibMMm2 = 0;, int fibMMm1 = 1;, int fibM = fibMMm2 + fibMMm1;: Инициализируем три последовательных числа Фибоначчи: fibMMm2 (F(m-2)), fibMMm1 (F(m-1)) и fibM (F(m)). Мы будем использовать эти числа для разделения массива на части.
7. while (fibM < n): Находим наименьшее число Фибоначчи fibM, которое больше или равно размеру массива n. Это необходимо для правильного разбиения массива.
8. int offset = -1;: offset - это переменная, которая отслеживает, какая часть массива уже была исключена из поиска.
9. while (fibM > 1): Основной цикл поиска. Продолжаем цикл, пока fibM больше 1, потому что когда fibM равен 1, у нас остается только один элемент для проверки.
10. int i = min(offset + fibMMm2, n - 1);: Вычисляем индекс i. Мы используем fibMMm2 для определения позиции элемента, с которым сравниваем target. Функция min гарантирует, что i не выйдет за пределы массива.
11. if (arr[i] < target): Если элемент в индексе i меньше target, то целевой элемент может находиться только в правой части массива.
    • Обновляем числа Фибоначчи: fibM = fibMMm1; fibMMm1 = fibMMm2; fibMMm2 = fibM - fibMMm1; Мы сдвигаем числа Фибоначчи, чтобы сузить область поиска.
    • Обновляем offset на i, потому что все элементы до i исключены из поиска.
12. else if (arr[i] > target): Если элемент в индексе i больше target, то целевой элемент может находиться только в левой части массива.
    • Обновляем числа Фибоначчи: fibM = fibMMm2; fibMMm1 = fibMMm1 - fibMMm2; fibMMm2 = fibM - fibMMm1; Мы сдвигаем числа Фибоначчи, чтобы сузить область поиска.
13. else: Если arr[i] == target, то мы нашли целевой элемент и возвращаем его индекс.
14. if (fibMMm1 && arr[offset + 1] == target): После завершения основного цикла, если fibMMm1 не равен 0 (то есть, если мы что-то искали) и если элемент по индексу offset + 1 равен target, то возвращаем offset + 1. Это необходимо, потому что при определенных обстоятельствах последний элемент может быть не проверен в основном цикле.
15. return -1;: Если целевой элемент не был найден, то возвращаем -1.

Как работает скрипт:

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

1. Находим наименьшее число Фибоначчи (fibM), которое больше или равно размеру массива.
2. Исключаем части массива, сравнивая целевое значение с элементом, индекс которого вычисляется на основе чисел Фибоначчи.
3. Повторяем, пока не найдем целевой элемент или не останется один элемент.

Временная сложность:

• Лучший случай: O(1) • Средний случай: O(log n) • Худший случай: O(log n)

Поиск Фибоначчи имеет логарифмическую временную сложность, как и бинарный поиск. Однако, в некоторых случаях, он может быть немного медленнее, чем бинарный поиск, из-за более сложной логики вычисления индексов. Но у него есть преимущество, заключающееся в том, что для его реализации требуются только операции сложения и вычитания (а не деления, как в бинарном поиске), что может быть полезно на некоторых типах архитектур.

Важное условие: Поиск Фибоначчи работает только на отсортированных массивах.