Python для начинающих

### Алгоритмы сортировки: от простого к сложному

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

#### Пузырьковая сортировка: проще некуда

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

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

data = [64, 34, 25, 12, 22]
bubble_sort(data)
print(data)  # [12, 22, 25, 34, 64]

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

---

#### Сортировка выбором: минималистичный подход

Следующий метод — это сортировка выбором. Идея проста: мы находим минимальный элемент и меняем его местами с элементом на первой позиции, затем повторяем процесс для оставшегося массива.

def selection_sort(array):
    for i in range(len(array)):
        min_idx = i
        for j in range(i + 1, len(array)):
            if array[j] < array[min_idx]:
                min_idx = j
        array[i], array[min_idx] = array[min_idx], array[i]

data = [64, 34, 25, 12, 22]
selection_sort(data)
print(data)  # [12, 22, 25, 34, 64]

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

---

#### Быстрая сортировка: работа с рекурсией

Теперь отправляемся в мир более эффективных алгоритмов — быстрая сортировка (QuickSort). Это превосходный пример "разделяй и властвуй". Она делит список на две части: элементы меньше опорного попадают в левую часть, больше — в правую. Затем процесс повторяется для каждой из частей.

def quick_sort(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]  # выбираем средний элемент как опорный
    left = [x for x in array if x < pivot]
    middle = [x for x in array if x == pivot]
    right = [x for x in array if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

data = [64, 34, 25, 12, 22]
result = quick_sort(data)
print(result)  # [12, 22, 25, 34, 64]

Быстрая сортировка имеет среднюю временную сложность O(n log n), что делает ее невероятно популярным вариантом.

---

#### Сортировка встроенными методами Python

Все алгоритмы хороши, но в конечном счете, вам зачастую не нужно изобретать велосипед. Python имеет встроенную функцию sorted() и метод списка .sort(), которые работают на основе гибридного алгоритма Timsort. Он сочетает в себе подходы из сортировки вставками и слиянием.

data = [64, 34, 25, 12, 22]
result = sorted(data)
print(result)  # [12, 22, 25, 34, 64]

Встроенная сортировка в Python работает быстро и оптимизирована для большинства сценариев. Ее временная сложность — O(n log n).

---

#### Какой алгоритм выбрать?

1. Если у вас небольшой массив, вы хотите получить базовое понимание — начинайте с пузырьковой сортировки.
2. Нужно что-то чуть сложнее? Сортировка выбором покажет, как добиться результата за меньшее количество операций.
3. Хотите понять, как работают эффективные алгоритмы? Разберитесь с быстрой сортировкой.
4. Работаете с реальными задачами? Без сомнений, используйте встроенную sorted().

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

👍3🔥1

271 views00:12