Квадратичные сортировки

Мы подытожили предыдущее занятие важным выводом: в упорядоченных последовательностях искать информацию гораздо быстрее.

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

Сортировка — это операция над последовательностью элементов, которая переставляет их так, что они становятся упорядоченными по заранее определённому правилу.

Для наших целей достаточно использовать целочисленные массивы и простые правила:

• по возрастанию,
• по убыванию,
• по неубыванию и т. д.

Во всех примерах мы рассмотрим сортировку по возрастанию.

Проверка на упорядоченность

Для разминки давайте напишем алгоритм, который проверяет, упорядочен ли массив.

Ведь если последовательность уже отсортирована, сортировать её заново смысла нет.

Идея простая:

• идём по массиву слева направо,
• сравниваем каждый элемент с соседним,
• если где-то правило нарушается → массив не отсортирован.

Пример с обычным списком Python

def is_sorted(arr):
    # Проходим по массиву до предпоследнего элемента
    for i in range(len(arr) - 1):
        # Если текущий элемент больше следующего → порядок нарушен
        if arr[i] > arr[i + 1]:
            return False
    return True

# Проверка
A = [1, 2, 3, 5, 7]
print(is_sorted(A))  # True — массив упорядочен

B = [3, 1, 4, 2]
print(is_sorted(B))  # False — массив не упорядочен

Пример с NumPy

import numpy as np

def is_sorted_np(arr):
    # Сравниваем массив с его "сдвинутой" версией
    return np.all(arr[:-1] <= arr[1:])

# Проверка
A = np.array([1, 2, 3, 5, 7])
print(is_sorted_np(A))  # True

B = np.array([3, 1, 4, 2])
print(is_sorted_np(B))  # False

Оба алгоритма работают за O(n) — то есть время работы прямо пропорционально длине массива.

⚠️ Обрати внимание: в цикле мы идём только до предпоследнего элемента, ведь на каждом шаге сравниваем i-й и i+1-й элементы. Если бы мы пошли до конца массива, то Python выбросил бы ошибку «выход за границы».