Алгоритмы сортировки в Python с примерами кода

Как реализовать сортировку пузырьком для учебных целей?

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

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Флаг, чтобы отследить, были ли обмены на текущем проходе
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr[:]))  # [11, 12, 22, 25, 34, 64, 90]
  

сортировка выбором python (сортировка выбором в python)

[11, 12, 22, 25, 34, 64, 90]

сортировка данных python (сортировка данных в python)

Как отсортировать список в обратном порядке с помощью встроенных средств?

Достаточно указать параметр reverse=True в sorted() или sort().

sorted(nums, reverse=True)   # [9, 5, 4, 3, 1, 1]
nums.sort(reverse=True)
  

Как отсортировать список словарей по значению определённого поля?

Применяется key с lambda-функцией, извлекающей нужное поле.

students = [
    {'name': 'Alice', 'grade': 88},
    {'name': 'Bob', 'grade': 95},
    {'name': 'Charlie', 'grade': 72}
]
sorted_by_grade = sorted(students, key=lambda s: s['grade'])
print(sorted_by_grade)
  

[{'name': 'Charlie', 'grade': 72}, {'name': 'Alice', 'grade': 88}, {'name': 'Bob', 'grade': 95}]
  

sorted_by_grade = sorted(students, key=lambda s: s.get('grade', 0))
    

Как реализовать быструю сортировку (Quick sort) на Python?

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

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))
  

[1, 1, 2, 3, 6, 8, 10]

Как выполнить сортировку слиянием (Merge sort) на Python?

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

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))
  

[3, 9, 10, 27, 38, 43, 82]

Как отсортировать список, используя пользовательский класс с методом __lt__?

Если нужно сортировать объекты пользовательского типа, можно определить в классе метод __lt__(self, other), который возвращает True, если self должен быть меньше other. Тогда sorted() будет использовать его.

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age
    def __lt__(self, other):
        return self.age < other.age
    def __repr__(self):
        return f'{self.name}({self.age})'

people = [Person('Alice', 30), Person('Bob', 25), Person('Charlie', 35)]
print(sorted(people))
  

[Bob(25), Alice(30), Charlie(35)]

Как отсортировать список по нескольким критериям?

Можно вернуть кортеж из нескольких ключей в lambda. Сортировка будет выполняться сначала по первому элементу кортежа, затем при равенстве по второму и т.д.

data = [('Alice', 25, 85), ('Bob', 22, 90), ('Alice', 22, 92)]
sorted_data = sorted(data, key=lambda x: (x[0], -x[1], x[2]))
print(sorted_data)
  

[('Alice', 25, 85), ('Alice', 22, 92), ('Bob', 22, 90)]

В примере сначала по имени (по возрастанию), затем по возрасту (убывание за счёт минуса).

Какие проблемы возникают при сортировке строк с учётом регистра?

По умолчанию строки сортируются по лексикографическому порядку на основе кодов Unicode. Заглавные буквы имеют меньшие коды, чем строчные, поэтому 'Apple' окажется раньше 'apple'. Чтобы игнорировать регистр, используется key=str.lower.

words = ['banana', 'Apple', 'cherry', 'Banana']
sorted(words)              # ['Apple', 'Banana', 'banana', 'cherry']
sorted(words, key=str.lower)  # ['Apple', 'banana', 'Banana', 'cherry']