Топ-5 алгоритмов сортировки на python

Введение

Быстрая сортировка — популярный алгоритм сортировки, который часто используется вместе с сортировкой слиянием. Это алгоритм является хорошим примером эффективного алгоритма сортировки со средней сложностью O(n log_n). Часть его популярности еще связана с простотой реализации.

Быстрая сортировка является представителем трех типов алгоритмов: divide and conquer (разделяй и властвуй), in-place (на месте) и unstable (нестабильный).

• Divide and conquer: Быстрая сортировка разбивает массив на меньшие массивы до тех пор, пока он не закончится пустым массивом, или массивом, содержащим только один элемент, и затем все рекурсивно соединяется в сортированный большой массив.
• In place: Быстрая сортировка не создает никаких копий массива или его подмассивов. Однако этот алгоритм требует много стековой памяти для всех рекурсивных вызовов, которые он делает.
• Unstable: стабильный (stable) алгоритм сортировки — это алгоритм, в котором элементы с одинаковым значением отображаются в том же относительном порядке в отсортированном массиве, что и до сортировки массива. Нестабильный алгоритм сортировки не гарантирует этого, это, конечно, может случиться, но не гарантируется. Это может быть важным, когда вы сортируете объекты вместо примитивных типов. Например, представьте, что у вас есть несколько объектов Person одного и того же возраста, например, Дейва в возрасте 21 года и Майка в возрасте 21 года. Если бы вы использовали Quicksort в коллекции, содержащей Дейва и Майка, отсортированных по возрасту, нет гарантии, что Дейв будет приходить раньше Майка каждый раз, когда вы запускаете алгоритм, и наоборот.

Простая сортировка

Чтобы отсортировать список по возрастанию вызовите функцию sorted(). Функция вернёт новый сортированный список:

>>>
>>> sorted()

1 2 3

>>> >>>sorted(5,2,3,1,4) 1,2,3,4,5

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

>>> a =
>>> a.sort()
>>> a

1 2 3 4

>>>a=5,2,3,1,4 >>>a.sort() >>>a 1,2,3,4,5

Метод определён только для списков. В отличи от него, функция sorted() работает с любыми перечисляемыми объектами:

>>> sorted({1: ‘D’, 2: ‘B’, 3: ‘B’, 4: ‘E’, 5: ‘A’})

1 2	>>>sorted({1’D’,2’B’,3’B’,4’E’,5’A’}) 1,2,3,4,5

Входные данные не меняются

Пусть есть два списка и .

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

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

Перейдем к коду:

Заметим, что в данном коде используется только перемещение вперед по списку. Поэтому будет достаточно работать с итераторами. Перепишем алгоритм с помощью итераторов.

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

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

Встроенные реализации

Рассмотрим еще несколько способов слияния через встроенные в python функции.

• из . Как говорит документация, эта функция делает именно то, что мы хотим, и больше: объединяет несколько итерируемых объекта, можно задать ключ, можно сортировать в обратном порядке.

  Тогда нам нужно просто импортировать и использовать:

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

  Воспользуемся для слияния элементов и :

• И, наконец, просто сортировка. Объединяем и сортируем заново.

Сортировка слиянием

Этот алгоритм относится к алгоритмам «разделяй и властвуй». Он разбивает список на две части, каждую из них он разбивает ещё на две и т. д. Список разбивается пополам, пока не останутся единичные элементы.

Соседние элементы становятся отсортированными парами. Затем эти пары объединяются и сортируются с другими парами. Этот процесс продолжается до тех пор, пока не отсортируются все элементы.

Алгоритм

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

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

Реализация

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

Функция operator.itemgetter

При сортировке кортежей частой задачей является сортировка
по какому-то одному элементу кортежа. Например, если нужно отсортировать
кортежи по элементу с индексом 1, то можно написать такую лямбда-функцию:

a.sort(key=lambda elem: elem)

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

def itemgetter(i):
    return lambda elem: elem

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

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

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

>>> data = 
>>> sorted(data, key=itemgetter(0))

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

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

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

>>> s = sorted(student_objects, key=attrgetter('age'))     # sort on secondary key
>>> sorted(s, key=attrgetter('grade'), reverse=True)       # now sort on primary key, descending

Можно абстрагировать все это в функцию-оболочку, которая может принимать список и кортежи поля и упорядочивать их за нескольких проходах.

>>> def multisort(xs, specs):
...    for key, reverse in reversed(specs):
...        xs.sort(key=attrgetter(key), reverse=reverse)
...    return xs

>>> multisort(list(student_objects), (('grade', True), ('age', False)))

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

Сортировка гарантировано стабильная. Когда несколько записей имеют одинаковый ключ их порядок всегда сохраняется.

>>> data =
>>> sorted(data, key=itemgetter(0))

1 2 3

>>>data=(‘red’,1),(‘blue’,1),(‘red’,2),(‘blue’,2) >>>sorted(data,key=itemgetter()) (‘blue’,1),(‘blue’,2),(‘red’,1),(‘red’,2)

Заметьте что две записи с сохраняют исходный порядок, так что гарантировано впереди .

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

>>> s = sorted(student_objects, key=attrgetter(‘age’)) # сортировка по вторичному ключу
>>> sorted(s, key=attrgetter(‘grade’), reverse=True) # сортировка по первичному ключу

1 2 3

>>>s=sorted(student_objects,key=attrgetter(‘age’))# сортировка по вторичному ключу >>>sorted(s,key=attrgetter(‘grade’),reverse=True)# сортировка по первичному ключу (‘dave’,’B’,10),(‘jane’,’B’,12),(‘john’,’A’,15)

Эту возможность можно абстрагировать и обернуть в функцию которая принимает список и кортежи из полей и порядка сортировки:

>>> def multisort(xs, specs):
… for key, reverse in reversed(specs):
… xs.sort(key=attrgetter(key), reverse=reverse)
… return xs
>>> multisort(list(student_objects), ((‘grade’, True), (‘age’, False)))

1 2 3 4 5 6

>>>def multisort(xs,specs) …forkey,reverse inreversed(specs) …xs.sort(key=attrgetter(key),reverse=reverse) …returnxs >>>multisort(list(student_objects),((‘grade’,True),(‘age’,False))) (‘dave’,’B’,10),(‘jane’,’B’,12),(‘john’,’A’,15)

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

Python Tutorial

Python HOMEPython IntroPython Get StartedPython SyntaxPython CommentsPython Variables
Python Variables
Variable Names
Assign Multiple Values
Output Variables
Global Variables
Variable Exercises

Python Data TypesPython NumbersPython CastingPython Strings
Python Strings
Slicing Strings
Modify Strings
Concatenate Strings
Format Strings
Escape Characters
String Methods
String Exercises

Python BooleansPython OperatorsPython Lists
Python Lists
Access List Items
Change List Items
Add List Items
Remove List Items
Loop Lists
List Comprehension
Sort Lists
Copy Lists
Join Lists
List Methods
List Exercises

Python Tuples
Python Tuples
Access Tuples
Update Tuples
Unpack Tuples
Loop Tuples
Join Tuples
Tuple Methods
Tuple Exercises

Python Sets
Python Sets
Access Set Items
Add Set Items
Remove Set Items
Loop Sets
Join Sets
Set Methods
Set Exercises

Python Dictionaries
Python Dictionaries
Access Items
Change Items
Add Items
Remove Items
Loop Dictionaries
Copy Dictionaries
Nested Dictionaries
Dictionary Methods
Dictionary Exercise

Python If…ElsePython While LoopsPython For LoopsPython FunctionsPython LambdaPython ArraysPython Classes/ObjectsPython InheritancePython IteratorsPython ScopePython ModulesPython DatesPython MathPython JSONPython RegExPython PIPPython Try…ExceptPython User InputPython String Formatting

insert (индекс, объект)

Этот метод вставляет объект непосредственно перед указанным индексом.

Если значение индекса больше, чем длина списка, объект добавляется в конец.

Если значение индекса отрицательное и не входит в диапазон, то объект добавляется в начало.

>>> my_list = 
>>> 
>>> my_list.insert(1, 'X')  # insert just before index 1
>>> print(my_list)

>>> 
>>> my_list.insert(100, 'Y')  # insert at the end of the list
>>> print(my_list)

>>> 
>>> my_list.insert(-100, 'Z')  # negative and not in range, so insert at the start
>>> print(my_list)

>>> my_list.insert(-2, 'A')  # negative and in the range, so insert before second last element
>>> print(my_list)

>>> 

Работа с массивами с изменяемым размером в python

Как правило в программах Python размер массива не четко задан, может вводиться с клавиатуры, может изменяться и размер массива, элементы могут добавляться и удаляться.
Для работы с массивами изменяемого размера в Python используется специальное объявление массива Объявление  массива с неизвестным числом элементов в pythonИмя массива=[]Задание массива явноИмя массива=Вывод всего массива в pythonprint(имя массива)
Напримерa=[]
a=
print(a)
Добавление элемента в конец массива вpythonИмя массива.append(значение)
Напримерa=[]
a=
print(a)
a.append(7)
print(a)
будет выведено на экран
Ввод массива с клавиатуры в python
Для ввода массива с неизвестным числом элементов в python в программе запрашивается чилсо элементов, а затем в цикле for добавляется элементы с помощью команды имямассива.append()a=[]
n=int(input())
for i in range(n):
    a.append(int(input()))
print(a)Для определения длины массива в python используется команда len(имя массива)Вывод поэлементно массива на экран в Python
Вывод массива неизвестной длины осуществляется в цикле for, верхняя граница цикла определятся с помощью команды len(имя массива)for i in range(len(a)):
    print(a)Для удаления элемента массива в python используется командаИмя массива.remove(номер элемента который нужно удалить)
Напримерa=[]
a=
print(a)
a.remove(1)
print(a)
выведет на экран
Сортировка массива в python
Для сортировки числового массива по возрастанию в python используется командаимя массива.sort()

Пример программы на Python ввода массива, вывода массива и сортировки массиваa=[]
n=int(input())
for i in range(n):
    a.append(int(input()))
print(‘массив’)
for i in range(len(a)):
    print(a)
a.sort()
print(‘отсортированный массив’)
for i in range(len(a)):
    print(a)

Вернуться к содержанию Следующая тема Работа с модулями в Питон 

Полезно почитать по теме массивы в python:Матрицы в pyhtonРабота с матрицами в python в библиотеке numpy

Ordering Values With .sort()

The very similarly named differs quite a bit from the built-in. They accomplish more or less the same thing, but the documentation for highlights two of the most critical differences between and :

>>>

First, sort is a method of the class and can only be used with lists. It is not a built-in with an iterable passed to it.

Second, returns and modifies the values in place. Let’s take a look at the impacts of both of these differences in code:

>>>

There are some pretty dramatic differences in how operates compared to in this code example:

1. There is no ordered output of , so the assignment to a new variable only passes a type.
2. The list has been changed in place, and the original order is not maintained in any way.

These differences in behavior make and absolutely not interchangeable in code, and they can produce wildly unexpected outcomes if one is used in the wrong way.

has the same and optional keyword arguments that produce the same robust functionality as . Here, you can sort a list of phrases by the second letter of the third word and return the list in reverse:

>>>

In this sample, a is used to do the following:

Алгоритм MergeSort

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

В приведенном ниже фрагменте кода метод выполняет фактическое разделение на подмассивы, а метод perform_merge() объединяет два ранее отсортированных массива в новый отсортированный.

import array

def mergesort(a, arr_type):
    def perform_merge(a, arr_type, start, mid, end):
        # Merges two previously sorted arrays
        # a and a
        tmp = array.array(arr_type, )
        def compare(tmp, i, j):
            if tmp <= tmp:
                i += 1
                return tmp
            else:
                j += 1
                return tmp
        i = start
        j = mid + 1
        curr = start
        while i<=mid or j<=end:
            if i<=mid and j<=end:
                if tmp <= tmp:
                    a = tmp
                    i += 1
                else:
                    a = tmp
                    j += 1
            elif i==mid+1 and j<=end:
                a = tmp
                j += 1
            elif j == end+1 and i<=mid:
                a = tmp
                i += 1
            elif i > mid and j > end:
                break
            curr += 1


    def mergesort_helper(a, arr_type, start, end):
        # Divides the array into two parts
        # recursively and merges the subarrays
        # in a bottom up fashion, sorting them
        # via Divide and Conquer
        if start < end:
            mergesort_helper(a, arr_type, start, (end + start)//2)
            mergesort_helper(a, arr_type, (end + start)//2 + 1, end)
            perform_merge(a, arr_type, start, (start + end)//2, end)


    # Sorts the array using mergesort_helper
    mergesort_helper(a, arr_type, 0, len(a)-1)

Прецедент:

a = array.array('i', )
print('Before MergeSort ->', a)
mergesort(a, 'i')
print('After MergeSort ->', a)

Вывод:

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

Сравнение

Пора перейти к самому интересному.
Составим список функций, которые будем сравнивать:

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

Тест первый

Проведем общий тест, размеры от до , элементы от до .

Отдельно сравним и :

тратит колоссально больше времени в общем случае, как и ожидалось.

Не будем учитывать здесь огромный , чтобы лучше видеть разницу между другими:

показал себя относительно неплохо по сравнению с ручной реализацией и .

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

Тест второй, сравнимые размеры

Размеры будут принадлежать отрезку , а увеличиваем, начиная с . Шаг .

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

Тест третий, один маленький, второй большой

Размер первого равен , размер второго .

В самом начале (на очень маленьких списках) обгоняет всех, кроме , но на чуть больших все выходит на стандартные позиции.

Тест четвертый, много повторных

Размеры фиксированы, а количество элементов увеличивается на , начиная с .

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

Key Functions¶

Both and have a key parameter to specify a
function (or other callable) to be called on each list element prior to making
comparisons.

For example, here’s a case-insensitive string comparison:

>>> sorted("This is a test string from Andrew".split(), key=str.lower)

The value of the key parameter should be a function (or other callable) that
takes a single argument and returns a key to use for sorting purposes. This
technique is fast because the key function is called exactly once for each
input record.

A common pattern is to sort complex objects using some of the object’s indices
as keys. For example:

>>> student_tuples = 
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... 
>>> sorted(student_tuples, key=lambda student student2])   # sort by age

The same technique works for objects with named attributes. For example:

>>> 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))

Предварительное использование key в функции сортировки

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

У нашей змеи есть имя, toxicity (токсичность, мерило того, насколько токсичен её яд) и agression (представленная в виде числа от 0 до 1, которое указывает на вероятность того, что змея нападет).

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

Змеи отсортированы в ожидаемом нами порядке (несмотря на то, что гремучая змея (rattlesnake) более ядовита, чем кобра (kingCobra), уровень агрессивности кобры делает её более опасной).

Какие есть методы списков в Python?

Метод списка extends

— расширяет список, добавляя элементы переданного итерируемого объекта.

Списки также можно объединять с помощью оператора +. При этом, оператор + не изменяет список, а создает новый.

Метод списка index

— возвращает индекс первого вхождения значения. Если вводного значения нет в списке, возникнет исключение ValueError. Если указан второй аргумент, поиск начнется с указанного индекса.

Метод списка insert

— добавляет значение value непосредственно перед указанным индексом index. После вставки новое значение занимает индекс index.

Метод списка pop

— удаляет и возвращает значение по индексу index. Без аргумента index удаляет и возвращает последний элемент списка.

Метод списка remove

— удаляет первое вхождение указанного значения. Если указанного значения нет в списке, выдаётся исключение ValueError.

Метод списка sort

— сортирует список в числовом и лексическом порядке и возвращает None

Списки также можно сортировать в обратном порядке используя флаг reverse=True в методе sort().

Для сортировки списка по атрибутам элементов, можно использовать аргумент key:

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

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, примеры использования

Сортировка с использованием функции attrgetter

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

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

Таким образом, attrgetter(name) возвращает функцию, которая ведет себя также как и определенная раннее нашей функцией byName_key():

Функция attrgetter(age) возвращает функцию, которая ведет себя также как и определенная раннее нашей функцией byAge_key():

Встроенные функции сортировки на Python

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

Отсортировать содержимое списка можно с помощью стандартного метода :

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

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

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

Функции в Python реализуют алгоритм Tim 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__)
  
  

Sorting a List of Objects

So what about if you have a list of generic objects and you want to sort these objects based on some custom criteria.

The key parameter is your friend.

Let’s take an example.

Assume you have a User class that looks like this

A simple class that has name and age attributes.

Let’s create some User objects and add them to a list.

Now let’s say you want to sort the objects in this list alphabetically by the name attribute.

Here is one way you can do that:

If you want to sort the objects based on the age attribute instead, here is what you need to do:

And just like that, you can define any custom sort on any python object you can think of.

Happy sorting!

Лямбда-функции

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

lambda список переменных-аргументов: возвращаемое значение

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

a = 
a.sort(key=lambda n: n % 10)

Рассмотрим другой пример. Пусть дан список точек, каждая точка: кортеж из двух чисел.
Например, . Этот список нужно отсортировать по возрастанию
расстояния от начала координат до точки. Напишем лямбда-функцию:

a.sort(key=lamda point: point ** 2 + point ** 2)

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

Функции-ключи

С версии Python 2.4 у и появился параметр  для указания функции, которая будет вызываться на каждом элементе до сравнения.

Например, вот регистронезависимое сравнение строк:

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

Конференция DataArt IT NonStop 2020

3–5 декабря, Онлайн, До 1500 ₽

tproger.ru

События и курсы на tproger.ru

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

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

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

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

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

>>> from operator import itemgetter, attrgetter

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


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

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

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


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

Если можно менять исходные списки

Предположим, что после слияния старые списки больше не нужны (как обычно и случается). Тогда можно написать еще один способ. Будем как и раньше сравнивать нулевые элементы списков и вызывать у списка с меньшим, пока один из списков не закончится.

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

Sorting a List of Tuples

Before we dive in, let’s see how Python compares two tuples.

Tuples are compared element by element starting from the first element which is very similar to how strings are compared.

In other words, you start out by comparing the first elements of the tuples and if they are not equal, this is the result of the comparison.

If they are equal, the second items are compared and so on.

If this is your goal, then just use the sort method or the sorted function and both will work just fine.

But sometimes this is not really what you want.

For example, assume you have a list of tuples where the first element in each tuple represents a name, and the second one represents the age.

And we want to sort this list of tuples by age.

how can you sort a list of tuples by the second element?

The key parameter will again come to the rescue.

We can define our custom sort by defining our own key function.

There you go!

You can even write a neater code if you want by using lambdas.

Заключение

Как мы уже упоминали ранее, эффективность быстрой сортировки сильно зависит от выбора точки опоры — он может «упростить или усложнить» сложность алгоритма во времени (и в пространстве стека). Нестабильность алгоритма также может стать препятствием для использования с пользовательскими объектами.

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

Источники используемые для написания статьи: Olivera Popović — Quicksort in Pythonhttps://stackoverflow.com/questions/18262306/quicksort-with-pythonhttps://www.geeksforgeeks.org/python-program-for-quicksort/

Spread the love