Python: Списки
2026-02-26 17:31 Diff
https://ru.hexlet.io/courses/python-lists/lessons/sorting/theory_unit

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

Тогда для чего задают подобные вопросы? Обычно собеседующий хочет узнать следующее:

  1. Насколько кандидат вообще в курсе о существовании алгоритмов
  2. Способен ли он программировать (составлять программу сам, думая своей головой)
  3. Как работает его алгоритмическое мышление

Знание алгоритмов действительно влияет на то, как мы думаем и насколько быстро соображаем. И хотя невозможно знать все алгоритмы, нужно хотя бы иметь представление о самых ключевых и в идеале уметь их реализовывать. В нашем списке рекомендуемых книг есть как минимум одна книга, полностью посвященная алгоритмам.

Кроме того, Роберт Мартин в своей книге "Идеальный программист" рассказывает о подходе Ката — понятии, взятом из боевых искусств:

Принцип изучения боевого искусства на основе ката состоит в том, что повторяя ката многие тысячи раз, практик боевого искусства приучает свое тело к определенного рода движениям, выводя их на бессознательный уровень. Таким образом, попадая в боевую ситуацию, тело работает "само" на основе рефлексов, вложенных многократным повторением ката. Также считается, что ката обладают медитативным воздействием.

Роберт Мартин рекомендует время от времени решать классические алгори��мические задачки для поддержания формы. Эта тема стала настолько популярной, что если загуглить python github kata, то вы увидите множество репозиториев с подобными задачками.

Сортировка

Способов сортировать список достаточно много. Самый популярный для обучения — пузырьковая сортировка (bubble sort).

Алгоритм состоит из повторяющихся проходов по сортируемому списку. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по списку повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — список отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент списка ставится на свое место в конце списка рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу списка («всплывает» до нужной позиции, как пузырек в воде. Отсюда и название алгоритма).

Весь код этой функции делится на два уровня:

  1. Внутренний цикл for, который проходит по списку от начала до конца, меняя элементы попарно, если нужно сортировать.
  2. Внешний цикл while, который определяет, когда нужно остановиться. Обратите внимание, что в худшем случае этот цикл выполнится len(coll) раз, что совпадает с теоретическим худшим случаем этого алгоритма, при котором самый большой или маленький элемент находятся в противоположных концах списка от сортированного варианта.

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