КВАДРАТИЧНЫЕ СОРТИРОВКИ PYTHON

Квадратичные сортировки Python — это алгоритмы сортировки, которые имеют квадратичную сложность времени O(n^2). Это означает, что время выполнения алгоритма будет увеличиваться в квадрате с увеличением количества элементов в массиве.

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

def insertion_sort(arr):    for i in range(1, len(arr)):        key = arr[i]        j = i - 1        while j >= 0 and key < arr[j] :                arr[j + 1] = arr[j]                j -= 1        arr[j + 1] = key

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

Хотя квадратичные сортировки Python просты в реализации, они могут быть неэффективными для сортировки больших массивов. Для более эффективной сортировки рекомендуется использовать алгоритмы со сложностью времени O(n log n), такие как быстрая сортировка и сортировка слиянием.