Объяснение алгоритмов сортировки с примерами на python

Задания для самоподготовки

1. Пользователь
вводит с клавиатуры числа, до тех пор, пока не введет число 0. На основе
введенных данных нужно сформировать список, состоящий из квадратов введенных
чисел.

2. Написать
программу удаления из списка

всех номеров с
кодом «+7».

3. Написать
программу циклического сдвига элементов списка влево. Например, дан список:

после сдвига на
один элемент влево, должны получить:

Реализовать
через цикл, перебирая все элементы.

4. Написать
аналогичную программу циклического сдвига, но теперь вправо.

Видео по теме

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

Python 3 #30: функция enumerate, примеры использования

Алгоритм быстрой сортировки

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

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

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

def quicksort(a, arr_type):
    def do_partition(a, arr_type, start, end):
        # Performs the partitioning of the subarray a
        
        # We choose the last element as the pivot
        pivot_idx = end
        pivot = a

        # Keep an index for the first partition
        # subarray (elements lesser than the pivot element)
        idx = start - 1

        def increment_and_swap(j):
            nonlocal idx
            idx += 1
            a, a = a, a

         < pivot]
        
        # Finally, we need to swap the pivot (a with a)
        # since we have reached the position of the pivot in the actual
        # sorted array
        a, a = a, a

        # Return the final updated position of the pivot
        # after partitioning
        return idx+1

    def quicksort_helper(a, arr_type, start, end):
        if start < end:
            # Do the partitioning first and then go via
            # a top down divide and conquer, as opposed
            # to the bottom up mergesort
            pivot_idx = do_partition(a, arr_type, start, end)
            quicksort_helper(a, arr_type, start, pivot_idx-1)
            quicksort_helper(a, arr_type, pivot_idx+1, end)

    quicksort_helper(a, arr_type, 0, len(a)-1)

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

Прецедент:

b = array.array('i', )
print('Before QuickSort ->', b)
quicksort(b, 'i')
print('After QuickSort ->', b)

Вывод:

Before QuickSort -> array('i', )
After QuickSort -> array('i', )

Начало работы с методами сортировки Pandas ↑

Напоминаем, что DataFrame — это структура данных с помеченными осями для строк и столбцов. Вы можете отсортировать DataFrame по значению строки или столбца, а также по индексу строки или столбца.

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

Подготовка набора данных   

В этом уроке будем работать с данными об экономии топлива, собранными Агентством по охране окружающей среды США (EPA) на транспортных средствах, выпущенных в период с 1984 по 2021 год. Набор данных EPA по экономии топлива великолепен, потому что он содержит много различных типов информации, которую вы можете отсортировать, включая текстовую и числовою информацию. Набор данных содержит всего восемьдесят три колонки.

Чтобы продолжить, вам понадобится установленная библиотека Python pandas. Код в этом руководстве был выполнен с использованием pandas 1.2.0 и Python 3.9.1.

Для анализа будем просматривать данные о MPG (миля на галлон) для транспортных средств по маркам, моделям, годам и другим характеристикам транспортных средств. Можно указать, какие столбцы следует читать в DataFrame. Для этого урока вам понадобится только часть доступных столбцов. Вот команды для чтения соответствующих столбцов набора данных по экономии топлива в DataFrame и для отображения первых пяти строк:

>>> import pandas as pd

>>> column_subset = 

>>> df = pd.read_csv(
...     "https://www.fueleconomy.gov/feg/epadata/vehicles.csv",
...     usecols=column_subset,
...     nrows=100
... )

>>> df.head()
   city08  cylinders fuelType  ...  mpgData            trany  year
0      19          4  Regular  ...        Y     Manual 5-spd  1985
1       9         12  Regular  ...        N     Manual 5-spd  1985
2      23          4  Regular  ...        Y     Manual 5-spd  1985
3      10          8  Regular  ...        N  Automatic 3-spd  1985
4      17          4  Premium  ...        N     Manual 5-spd  1993

Вызывая с URL-адресом набора данных, вы можете загрузить данные в DataFrame. Сокращение количества столбцов приводит к более быстрой загрузке и меньшему использованию памяти. Чтобы еще больше ограничить потребление памяти и быстро почувствовать данные, вы можете указать, сколько строк загружать, используя .

Знакомство с .sort_values()   

Для сортировки значений в DataFrame по любой оси (столбцы или строки) используем . Как правило, требуется отсортировать строки в DataFrame по значениям одного или нескольких столбцов:

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

Знакомство с .sort_index()   

используем для сортировки DataFrame по индексу строки или меткам столбцов. Отличие от заключается в том, что вы сортируете DataFrame на основе индекса строки или имени столбцов, а не значений в этих строках или столбцах:

Индекс строки DataFrame обведен синим на рисунке выше. Индекс не считается столбцом, и обычно у вас есть только один индекс строки. Индекс строки можно рассматривать как номера строк, которые начинаются с нуля.

Как работает Быстрая сортировка

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

Подумайте об этом на мгновение — как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку — случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.

Самый простой подход — просто выбрать первый (или последний) элемент. По иронии судьбы, это приводит к быстрой сортировке на уже отсортированных (или почти отсортированных) массивах.

Именно так большинство людей выбирают реализацию быстрой сортировки, и, так как это просто и этот способ выбора опоры является очень эффективной операцией, и это именно то, что мы будем делать.

Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

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

Рассмотрим пошагово то, что мы планируем сделать, это поможет проиллюстрировать весь процесс. Пусть у нас будет следующий список.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

Выберем первый элемент как опору 29), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

• Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
• Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
• Мы меняем местами low и high:

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

• Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
• Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
• Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44

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

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 44,78,87,66,31,76,58,88,83,97,41,99,44 (правая сторона). И так далее.

Скорость сортировки в Python

Python

# speed/main.py

import random

from boxx import timeit

def list_sort(arr):
return arr.sort()

def sorted_builtin(arr):
return sorted(arr)

def main():
arr =

with timeit(name=»sorted(list)»):
sorted_builtin(arr)

with timeit(name=»list.sort()»):
list_sort(arr)

if __name__ == «__main__»:
main()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

# speed/main.py   importrandom fromboxx importtimeit deflist_sort(arr) returnarr.sort() defsorted_builtin(arr) returnsorted(arr) defmain() arr=random.randint(,50)forrinrange(1_000_000) withtimeit(name=»sorted(list)») sorted_builtin(arr) withtimeit(name=»list.sort()») list_sort(arr) if__name__==»__main__» main()

Указанный выше код выводит следующий результат:

Shell

$ python main.py
«sorted(list)» spend time: 0.1104379
«list.sort()» spend time: 0.0956471

1 2 3

$python main.py «sorted(list)»spend time0.1104379 «list.sort()»spend time0.0956471

Как видите, метод немного быстрее, чем функция . Почему так получается? Разберем обе функции и посмотрим, сможет ли байтовый код дать ответ:

Python

>>> import dis
>>> dis.dis(list_sort)
12 0 LOAD_FAST 0 (arr)
2 LOAD_METHOD 0 (sort)
4 CALL_METHOD 0
6 RETURN_VALUE
>>> dis.dis(sorted_builtin)
16 0 LOAD_GLOBAL 0 (sorted)
2 LOAD_FAST 0 (arr)
4 CALL_FUNCTION 1
6 RETURN_VALUE

1 2 3 4 5 6 7 8 9 10 11

>>>importdis >>>dis.dis(list_sort) 12LOAD_FAST(arr) 2LOAD_METHOD(sort) 4CALL_METHOD 6RETURN_VALUE >>>dis.dis(sorted_builtin) 16LOAD_GLOBAL(sorted) 2LOAD_FAST(arr) 4CALL_FUNCTION1 6RETURN_VALUE

Байтовый код обеих функций практически идентичен. Единственное различие в том, что функция сначала загружает список, и за методом (sort) следует вызванный метод списка без аргументов. Если сравнить, функция сначала загружает встроенную функцию , а за ней следует список и вызов загруженной функции со списком в качестве аргумента.

Почему же временные результаты отличаются?

Можно предположить, что в то время как может работать с известным размером и менять элементы внутри данного размера, должен работать c неизвестным размером. Следовательно, если при добавлении нового элемента не хватает памяти, нужно изменить размер нового списка, созданного через . На это требуется время! Если просмотреть исходный код CPython, можно найти следующий комментарий об изменении размера списка объектов:

Помните, что сейчас мы работаем со списком из 1 000 000 элементов — изменений размера будет довольно много! К несчастью, пока что это лучший ответ на вопрос, почему на 13% быстрее, чем .

Python

new_array = arr.copy()
arr.sort()

1 2	new_array=arr.copy() arr.sort()

Имплементация приводит к разнице во времени выполнения, поскольку создание копии списка занимает некоторое время.

Выполняет сортировку последовательности по возростанию/убыванию.

Параметры:

• — объект, поддерживающий итерирование
• — пользовательская функция, которая применяется к каждому элементу последовательности
• — порядок сортировки

Описание:

Функция вернет новый отсортированный t-list] из итерируемых элементов. Функция имеет два необязательных аргумента, которые должны быть указаны в качестве аргументов ключевых слов.

Аргумент принимает функцию, например . Переданная функция вычисляет результат для каждого элемента последовательности, который используется для сравнения элементов при сортировке. Значением по умолчанию является , т.е. сравнивать элементы напрямую (как есть).

Аргумент имеет логическое значение. Если установлено значение , то элементы списка сортируются в обратной последовательности (по убыванию).

Используйте для преобразования функции, использующей cmp (старый стиль) в использующую key (новый стиль).

Встроенная функция sorted() является гарантированно стабильной. Это означает, что когда несколько элементов последовательности имеют равные значения, их первоначальный порядок сохраняется. Такое поведение полезно при сортировке в несколько проходов.

Примеры различных способов сортировки последовательностей.

Сортировка слов в предложении без учета регистра:

line = 'This is a test string from Andrew'
x = sorted(line.split(), key=str.lower)
print(x)
# 

Сортировка сложных объектов с использованием индексов в качестве ключей :

student = 
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
    

# Сортируем по возрасту student
x = sorted(student, key=lambda student student2])
print(x)
# 

Тот же метод работает для объектов с именованными атрибутами.

class Student
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age
    def __repr__(self):
        return repr((self.name, self.grade, self.age))

student = 
    Student('john', 'A', 15),
    Student('jane', 'B', 12),
    Student('dave', 'B', 10),
    

x = sorted(student, key=lambda student student.age)
print(x)
# 

Сортировка по убыванию:

student = 
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
    

# Сортируем по убыванию возраста student
x = sorted(student, key=lambda i i2], reverse=True)
print(x)
# 

Стабильность сортировки и сложные сортировки:

data = 
x = sorted(data, key=lambda data data])
print(x)
# 

Обратите внимание, как две записи (‘blue’, 1), (‘blue’, 2) для синего цвета сохраняют свой первоначальный порядок. Это замечательное свойство позволяет создавать сложные сортировки за несколько проходов по нескольким ключам

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

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

student = 
    ('john', 15, 4.1),
    ('jane', 12, 4.9),
    ('dave', 10, 3.9),
    ('kate', 11, 4.1),
    

# По средней оценке
x = sorted(student, key=lambda num num2])
# По убыванию возраста
y = sorted(x, key=lambda age age1], reverse=True)
print(y)
# 

А еще, для сортировок по нескольким ключам, удобнее использовать модуль . Функции модуля допускают несколько уровней сортировки. Например, как в предыдущем примере успеваемость будет первым ключом, возраст вторым.Только сортировать будем все по возрастанию:

from operator import itemgetter

x = sorted(student, key=itemgetter(2,1))
print(x)
# 

Поддержание порядка сортировки

В стандартной библиотеке Python нет модулей, аналогичных типам данных C++ вроде и . Python делегирует эту задачу сторонним библиотекам, доступным в Python Package Index: они используют различные методы для сохранения типов , и в отсортированном порядке. Поддержание порядка с помощью специальной структуры данных может помочь избежать очень медленного поведения (квадратичного времени выполнения) при наивном подходе с редактированием и постоянной пересортировкой данных. Вот некоторые из модулей, реализующих эти типы данных:

• SortedContainers — реализация сортированных типов , и на чистом Python, по скорости не уступает реализациям на C. Тестирование включает 100% покрытие кода и многие часы стресс-тестирования. В документации можно найти полный справочник по API, сравнение производительности и руководства по внесению своего вклада.
• rbtree — быстрая реализация на C для типов и . Реализация использует структуру данных, известную как красно-чёрное дерево.
• treap — сортированный . В реализации используется Декартово дерево, а производительность улучшена с помощью Cython.
• bintrees — несколько реализаций типов и на основе деревьев на C. Самые быстрые основаны на АВЛ и красно-чёрных деревьях. Расширяет общепринятый API для предоставления операций множеств для словарей.
• banyan — быстрая реализация и на C.
• skiplistcollections — реализация на чистом Python, основанная на списках с пропусками, предлагает ограниченный API для типов и .
• blist — предоставляет сортированные типы , и , основанные на типе данных «blist», реализация на Б-деревьях. Написано на Python и C.

9

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

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

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()	Сортирует элементы списка

Odd and Ends¶

• For locale aware sorting, use for a key function or
  for a comparison function.

• The reverse parameter still maintains sort stability (so that records with
  equal keys retain the original order). Interestingly, that effect can be
  simulated without the parameter by using the builtin function
  twice:

  >>> data = 
  >>> standard_way = sorted(data, key=itemgetter(), reverse=True)
  >>> double_reversed = list(reversed(sorted(reversed(data), key=itemgetter())))
  >>> assert standard_way == double_reversed
  >>> standard_way
  
  

• The sort routines are guaranteed to use when making comparisons
  between two objects. So, it is easy to add a standard sort order to a class by
  defining an method:

  >>> Student.__lt__ = lambda self, other self.age < other.age
  >>> sorted(student_objects)
  
  

• Key functions need not depend directly on the objects being sorted. A key
  function can also access external resources. For instance, if the student grades
  are stored in a dictionary, they can be used to sort a separate list of student
  names:

  >>> students = 'dave', 'john', 'jane'
  >>> newgrades = {'john' 'F', 'jane''A', 'dave' 'C'}
  >>> sorted(students, key=newgrades.__getitem__)
  
  

Python sort list by multiple sort criteria

The following example sorts a list of students by two sorting
criteria.

multiple_sort.py

#!/usr/bin/env python3

from typing import NamedTuple
from operator import attrgetter


def multi_sort(data, specs):

    for key, reverse in reversed(specs):
        data.sort(key=attrgetter(key), reverse=reverse)
    return data


class Student(NamedTuple):
    id: int
    name: str
    grade: str
    age: int


s1 = Student(1, 'Patrick', 'A', 21)
s2 = Student(2, 'Lucia', 'B', 19)
s3 = Student(3, 'Robert', 'C', 19)
s4 = Student(4, 'Monika', 'A', 22)
s5 = Student(5, 'Thomas', 'D', 20)
s6 = Student(6, 'Petra', 'B', 18)
s6 = Student(7, 'Sofia', 'A', 18)
s7 = Student(8, 'Harold', 'E', 22)
s8 = Student(9, 'Arnold', 'B', 23)

students = 

multi_sort(students, (('grade', False), ('age', True)))

for student in students:
    print(student)

First, the students are sorted by grades in ascending order, then
they are sorted by age in descending order.

def multi_sort(data, specs):

    for key, reverse in reversed(specs):
        data.sort(key=attrgetter(key), reverse=reverse)
    return data

The method applies all the sorting specs
on the list.

$ ./multi_sort.py 
Student(id=4, name='Monika', grade='A', age=22)
Student(id=1, name='Patrick', grade='A', age=21)
Student(id=7, name='Sofia', grade='A', age=18)
Student(id=9, name='Arnold', grade='B', age=23)
Student(id=2, name='Lucia', grade='B', age=19)
Student(id=3, name='Robert', grade='C', age=19)
Student(id=5, name='Thomas', grade='D', age=20)
Student(id=8, name='Harold', grade='E', age=22)

This is the output.