Python: how to sort a list? (the right way)

Key Functions

Starting with Python 2.4, both list.sort() and sorted() added a key parameter to specify a function 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 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 a key. For example:

>>> student_tuples = 
>>> sorted(student_tuples, key=lambda student: student)   # 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))
        def weighted_grade(self):
                return 'CBA'.index(self.grade) / float(self.age)

>>> student_objects = 
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age

Значения нотации «О» большое

На письме временная сложность алгоритма обозначается как O(n), где n — размер входной коллекции.

O(1)

Обозначение константной временной сложности. Независимо от размера коллекции, время, необходимое для выполнения операции, константно. Это обозначение константной временной сложности. Эти операции выполняются настолько быстро, насколько возможно. Например, операции, которые проверяют, есть ли внутри коллекции элементы, имеют сложность O(1).

O(log n)

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

O(n)

Обозначение линейной временной сложности. Время, необходимое для выполнения операции, прямо и линейно пропорционально количеству элементов в коллекции. Это обозначение линейной временной сложности. Это что-то среднее с точки зрения производительности. Например, если мы хотим суммировать все элементы в коллекции, нужно будет выполнить итерацию по коллекции. Следовательно, итерация коллекции является операцией O(n).

O(n log n)

Обозначение квазилинейной временной сложности. Скорость выполнения операции является квазилинейной функцией числа элементов в коллекции. Временная сложность оптимизированного алгоритма сортировки обычно равна O(n log n).

O(n^2)

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

O(n!)

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

Нотация «O» большое относительна. Она не зависит от машины, игнорирует константы и понятна широкой аудитории, включая математиков, технологов, специалистов по данным и т. д.

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

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

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

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

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

Что такое списки?

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

Чтобы использовать списки, их нужно создать. Создать список можно несколькими способами. Например, можно обработать любой итерируемый объект (например, строку) встроенной функцией list:

>>> list('список')

Список можно создать и при помощи литерала:

>>> s = []  # Пустой список
>>> l = 's', 'p', 'isok'], 2
>>> s
[]
>>> l
, 2]

Как видно из примера, список может содержать любое количество любых объектов (в том числе и вложенные списки), или не содержать ничего.

И еще один способ создать список — это генераторы списков. Генератор списков — способ построить новый список, применяя выражение к каждому элементу последовательности. Генераторы списков очень похожи на цикл for.

>>> c = c * 3 for c in 'list'
>>> c

Возможна и более сложная конструкция генератора списков:

>>> c = c * 3 for c in 'list' if c != 'i'
>>> c

>>> c = c + d for c in 'list' if c != 'i' for d in 'spam' if d != 'a'
>>> c

Быстрая сортировка

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

Алгоритм

Быстрая сортировка начинается с разбиения списка и выбора одного из элементов в качестве опорного. А всё остальное передвигаем так, чтобы этот элемент встал на своё место. Все элементы меньше него перемещаются влево, а равные и большие элементы перемещаются вправо.

Реализация

Существует много вариаций данного метода. Способ разбиения массива, рассмотренный здесь, соответствует схеме Хоара (создателя данного алгоритма).

Время выполнения

В среднем время выполнения быстрой сортировки составляет O(n log n).

Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, в отличие от сортировок кучей и слиянием, обе из которых имеют в худшем случае время сортировки O(n log n), быстрая сортировка в худшем случае будет выполняться O(n²)

The Old Way Using Decorate-Sort-Undecorate

This idiom is called Decorate-Sort-Undecorate after its three steps:

• First, the initial list is decorated with new values that control the sort order.
• Second, the decorated list is sorted.
• Finally, the decorations are removed, creating a list that contains only the initial values in the new order.

For example, to sort the student data by grade using the DSU approach:

>>> decorated = 
>>> decorated.sort()
>>>                # undecorate

This idiom works because tuples are compared lexicographically; the first items are compared; if they are the same then the second items are compared, and so on.

It is not strictly necessary in all cases to include the index i in the decorated list. Including it gives two benefits:

• The sort is stable — if two items have the same key, their order will be preserved in the sorted list.

• The original items do not have to be comparable because the ordering of the decorated tuples will be determined by at most the first two items. So for example the original list could contain complex numbers which cannot be sorted directly.

Another name for this idiom is Schwartzian transform, after Randal L. Schwartz, who popularized it among Perl programmers.

For large lists and lists where the comparison information is expensive to calculate, and Python versions before 2.4, DSU is likely to be the fastest way to sort the list. For 2.4 and later, key functions provide the same functionality.

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

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

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

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

Реализация

Сортировка массивов

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

При этом мы будем использовать две функции — partition() и quick_sort().

Давайте начнем с функции partition():

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array <= array:
            pivot += 1
            array, array = array, array
    array, array = array, array
    return pivot

И, наконец, давайте реализуем функцию quick_sort():

def quick_sort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

После того, как обе функции реализованы, мы можем запустить quick_sort():

array = 

quick_sort(array)
print(array)

Результат:

Поскольку алгоритм unstable (нестабилен), нет никакой гарантии, что два 19 будут всегда в этом порядке друг за другом. Хотя это ничего не значит для массива целых чисел.

Оптимизация быстрой сортировки

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

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

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

Случайная сортировка

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

Функция random() – это часть стандартной библиотеки random, которая выдает числа в случайном порядке от 0 до 1. Сортировка с использованием данного ключа выдает, кто бы мог подумать, случайный порядок:

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

Мы также научились определять наш собственный порядок сортировки, передавая функцию key функции sorted(). Наши ключевые функции могут возвращать любое значение, какое нам угодно, но зачастую нам, скорее всего, понадобится отсортировать атрибут, который принадлежит каждому элементу списка. Фактически, эта ситуация возникает настолько часто, что Python поместили функцию operator.getattr() в стандартную библиотеку, которая может генерировать ключевые функции этого типа для нас.

Python NumPy

NumPy IntroNumPy Getting StartedNumPy Creating ArraysNumPy Array IndexingNumPy Array SlicingNumPy Data TypesNumPy Copy vs ViewNumPy Array ShapeNumPy Array ReshapeNumPy Array IteratingNumPy Array JoinNumPy Array SplitNumPy Array SearchNumPy Array SortNumPy Array FilterNumPy Random
Random Intro
Data Distribution
Random Permutation
Seaborn Module
Normal Distribution
Binomial Distribution
Poisson Distribution
Uniform Distribution
Logistic Distribution
Multinomial Distribution
Exponential Distribution
Chi Square Distribution
Rayleigh Distribution
Pareto Distribution
Zipf Distribution

NumPy ufunc
ufunc Intro
ufunc Create Function
ufunc Simple Arithmetic
ufunc Rounding Decimals
ufunc Logs
ufunc Summations
ufunc Products
ufunc Differences
ufunc Finding LCM
ufunc Finding GCD
ufunc Trigonometric
ufunc Hyperbolic
ufunc Set Operations

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 имеют нулевую индексацию, как у массивов в других языках. Это означает, что первый элемент списка имеет индекс 0, второй элемент — индекс 1, третий — 2 и т. д.

Если запросить элемент по индексу за пределами списка, Python выкинет исключение .

Отрицательные индексы интерпретируются как подсчёт с конца списка.

То же действие можно воспроизвести следующим образом:

Списки в Python поддерживают слайсинг. Синтаксис слайса:  . Результатом слайса будет новый список, содержащий элементы от начала до конца — 1.

Слайсингом можно развернуть список в обратную сторону:

Использование отрицательного шага эквивалентно следующему коду:

3 Сортировка элементов коллекции

3.1 Функция sorted()

функция не меняет исходную коллекцию, а возвращает новый список из ее элементов;
не зависимо от типа исходной коллекции, вернётся список (list) ее элементов;
поскольку она не меняет исходную коллекцию, ее можно применять к неизменяемым коллекциям;
Поскольку при сортировке возвращаемых элементов нам не важно, был ли у элемента некий индекс в исходной коллекции, можно применять к неиндексированным коллекциям;
Имеет дополнительные не обязательные аргументы:reverse=True — сортировка в обратном порядкеkey=funcname (начиная с Python 2.4) — сортировка с помощью специальной функции funcname, она может быть как стандартной функцией Python, так и специально написанной вами для данной задачи функцией и лямбдой.

3.2 Функция reversed()

• возвращает генератор списка, а не сам список;
• если нужно получить не генератор, а готовый список, результат можно обернуть в list() или же вместо reversed() воспользоваться срезом ;
• она не сортирует элементы, а возвращает их в обратном порядке, то есть читает с конца списка;
• из предыдущего пункта понятно, что если у нас коллекция неиндексированная — мы не можем вывести её элементы в обратном порядке и эта функция к таким коллекциям не применима — получим «TypeError: argument to reversed() must be a sequence»;
• не позволяет использовать дополнительные аргументы — будет ошибка «TypeError: reversed() does not take keyword arguments».

3.3 Методы списка .sort() и .reverse()

• Меняют сам исходный список, а не генерируют новый;
• Возвращают None, а не новый список;
• поддерживают те же дополнительные аргументы;
• в них не надо передавать сам список первым параметром, более того, если это сделать — будет ошибка — не верное количество аргументов.

Обратите внимание:

3.4 Особенности сортировки словаря

• sorted(my_dict) — когда мы передаем в функцию сортировки словарь без вызова его дополнительных методов — идёт перебор только ключей, сортированный список ключей нам и возвращается;
• sorted(my_dict.keys()) — тот же результат, что в предыдущем примере, но прописанный более явно;
• sorted(my_dict.items()) — возвращается сортированный список кортежей (ключ, значение), сортированных по ключу;
• sorted(my_dict.values()) — возвращается сортированный список значений

сортировка словаряпо значениямlambda x: x

Приглашаю к обсуждению:

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

Всякие частности

• Для сортировки с учетом локали используйте для ключевой функции или для функции сравнения.
• Обратный параметр по-прежнему сохраняет стабильность сортировки (так что записи с одинаковыми клавишами сохраняют исходный порядок). Интересно, что этот эффект можно смоделировать без параметра, дважды используя встроенную функцию:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные функции сравнения

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

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

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

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

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

>>> student_tuples = 
>>> sorted(student_tuples, key=lambda student: student)   # sort by age

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

>>> 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_objects = 
>>> sorted(student_objects, key=lambda student: student.age)   # sort by age

Дополнительные заметки о сортировке в Python

Перед завершением статьи давайте рассмотрим, что говорит документация Python о сортировке:

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

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

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

Заключение

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

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

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

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

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

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

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

Функции в Python реализуют алгоритм Tim Sort, основанный на сортировке слиянием и сортировке вставкой.

Odd and Ends

• For locale aware sorting, use locale.strxfrm() for a key function or locale.strcoll() for a comparison function.

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

  >>> data =
  >>> assert sorted(data, reverse=True) == list(reversed(sorted(reversed(data))))

• To create a standard sort order for a class, just add the appropriate rich comparison methods:

  >>> Student.__eq__ = lambda self, other: self.age == other.age
  >>> Student.__ne__ = lambda self, other: self.age != other.age
  >>> Student.__lt__ = lambda self, other: self.age >> Student.__le__ = lambda self, other: self.age >> Student.__gt__ = lambda self, other: self.age > other.age
  >>> Student.__ge__ = lambda self, other: self.age >= other.age
  >>> sorted(student_objects)

  For general purpose comparisons, the recommended approach is to define all six rich comparison operators. The functools.total_ordering class decorator makes this easy to implement.

• Key functions need not access data internal to 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 =
  >>> newgrades = {‘john’: ‘F’, ‘jane’:’A’, ‘dave’: ‘C’}
  >>> sorted(students, key=newgrades.__getitem__)

Заключение

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

Тем не менее, несмотря на все это, средняя сложность времени 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