Сортировка списков в python: list.sort() против sorted(list)

Функции из модуля operator

Шаблон с ключевой функций, показанный выше, используется очень часто, поэтому Python предоставляет функции для быстрого создания функций доступа. Модуль operator содержит функции: itemgetter(), attrgetter(), и methodcaller().


Используя эти функции, примеры выше становятся проще и быстрее:

>>> from operator import itemgetter, attrgetter

1 >>>from operator import itemgetter,attrgetter

>>> sorted(student_tuples, key=itemgetter(2))

1 2

>>>sorted(student_tuples,key=itemgetter(2))

(‘dave’,’B’,10),(‘jane’,’B’,12),(‘john’,’A’,15)

>>> sorted(student_objects, key=attrgetter(‘age’))

1 2

>>>sorted(student_objects,key=attrgetter(‘age’))

(‘dave’,’B’,10),(‘jane’,’B’,12),(‘john’,’A’,15)

Функции модуля operator позволяют несколько уровней сортировки. Для примера, сортировка по классу и по возрасту:

>>> sorted(student_tuples, key=itemgetter(1,2))

1 2

>>>sorted(student_tuples,key=itemgetter(1,2))

(‘john’,’A’,15),(‘dave’,’B’,10),(‘jane’,’B’,12)

>>> sorted(student_objects, key=attrgetter(‘grade’, ‘age’))

1 2

>>>sorted(student_objects,key=attrgetter(‘grade’,’age’))

(‘john’,’A’,15),(‘dave’,’B’,10),(‘jane’,’B’,12)

Плавная сортировка :: Smoothsort

  • I. Создаём из массива кучу леонардовых куч, каждая из которых является сортирующим деревом.
    • I.1. Перебираем элементы массива слева-направо.
    • II.1. Проверяем, можно ли с помощью текущего элемента объединить две крайние слева кучи в уже имеющейся куче леонардовых куч:
      • II.1.а. Если да, то объединяем две крайние слева кучи в одну, текущий элемент становится корнем этой кучи, делаем просейку для объединённой кучи.
      • II.1.б. Если нет, то добавляем текущий элемент в качестве новой кучи (состоящей пока из одного узла) в имеющуюся кучу леонардовых куч.
  • II. Извлекаем из куч текущие максимальные элементы, которые перемещаем в конец неотсортированной части массива:
    • II.1. Ищем максимумы в леонардовых кучах. Так как на предыдущем этапе для куч постоянно делалась просейка, максимумы находятся в корнях этих куч.
    • II.2. Найденный максимум (который является корнем одной из куч) меняем местами с последним элементом массива (который является корнем самой последней кучи).
    • II.3. После этого обмена куча, в которой был найден максимум перестала быть сортирующим деревом. Поэтому делаем для неё просейку.
    • II.4. В последней куче удаляем корень (в которой находится текущий максимум), в результате чего эта куча распадается на две кучи поменьше.
    • II.5. После перемещения максимального элемента в конец, отсортированная часть массива увеличилась, а неотсортированная часть уменьшилась. Повторяем пункты II.1-II.4 для оставшейся неотсортированной части массива.

Operator Module Functions

The key-function patterns shown above are very common, so Python provides convenience functions to make accessor functions easier and faster. The has itemgetter, attrgetter, and starting in Python 2.6 a methodcaller function.

Using those functions, the above examples become simpler and faster.

>>> from operator import itemgetter, attrgetter, methodcaller

>>> sorted(student_tuples, key=itemgetter(2))


>>> sorted(student_objects, key=attrgetter('age'))

The operator module functions allow multiple levels of sorting. For example, to sort by grade then by age:

>>> sorted(student_tuples, key=itemgetter(1,2))


>>> sorted(student_objects, key=attrgetter('grade', 'age'))

The third function from the operator module, methodcaller is used in the following example in which the weighted grade of each student is shown before sorting on it:

>>> 

>>> sorted(student_objects, key=methodcaller('weighted_grade'))

Старый способ «декорируем-сортируем-раздекорируем»

Данная идиома так называется по трём её шагам:

  1. Сначала исходный список дополняется новыми значениями, контролирующими порядок сортировки.
  2. Затем новый список сортируется.
  3. После этого добавленные значения убираются, и в итоге остаётся отсортированный список, содержащий только исходные элементы.

Вот так, например, можно отсортировать данные учеников по оценке:

Это работает из-за того, что кортежи сравниваются лексикографически; сравниваются первые элементы; если они совпадают, то сравниваются вторые и так далее.

Не всегда обязательно включать индекс в декорируемый список, однако он даёт некоторые преимущества:

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

По-другому эта идиома называется преобразованием Шварца в честь Рэндела Шварца, который популяризировал её среди Perl-программистов.

Для больших списков и списков, где информацию для сравнения дорого вычислять, а также для версий Python ниже 2.4 «декорируем-сортируем-раздекорируем», наверное, будет самым быстрым способом сортировки. Для версий 2.4+ ту же функциональность предоставляют функции-ключи.

Методы списков

Давайте теперь предположим, что у нас имеется список из чисел:

a = 1, -54, 3, 23, 43, -45, 

и мы хотим в конец этого списка добавить значение. Это можно сделать с помощью метода:

a.append(100)

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

a = a.append(100)

категорически не следует, так мы только потеряем весь наш список! И этим методы списков отличаются от методов строк, когда мы записывали:

string="Hello"
string = string.upper()

Здесь метод upper возвращает измененную строку, поэтому все работает как и ожидается. А метод append ничего не возвращает, и присваивать значение None переменной a не имеет смысла, тем более, что все работает и так:

a = 1, -54, 3, 23, 43, -45, 
a.append(100)

Причем, мы в методе append можем записать не только число, но и другой тип данных, например, строку:

a.append("hello")

тогда в конец списка будет добавлен этот элемент. Или, булевое  значение:

a.append(True)

Или еще один список:

a.append(1,2,3)

И так далее. Главное, чтобы было указано одно конкретное значение. Вот так работать не будет:

a.append(1,2)

Если нам нужно вставить элемент в произвольную позицию, то используется метод

a.insert(3, -1000)

Здесь мы указываем индекс вставляемого элемента и далее значение самого элемента.

Следующий метод remove удаляет элемент по значению:

a.remove(True)
a.remove('hello')

Он находит первый подходящий элемент и удаляет его, остальные не трогает. Если же указывается несуществующий элемент:

a.remove('hello2')

то возникает ошибка. Еще один метод для удаления

a.pop()

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

end = a.pop()

Также в этом методе можно указывать индекс удаляемого элемента, например:

a.pop(3)

Если нам нужно очистить весь список – удалить все элементы, то можно воспользоваться методом:

a.clear()

Получим пустой список. Следующий метод

a = 1, -54, 3, 23, 43, -45, 
c = a.copy()

возвращает копию списка. Это эквивалентно конструкции:

c = list(a)

В этом можно убедиться так:

c1 = 1

и список c будет отличаться от списка a.

Следующий метод count позволяет найти число элементов с указанным значением:

c.count(1)
c.count(-45)

Если же нам нужен индекс определенного значения, то для этого используется метод index:

c.index(-45)
c.index(1)

возвратит 0, т.к. берется индекс только первого найденного элемента. Но, мы здесь можем указать стартовое значение для поиска:

c.index(1, 1)

Здесь поиск будет начинаться с индекса 1, то есть, со второго элемента. Или, так:

c.index(23, 1, 5)

Ищем число 23 с 1-го индекса и по 5-й не включая его. Если элемент не находится

c.index(23, 1, 3)

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

23 in c1:3

и при значении True далее уже определять индекс этого элемента.

Следующий метод

c.reverse()

меняет порядок следования элементов на обратный.

Последний метод, который мы рассмотрим, это

c.sort()

выполняет сортировку элементов списка по возрастанию. Для сортировки по убыванию, следует этот метод записать так:

c.sort(reverse=True)

Причем, этот метод работает и со строками:

lst = "Москва", "Санкт-Петербург", "Тверь", "Казань"
lst.sort()

Здесь используется лексикографическое сравнение, о котором мы говорили, когда рассматривали строки.

Это все основные методы списков и чтобы вам было проще ориентироваться, приведу следующую таблицу:

Метод

Описание

append()

Добавляет элемент в конец списка

insert()

Вставляет элемент в указанное место списка

remove()

Удаляет элемент по значению

pop()

Удаляет последний элемент, либо элемент с указанным индексом

clear()

Очищает список (удаляет все элементы)

copy()

Возвращает копию списка

count()

Возвращает число элементов с указанным значением

index()

Возвращает индекс первого найденного элемента

reverse()

Меняет порядок следования элементов на обратный

sort()

Сортирует элементы списка

Быстрый алгоритм Евклида

Но у этого алгоритма есть один существенный недостаток: если мы введем два вот таких числа:

100000000 и 2

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

4-2 = 2

После чего оба числа станут равными и НОД будет равен двум. Так вот, чтобы без лишних операций сразу определить на сколько будут отличаться два числа после серии вычитаний, достаточно взять целый остаток от деления. Например:

100000000 % 2 = 0

Это значит, что большее число можно полностью составить из суммы двоек. Следовательно, они оба делятся на два нацело и их НОД равен 2. Хорошо, а если вместо 2 взять 3. В этом случае имеем:

100000000 % 3 = 1

и далее уже можно рассматривать два числа: 3 и 1. Причем, для них также можно выполнить такую же операцию:

3 % 1 = 1 1 % 1 = 0

Все, получили НОД, равный 1. И смотрите, здесь на каждой итерации большее число делится на меньшее. Поэтому быстрый алгоритм Евклида можно записать так:

пока меньшее число больше 0         большему числу присваиваем остаток от деления на меньшее число выводим большее число

Реализуем этот алгоритм. И договоримся, что большее число будем хранить в a, меньшее – в b.

a = int(input("Введите 1-е натуральное число: "))
b = int(input("Введите 2-е натуральное число: "))
sa = a; sb = b
b = min(sa, sb)
a = max(sa, sb)
while b:
    a,b = b, a%b
 
print("НОД(%d, %d) = %d"%(sa,sb,a))

В этом алгоритме используется свойство:

a%b = c,  c < b

то есть, остаток всегда будет меньше числа b. Значит, из двух чисел c и b большим будет b, а меньшим – c. Именно поэтому в программе записано такое множественное присваивание:

a,b = b, a%b

Мы здесь переменной a присваиваем значение b, а b становится равным остатку от деления. Это гарантируется, что a >= b.

Видео по теме

Python 3 #1: установка и запуск интерпретатора языка

Python 3 #2: переменные, оператор присваивания, типы данных

Python 3 #3: функции input и print ввода/вывода

Python 3 #4: арифметические операторы: сложение, вычитание, умножение, деление, степень

Python 3 #5: условный оператор if, составные условия с and, or, not

Python 3 #6: операторы циклов while и for, операторы break и continue

Python 3 #7: строки — сравнения, срезы строк, базовые функции str, len, ord, in

Python 3 #8: методы строк — upper, split, join, find, strip, isalpha, isdigit и другие

Python 3 #9: списки list и функции len, min, max, sum, sorted

Python 3 #10: списки — срезы и методы: append, insert, pop, sort, index, count, reverse, clear

Python 3 #11: списки — инструмент list comprehensions, сортировка методом выбора

Python 3 #12: словарь, методы словарей: len, clear, get, setdefault, pop


Python 3 #13: кортежи (tuple) и операции с ними: len, del, count, index

Python 3 #14: функции (def) — объявление и вызов

Python 3 #15: делаем «Сапер», проектирование программ «сверху-вниз»

Python 3 #16: рекурсивные и лямбда-функции, функции с произвольным числом аргументов

Python 3 #17: алгоритм Евклида, принцип тестирования программ

Python 3 #18: области видимости переменных — global, nonlocal

Python 3 #19: множества (set) и операции над ними: вычитание, пересечение, объединение, сравнение

Python 3 #20: итераторы, выражения-генераторы, функции-генераторы, оператор yield

Python 3 #21: функции map, filter, zip

Python 3 #22: сортировка sort() и sorted(), сортировка по ключам

Python 3 #23: обработка исключений: try, except, finally, else

Python 3 #24: файлы — чтение и запись: open, read, write, seek, readline, dump, load, pickle

Python 3 #25: форматирование строк: метод format и F-строки

Python 3 #26: создание и импорт модулей — import, from, as, dir, reload

Python 3 #27: пакеты (package) — создание, импорт, установка (менеджер pip)

Python 3 #28: декораторы функций и замыкания

Python 3 #29: установка и порядок работы в PyCharm

Быстрая сортировка (Quick Sort)

Этот широко известный алгоритм сортировки был разработан английским информатиком Чарльзом Хоаром во время его работы в МГУ в советские годы.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n-элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Быстрая сортировка относится к алгоритмам «разделяй и властвуй».


Алгоритм состоит из трёх шагов:

  1. Выбор опорного элемента из массива.
  2. Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные — после.
  3. Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.

С исходным кодом алгоритма и его интерактивной презентацией вы сможете ознакомиться на специальном ресурсе.

Старый способ с использованием параметра cmp

Многие из приведённых здесь примеров подразумевают использование Python версии 2.4 и выше. До этой версии не было функции , а не принимал ключевых аргументов. Вместо этого все версии Python 2.x поддерживали параметр для обработки пользовательских функций сравнения.

В Python 3.0 от этого параметра полностью избавились в целях упрощения языка и разрешения конфликта между операторами сравнения и методами .

В Python 2.x в можно было передать функцию, которая использовалась бы для сравнения элементов. Она должна принимать два аргумента и возвращать отрицательное значение для случая «меньше чем», положительное — для «больше чем» и ноль, если они равны. Например:

Можно сравнивать в обратном порядке:

При портировании кода с версии 2.x на 3.x может возникнуть ситуация, когда нужно преобразовать пользовательскую функцию для сравнения в функцию-ключ. Следующая обёртка упрощает эту задачу:

Чтобы произвести преобразование, просто оберните старую функцию:

В Python 2.7 функция была добавлена в модуль functools.

Сортировка с функцией

Аргумент key принимает функцию и позволяет выполнять более сложные операции сортировки.

Самый простой пример – сортировка элементов по длине:

directions =  

directions.sort(key=len)

print('Sorted list:', directions)

Мы используем функцию len(), чтобы вернуть количество символов в строке, которая используется в качестве компаратора:

Sorted list: 

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

def sum_digits(num): 
    digits =  
    return sum(digits) 
      
numbers =  

numbers.sort(reverse=True, key=sum_digits)

print('Sorted list:', numbers)
Sorted list: 

Другим примером может быть использование ключевого аргумента для сортировки сложного списка, такого как список кортежей:

numbers = 

numbers.sort(key=lambda k: k)

print('Sorted list:', numbers)

Мы используем анонимную (лямбда) функцию, которая возвращает первый элемент кортежа. Список отсортирован по значению, возвращенному функцией:

Sorted list: 

Тот же подход можно использовать для сортировки списка словарей:

elements = 

elements.sort(key=lambda k: k)

print('Sorted list:', elements)

Лямбда-функция возвращает значение nameключа, которое используется для сравнения:

Sorted list: 

Лучший и более быстрый способ сортировки сложной функции – использовать функции модуля «Оператор». Вот пример:

from operator import itemgetter

elements = 

elements.sort(key=itemgetter('symbol')) 

print('Sorted list:', elements)

Функция itemgetter считывает значение ключа symbol:

Sorted list: 

С этим читают