Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Сортировка списков Python: Списки

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

numbers = [8, 3, 10]
# sort изменяет список
numbers.sort()
print(numbers)  # => [3, 8, 10]

# В обратную сторону можно указав параметр reverse
numbers.sort(reverse=True)
print(numbers)  # => [10, 8, 3]

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

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

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

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

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

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

Сортировка

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

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

def bubble_sort(coll):
    # Функция изменяет входящий список coll
    steps_count = len(coll) - 1
    # Объявляем переменную swapped, значение которой показывает,
    # был ли совершен обмен элементов во время перебора списка
    swapped = True
    # Цикл while
    while swapped:
        swapped = False
        # Перебираем список и меняем местами элементы, если предыдущий
        # больше, чем следующий
        for i in range(steps_count):
            if coll[i] > coll[i + 1]:
                # Используем множественное присваивание для обмена элементов
                coll[i], coll[i + 1] = coll[i + 1], coll[i]
                # Если была совершена перестановка,
                # присваиваем swapped значение True
                swapped = True
        # Уменьшаем счетчик на 1, т.к. самый большой элемент уже находится
        # в конце списка
        steps_count -= 1

    return coll

print(bubble_sort([3, 2, 10, -2, 0]))  # => [-2, 0, 2, 3, 10]

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

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

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


Дополнительные материалы

  1. Сортировка средствами Python
  2. Визуализация алгоритмов сортировок

Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы
профессия
Обучитесь разработке бэкенда сайтов и веб-приложений — серверной части, которая отвечает за логику и базы данных
10 месяцев
с нуля
Старт 28 ноября
профессия
новый
Собирайте, анализируйте и интерпретируйте данные, улучшайте бизнес-процессы и продукт компании. Обучитесь работе с библиотеками Python
9 месяцев
с нуля
Старт 28 ноября

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

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