Sort python: 6 примеров сортировки в Python с помощью функции sorted

6 примеров сортировки в Python с помощью функции sorted

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

1. Стандартная сортировка

a = [3, 2, 5 ,4, 7, 1]
a = sorted(a)
 
print(a) # [1, 2, 3, 4, 5, 7]

Сортируем кортеж.

t = ('Zane', 'Bob', 'Janet')
t = sorted(t)
 
print(t) # ['Bob', 'Janet', 'Zane']

Сортировка словаря.

d = {1:'a', 2:'b', 3:'c'}
d = sorted(d)
print(d) # [1, 2, 3]

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

2. Сортировка сложных структур с использованием ключа

Это нормально работать с вещами, у которых по природе есть определенный порядок, вроде чисел или строк, но что делать с более сложными структурами? Здесь функция sorted() демонстрирует свое великолепие. Функция sorted() принимает ключ в качестве опционально названного параметра. Этот ключ должен быть, сам по себе, функцией, которая принимает один параметр, которая затем используется функцией sorted(), для определения значения в целях дальнейшей сортировки. Давайте взглянем на пример. Скажем, у нас есть класс Person с такими атрибутами как имя и возраст:

class Person(object):
    def __init__(self, name, age):
        self.name = name
        self.age = age
 
    def __repr__(self):
        return "" % (self.name, self.age)

(Функция __repr__ является специальной функцией, которая используется для переопределения того, как объект будет представлен в интерпретаторе Python)

Причина, по которой я определил функцию – это выделение порядка сортировки. По умолчанию, представление определенных пользователем объектов выглядит примерно так: “”. Если оставить все как есть, то отличать различные экземпляры в будущих примерах будет несколько затруднительно для нас.

Давайте сделаем список людей:

jack = Person('Jack', 19)
adam = Person('Adam', 43)
becky = Person('Becky', 11)
people = [jack, adam, becky]

Сама по себе функция sorted() не знает, что делать со списком людей:

a = sorted(people)
print(a) # [<name: Jack, age: 19>, <name: Adam, age: 43>, <name: Becky, age: 11>]

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

def byName_key(person):
    return person.name

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

a = sorted(people, key = byName_key)
print(a) # [<name: Adam, age: 43>, <name: Becky, age: 11>, <name: Jack, age: 19>]

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

Давайте взглянем на еще один код, на этот раз определяем возраст как значение для сортировки:

def byAge_key(person):
    return person.age
 
a = sorted(people, key = byAge_key)
print(a) # [<name: Becky, age: 11>, <name: Jack, age: 19>, <name: Adam, age: 43>]

3. Обратная сортировка

Функция sorted() намного упрощает сортировку в обратном порядке. Функция принимает опциональный параметр под названием reverse, который действует по строгой логике.

data = [3, 2, 5 ,4, 7, 1]
a = sorted(data, reverse = True)
print(a) # [7, 5, 4, 3, 2, 1]
 
data = ('Zane', 'Bob', 'Janet')
b = sorted(data, reverse = True)
print(b) # ['Zane', 'Janet', 'Bob']

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

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

from operator import attrgetter

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

getName = attrgetter('name')
result = getName(jack)
print(result) # 'jack'

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

result = sorted(people, key = attrgetter('name'))
print(result) # [<name: Adam, age: 43>, <name: Becky, age: 11>, <name: Jack, age: 19>]

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

result = sorted(people, key = attrgetter('age'))
print(result) # [<name: Becky, age: 11>, <name: Jack, age: 19>, <name: Adam, age: 43>]

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

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

class Snake(object):
    def __init__(self, name, toxicity, aggression):
        self.name = name
        self.toxicity = toxicity
        self.aggression = aggression
    
    def __repr__(self):
        return "" % self.name

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

Надежный сайт по продвижению doctorsmm предлагает купить подписчиков на свой Телеграмм канал по очень выгодным и притягательным ценам от 51 рубля за сотню аккаунтов. Кроме того, Вы сможете подобрать наиболее оптимальную для Вашего сообщества скорость поступления, которая доходит до 1000 единиц в сутки.

gardenSnake = Snake('gardenSnake', 10, 0.1)
rattleSnake = Snake('rattleSnake', 100, 0.25)
kingCobra = Snake('kingCobra', 50, 1.0)
snakes = [rattleSnake, kingCobra, gardenSnake]

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

def byDangerous_key(snake):
    return snake.toxicity * snake.aggression
 
result = sorted(snakes, key = byDangerous_key)
print(result) # [<gardenSnake>, <rattleSnake>, <kingCobra>]

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

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

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

from random import random
 
def randomOrder_key(element):
    return random()

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

a = sorted(snakes, key = randomOrder_key)
print(a) # [<kingCobra>, <gardenSnake>, <rattleSnake>]
 
b = sorted(snakes, key = randomOrder_key)
print(b) # [<rattleSnake>, <kingCobra>, <gardenSnake>]

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

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

Алгоритмы сортировки в Python — Еще один блог веб-разработчика

Введение

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

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

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

Пузырьковая сортировка (Bubble Sort)

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

Объяснение

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

Достигнув конца списка, повторяем этот процесс для каждого элемента снова. Хотя это крайне неэффективно. Что если в массиве нужно сделать только одну замену? Почему мы все еще повторяем, даже если список уже отсортирован? Получается нам нужно пройти список n^2 раза.

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

Откуда нам знать, что мы закончили сортировку? Если бы элементы были отсортированы, то нам не пришлось бы их менять местами. Таким образом, всякий раз, когда мы меняем элементы, мы устанавливаем флаг в True, чтобы повторить процесс сортировки. Если перестановок не произошло, флаг останется False, и алгоритм остановится.

Реализация

Мы можем реализовать пузырьковую сортировку в Python следующим образом:

def bubble_sort(nums):  
    # We set swapped to True so the loop looks runs at least once
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                # Swap the elements
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                # Set the flag to True so we'll loop again
                swapped = True


# Verify it works
random_list_of_nums = [5, 2, 1, 8, 4]  
bubble_sort(random_list_of_nums)  
print(random_list_of_nums)  

Алгоритм работает в цикле while, прерываясь только тогда, когда никакие элементы не меняются местами. Вначале мы установили для swapped значение True, чтобы алгоритм прошел по списку хотя бы один раз.

Сложность

Сложность пузырьковой сортировки в худшем случае (когда список отсортирован в обратном порядке) равна O(n^2).

Сортировка выбором (Selection Sort)

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

Объяснение

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

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

Реализация

def selection_sort(nums):  
    # значение i соответствует тому, сколько значений было отсортировано
    for i in range(len(nums)):
        # Мы предполагаем, что первый элемент несортированного сегмента является наименьшим
        lowest_value_index = i
        # Этот цикл перебирает несортированные элементы
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[lowest_value_index]:
                lowest_value_index = j
        # Поменять местами значения самого низкого несортированного элемента с первым несортированным
        nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]


# Проверяем, что это работает
random_list_of_nums = [12, 8, 3, 20, 11]  
selection_sort(random_list_of_nums)  
print(random_list_of_nums)  

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

Сложность

Сложность сортировки выбором в среднем составляет O(n^2).

Сортировка вставками (Insertion Sort)

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

Объяснение

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

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

Реализация

def insertion_sort(nums):  
    # Начнем со второго элемента, так как мы предполагаем, что первый элемент отсортирован
    for i in range(1, len(nums)):
        item_to_insert = nums[i]
        # И сохранить ссылку на индекс предыдущего элемента
        j = i - 1
        # Переместить все элементы отсортированного сегмента вперед, если они больше, чем элемент для вставки
        while j >= 0 and nums[j] > item_to_insert:
            nums[j + 1] = nums[j]
            j -= 1
        # Вставляем элемент
        nums[j + 1] = item_to_insert


# Проверяем, что это работает
random_list_of_nums = [9, 1, 15, 28, 6]  
insertion_sort(random_list_of_nums)  
print(random_list_of_nums)  

Сложность

Сложность сортировки вставками в среднем равна O(n^2).

Пирамидальная сортировка (Heap Sort) (англ. Heapsort, «Сортировка кучей») 

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

Объяснение

Мы начинаем с преобразования списка в Max Heap — бинарное дерево, где самым большим элементом является корневой узел. Затем мы помещаем этот элемент в конец списка. Затем мы восстанавливаем нашу Max Heap, которая теперь имеет на одно меньшее значение, помещая новое наибольшее значение перед последним элементом списка.

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

Реализация

Мы создаем вспомогательную функцию heapify для реализации этого алгоритма:

def heapify(nums, heap_size, root_index):  
    # Предположим, что индекс самого большого элемента является корневым индексом
    largest = root_index
    left_child = (2 * root_index) + 1
    right_child = (2 * root_index) + 2

    # Если левый потомок корня является допустимым индексом, а элемент больше
    # чем текущий самый большой элемент, то обновляем самый большой элемент
    if left_child < heap_size and nums[left_child] > nums[largest]:
        largest = left_child

    # Делайте то же самое для right_child
    if right_child < heap_size and nums[right_child] > nums[largest]:
        largest = right_child

    # Если самый большой элемент больше не является корневым элементом, меняем их местами
    if largest != root_index:
        nums[root_index], nums[largest] = nums[largest], nums[root_index]
        # Heapify the new root element to ensure it's the largest
        heapify(nums, heap_size, largest)


def heap_sort(nums):  
    n = len(nums)

    # Создаем Max Heap из списка
    # Второй аргумент означает, что мы останавливаемся на элементе перед -1, то есть на первом элементе списка.
    # Третий аргумент означает, что мы повторяем в обратном направлении, уменьшая количество i на 1
    for i in range(n, -1, -1):
        heapify(nums, n, i)

    # Перемещаем корень max hea в конец
    for i in range(n - 1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)


# Проверяем, что все работает
random_list_of_nums = [35, 12, 43, 8, 51]  
heap_sort(random_list_of_nums)  
print(random_list_of_nums)  

Сложность

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

Сортировка слиянием (Merge Sort)

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

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

Объяснение

Мы рекурсивно разделяем список пополам, пока не получим списки с одиночным размером. Затем мы объединяем каждую половину, которая была разделена, и при этом сортируя их.

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

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

Реализация

def merge(left_list, right_list):  
    sorted_list = []
    left_list_index = right_list_index = 0

    # Мы будет часто используем длины списков, поэтому удобно сразу создавать переменные для этого
    left_list_length, right_list_length = len(left_list), len(right_list)

    for _ in range(left_list_length + right_list_length):
        if left_list_index < left_list_length and right_list_index < right_list_length:
            # Мы проверяем, какое значение с начала каждого списка меньше
            # Если элемент в начале левого списка меньше, добавляем его в отсортированный список
            if left_list[left_list_index] <= right_list[right_list_index]:
                sorted_list.append(left_list[left_list_index])
                left_list_index += 1
            # Если элемент в начале правого списка меньше, добавляем его в отсортированный список
            else:
                sorted_list.append(right_list[right_list_index])
                right_list_index += 1

        # Если мы достигли конца левого списка, добавляем элементы из правого списка
        elif left_list_index == left_list_length:
            sorted_list.append(right_list[right_list_index])
            right_list_index += 1
        # Если мы достигли конца правого списка, добавляем элементы из левого списка
        elif right_list_index == right_list_length:
            sorted_list.append(left_list[left_list_index])
            left_list_index += 1

    return sorted_list


def merge_sort(nums):  
    # Если список представляет собой один элемент, возвращаем его
    if len(nums) <= 1:
        return nums

    # Используем деление с округленим по наименьшему целому для получения средней точки, индексы должны быть целыми числами 
    mid = len(nums) // 2

    # Сортируем и объединяем каждую половину
    left_list = merge_sort(nums[:mid])
    right_list = merge_sort(nums[mid:])

    # Объединить отсортированные списки в новый
    return merge(left_list, right_list)


# Проверяем, что все работает
random_list_of_nums = [120, 45, 68, 250, 176]  
random_list_of_nums = merge_sort(random_list_of_nums)  
print(random_list_of_nums)  

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

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

Сложность

В среднем сложность сортировки слиянием составляет O(nlog (n)).

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

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

Объяснение

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

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

Реализация

# Есть разные способы реализовать быструю сортировки
# мы выбрали схема Tony Hoare
def partition(nums, low, high):  
    # Мы выбираем средний элемент, в качестве опорного. Некоторые реализации выбирают
    # первый элемент или последний элемент или вообще случайный элемент.
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums[i] < pivot:
            i += 1

        j -= 1
        while nums[j] > pivot:
            j -= 1

        if i >= j:
            return j

        # Если элемент в i (слева от оси) больше, чем
        # элемент в J (справа от оси), то поменять их местами
        nums[i], nums[j] = nums[j], nums[i]


def quick_sort(nums):  
    # Создаем вспомогательную рекурсивную функцию
    def _quick_sort(items, low, high):
        if low < high:
            # Это индекс после опорного элемента, по которому наши списки разделены
            split_index = partition(items, low, high)
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)

    _quick_sort(nums, 0, len(nums) - 1)


# Проверяем, что все работает
random_list_of_nums = [22, 5, 1, 18, 99]  
quick_sort(random_list_of_nums)  
print(random_list_of_nums)  

Сложность

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

Примечание. Алгоритм быстрой сортировки будет работать медленно, если опорный элемент будет наименьшим или наибольшим элементом списка. Быстрая сортировка обычно работает быстрее с более сбалансированными значениями. В отличие от сортировки кучи и сортировки слиянием, обе из которых имеют худшие времена O(nlog (n)), быстрая сортировка имеет худшее время O(n^2).

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

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

Создадим новый список, чтобы отсортировать его содержимое с помощью метода sort():

apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2]  
apples_eaten_a_day.sort()  
print(apples_eaten_a_day) # [1, 1, 1, 2, 2, 2, 3]  

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

apples_eaten_a_day_2 = [2, 1, 1, 3, 1, 2, 2]  
sorted_apples = sorted(apples_eaten_a_day_2)  
print(sorted_apples) # [1, 1, 1, 2, 2, 2, 3]  

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

# Reverse sort the list in-place
apples_eaten_a_day.sort(reverse=True)  
print(apples_eaten_a_day) # [3, 2, 2, 2, 1, 1, 1]

# Reverse sort to get a new list
sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True)  
print(sorted_apples_desc) # [3, 2, 2, 2, 1, 1, 1]  

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

Встроенная функция сортировки реализуют алгоритм сортировки Тима. Этот алгоритм, основан на сортировке слиянием и сортировке вставкой.

Сравнение скорости

Чтобы понять, как быстро работают рассмотренные алгоритмы, мы сгенерируем список из 5000 чисел от 0 до 1000. Затем мы определим время, необходимое для завершения каждого алгоритма. Повторим это 10 раз, чтобы мы могли более надежно установить производительность сортировки.

Вот какие результаты мы получили, время в секундах:

Вы можете получить другие значения, если попробуете повторить тест самостоятельно, но общее соотношение должно быть одинаковым или похожим. Пузырьковая сортировка (Bubble Sort) — самая медленная и наихудшая из всех алгоритмов. Хотя она очень полезно в качестве введения в изучения алгоритмов сортировки, оно не подходит для практического использования.

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

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

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

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

Заключение

Алгоритмы сортировки дают нам много способов упорядочить наши данные. Мы рассмотрели 6 различных алгоритмов — Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort — и их реализации в Python.

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

Оригинальная статья: Marcus Sanatan Sorting Algorithms in Python

Была ли вам полезна эта статья?

[7 / 4.4]

Сортировка списка в Python | ИТ Блог. Администрирование серверов на основе Linux (Ubuntu, Debian, CentOS, openSUSE)

Сортировка данных – одна из самых распространенных задач при работе с Python. Например, вы можете отсортировать список членов команды по имени или список проектов в порядке приоритета.

В этой статье описывается, как сортировать списки в Python.

Sort() и sorted() в Python

В Python вы можете отсортировать список, используя встроенный метод list.sort() или встроенную функцию sorted().

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

Синтаксис sort()и sorted()следующий:

list.sort(key=function, reverse=Boolean)

sorted(iterable, key=function, reverse=Boolean)

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

• key – Функция, которая принимает один аргумент и преобразует его перед сравнением. Функция должна возвращать одно значение, которое используется для сравнения сортировки.
• reverse – Значение реверса может быть либо либо, True либо False. Значением по умолчанию является True. Когда для этого аргумента установлено значение false, список сортируется в обратном порядке.

Элементы списка сравниваются с помощью оператора < (меньше чем) и сортируются по возрастанию. Оператор < не поддерживает сравнения строки в целое число, так что если у вас есть список , содержащие строки и целые числа, то операция сортировки не удастся.

В следующем примере показано, как отсортировать список строк в алфавитном порядке:

directions = ["north", "east", "south", "west"] 

directions.sort()

print('Sorted list:', directions)

Sorted list: ['east', 'north', 'south', 'west']

Если вы хотите сохранить исходный список без изменений, используйте функцию sorted():

directions = ["north", "east", "south", "west"] 

sorted_directions = sorted(directions)

print('Sorted list:', sorted_directions)

Sorted list: ['east', 'north', 'south', 'west']

Чтобы отсортировать список в обратном (нисходящем) порядке, установите аргумент reverse в True:

directions = ["north", "east", "south", "west"] 

directions.sort(reverse=True)

print('Sorted list:', directions)

Sorted list: ['west', 'south', 'north', 'east']

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

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

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

directions = ["Destroyer", "Alex", "AndreyEx", "Max"] 

directions.sort(key=len)

print('Sorted list:', directions)

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

Sorted list: ['AndreyEx', 'Destroyer', 'Max', 'Alex']

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

def sum_digits(num): 
    digits = [int(x) for x in str(num)] 
    return sum(digits) 
      
numbers = [23, 77, 19, 310, 219] 

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

print('Sorted list:', numbers)

Sorted list: [77, 219, 19, 23, 310]

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

numbers = [(3, 14), (1, 61), (2, 71)]

numbers.sort(key=lambda k: k[0])

print('Sorted list:', numbers)

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

Sorted list: [(1, 61), (2, 71), (3, 14)]

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

elements = [
    {'name': 'Germanium', 'number': 25, 'symbol': 'ge'},
    {'name': 'Silver', 'number': 47, 'symbol': 'ag'},
    {'name': 'Iron', 'number': 26, 'symbol': 'fe'},
]

elements.sort(key=lambda k: k['name'])

print('Sorted list:', elements)

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

Sorted list: [
    {'name': 'Germanium', 'number': 25, 'symbol': 'ge'}, 
    {'name': 'Iron', 'number': 26, 'symbol': 'fe'}, 
    {'name': 'Silver', 'number': 47, 'symbol': 'ag'}
]

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

from operator import itemgetter

elements = [
    {'name': 'Germanium', 'number': 25, 'symbol': 'ge'},
    {'name': 'Silver', 'number': 47, 'symbol': 'ag'},
    {'name': 'Iron', 'number': 26, 'symbol': 'fe'},
]

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

print('Sorted list:', elements)

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

Sorted list: [
    {'name': 'Silver', 'number': 47, 'symbol': 'ag'},
    {'name': 'Iron', 'number': 26, 'symbol': 'fe'},
    {'name': 'Germanium', 'number': 25, 'symbol': 'ge'}
]

Вывод

Мы показали вам, как сортировать списки в Python, используя метод sort() и функцию sorted().

Если у вас есть какие-либо вопросы или отзывы, не стесняйтесь оставлять комментарии.

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Быстрая сортировка в Python | GeekBrains

Идея быстрой сортировки была придумана информатиком Чарльзом Хоаром в 1960 году. Рассмотрим её преимущества над пузырьковой сортировкой и реализуем алгоритм в Python.

https://d2xzmw6cctk25h.cloudfront.net/post/1333/og_cover_image/dd0558fd43db6b489f3263dbad1e57ef

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

nums = [4, 1, 6, 3, 2, 7, 8]
n = 1
while n < len(nums):
   for i in range(len(nums) - n):
       if nums[i] > nums[i + 1]:
           nums[i], nums[i + 1] = nums[i + 1], nums[i]
   n += 1

Однако на практике он неэффективен, так как предполагает многократное прохождение по всему массиву. Альтернативный метод, впоследствии получивший название «быстрая сортировка», изобрел информатик Чарльз Хоар в 1960. Он предполагает деление массива на две части, в одной из которых находятся элементы меньше определённого значения, в другой – больше или равные.  Рассмотрим реализацию в Python быстрой сортировки Хоара.

def quicksort(nums):
   if len(nums) <= 1:
       return nums
   else:
       q = random.choice(nums)
       s_nums = []
       m_nums = []
       e_nums = []
       for n in nums:
           if n < q:
               s_nums.append(n)
           elif n > q:
               m_nums.append(n)
           else:
               e_nums.append(n)
       return quicksort(s_nums) + e_nums + quicksort(m_nums)

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

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

def quicksort(nums, fst, lst):
   if fst >= lst: return
 
   i, j = fst, lst
   pivot = nums[random.randint(fst, lst)]
 
   while i <= j:
       while nums[i] < pivot: i += 1
       while nums[j] > pivot: j -= 1
       if i <= j:
           nums[i], nums[j] = nums[j], nums[i]
           i, j = i + 1, j - 1
   quicksort(nums, fst, j)
   quicksort(nums, i, lst)

В этом случае вы используете память только для организации рекурсии и в Python быстрая сортировка становится по-настоящему «быстрой». В заключении темы опишем на питоне сортировку Хоара в функциональном виде:

def quicksort(nums):
   if len(nums) <= 1:
       return nums
   else:
       q = random.choice(nums)
   l_nums = [n for n in nums if n < q]
 
   e_nums = [q] * nums.count(q)
   b_nums = [n for n in nums if n > q]
   return quicksort(l_nums) + e_nums + quicksort(b_nums)

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

Функция Sorted () в Python

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

Синтаксис: отсортированный (повторяемый, ключ, обратный)

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

• Итерируемый: последовательность (список, кортеж, строка) или коллекция (словарь, набор, frozenset) или любой другой итератор, который нужно отсортировать.
• Ключ (необязательно): функция, которая будет служить сервером в качестве ключа или основы сравнения сортировки.
• Обратное (необязательно): если установлено значение true, то итерация будет отсортирована в обратном (нисходящем) порядке, по умолчанию она установлена в значение false.

Пример 1

Output :
Sorted List returned : [1, 2, 3, 4, 6, 7, 8]

Reverse sort : [8, 7, 6, 4, 3, 2, 1]

Original list not modified : [2, 8, 1, 4, 6, 3, 7]

Пример 2: сортировка разных типов данных

Output :
['e', 'q', 'r', 't', 'w', 'y']
['e', 'q', 'r', 't', 'w', 'y']
['h', 'n', 'o', 'p', 't', 'y']
['e', 'q', 'r', 't', 'w', 'y']
['e', 'q', 'r', 't', 'w', 'y']
['e', 'q', 'r', 't', 'w', 'y']

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

Например, если мы передаем список строк в sorted (), он сортируется по алфавиту. Но если мы укажем key = len, т.е. дадим функцию len в качестве ключа, то строки будут переданы len, и значение, которое он возвращает, т.е. длина строк будет отсортирована. Это означает, что строки будут отсортированы по длине вместо

Output :
Normal sort : ['aaa', 'b', 'cccc', 'dd']
Sort with len : ['b', 'dd', 'aaa', 'cccc']

Ключ также принимает пользовательские функции в качестве значения для сортировки.

Output :
Normal sort : [3, 7, 11, 15]
Sorted with key: [7, 15, 3, 11]

Эта статья предоставлена Харшитом Агравалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи [email protected]. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Функция Sorted () в Python

0.00 (0%) 0 votes

Быстрая сортировка в Python — Еще один блог веб-разработчика

Введение

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

Спонсор поста Онлайн-курс по алгоритмам на Python

Курс по алгоритмам и структурам данных на Python для новичков. Видео-уроки, домашние задания, поддержка. На курсе вы изучите следующие темы:
– Структуры данных, сортировка и поиск.
– Рекурсия, деревья, сжатие информации.
– Криптография и и блокчейн.

С 2019 года курс «читается» студентам Московского университета экономики и права им. Витте
на специальностях «Прикладная информатика» и «Бизнес-информатика».

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

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

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

Базовая версия алгоритма делает следующее:

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

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

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

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

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

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

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

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

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

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

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

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 (правая сторона). И так далее.

Реализация

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

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

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

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

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    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 = [29,19,47,11,6,19,24,12,17,23,11,71,41,36,71,13,18,32,26]

quick_sort(array)
print(array)

Результат:

[6, 11, 11, 12, 13, 17, 18, 19, 19, 23, 24, 26, 29, 32, 36, 41, 47, 71, 71]

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

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

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

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

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

Заключение

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

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

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

Была ли вам полезна эта статья?

[4 / 2.5]

Python: как отсортировать список? (Правильный путь)

Это происходит постоянно.

У вас есть список Python, и вы хотите отсортировать содержащиеся в нем элементы.

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

Разница между sort и sorted заключается в том, что sort — это метод списка, который изменяет список на месте, тогда как sorted — это встроенная функция, которая создает новый список, не касаясь исходного.

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

Я также научу вас определять свои собственные функции сортировки.

Прочтите всю статью, если хотите узнать все о сортировке списков в Python. В противном случае смело переходите прямо к конкретному разделу.

Сортировка списка чисел

Сортировка числового списка в Python — это несложно.

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

Вот пример:

  >>> L = [15, 22.4, 8, 10, 3.14]
>>> L.sort ()
>>> L
[3.14, 8, 10, 15, 22.4]  

Обратите внимание, что список L был отсортирован по месту. Новые объекты не создавались.

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

  >>> L = [15, 22.4, 8, 10, 3.14]
>>> sorted_list = отсортировано (L)
>>> L
[15, 22.4, 8, 10, 3.14]
>>> отсортированный_лист
[3.14, 8, 10, 15, 22.4]  

Как вы можете заметить, и sort и по умолчанию сортируют элементы в порядке возрастания.

Если вы хотите отсортировать в порядке убывания, все, что вам нужно сделать, это добавить параметр reverse = True либо к функциям sort или sorted .

Они оба принимают это!

Вот еще один пример, показывающий, как можно использовать метод sort по убыванию.

  >>> L = [15, 22,4, 8, 10, 3,14]
>>> L.sort (reverse = True)
>>> L
[22.4, 15, 10, 8, 3.14]  

Теперь давайте посмотрим, как сортировать список строк.

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

Так что, если вы хотите отсортировать список строк вместо чисел?

Ну, особо ничего не меняется.

Вы по-прежнему можете использовать sort или sorted .

Вот пример использования sort :

  >>> L = ["апельсины", "яблоки", "бананы"]
>>> Л.Сортировать()
>>> L
['яблоки', 'бананы', 'апельсины']  

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

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

  >>> L = ["апельсины", "яблоки", "бананы"]
>>> отсортировано (L, обратный = True)
['апельсины', 'бананы', 'яблоки']  

Пока все хорошо, но есть загвоздка.

Давайте посмотрим, что происходит, когда существуют прописные буквы.

  >>> L = ["апельсины", "яблоки", "бананы"]
>>> L.sort ()
>>> L
[«Бананы», «яблоки», «апельсины»]  

Это интересно. Бананы появляются перед яблоками

Причина этого в том, что Python рассматривает все прописные буквы как более низкие, чем строчные.

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

Однако в большинстве случаев вы хотите обрабатывать строки как без учета регистра , когда дело доходит до сортировки.

Итак, как можно отсортировать список строк без учета регистра?

Начиная с Python 2.4, как sort , так и sorted добавили необязательный ключевой параметр.

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

Это действительно очень полезно, потому что теперь мы можем передать str.lower в качестве параметра key в функцию sort .

И это даст указание функции sort выполнять сравнения между строчными версиями строк, что нам и нужно!

  >>> L = ["апельсины", "яблоки", "бананы"]
>>> Л.sort (key = str.lower)
>>> L
['яблоки', 'Бананы', 'апельсины']  

Как видите, теперь сортировка нечувствительна к регистру.

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

Сортировка списка кортежей

Прежде чем мы углубимся, давайте посмотрим, как Python сравнивает два кортежа.

Кортежи сравниваются поэлементно, начиная с первого элемента, что очень похоже на сравнение строк.

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

Если они равны, сравниваются вторые элементы и так далее.

  >>> (2, 4) <(4, 1)
Правда
>>> (2, 4) <(2, 6)
True  

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

  >>> отсортировано ([(5, 4), (3, 3), (3, 10)])
[(3, 3), (3, 10), (5, 4)]  

Но иногда это не совсем то, что вам нужно.

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

И мы хотим отсортировать этот список кортежей по возрасту.

как можно отсортировать список кортежей по второму элементу?

Ключевой параметр снова придет на помощь.

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

  def custom_sort (t):
    вернуть t [1]

L = [("Алиса", 25), ("Боб", 20), ("Алекс", 5)]
Л.sort (ключ = custom_sort)
печать (L)

# выход
# [('Alex', 5), ('Bob', 20), ('Alice', 25)]  

Вот и все!

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

  L = [("Алиса", 25), ("Боб", 20), ("Алекс", 5)]
L.sort (ключ = лямбда x: x [1])
печать (L)
# выход
# [('Alex', 5), ('Bob', 20), ('Alice', 25)]  

Сортировка списка объектов

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

Ключевой параметр - ваш друг.

Возьмем пример.

Предположим, у вас есть класс User, который выглядит так:

  class User:
    def __init __ (я, имя, возраст):
        self.name = имя
        self.age = age  

Простой класс с атрибутами name и age.

Давайте создадим несколько объектов User и добавим их в список.

  Боб = Пользователь ("Боб", 20)
Алиса = Пользователь ('Алиса', 30)
Лев = Пользователь ('Лев', 15)
L = [Боб, Алиса, Лео]  

Теперь предположим, что вы хотите отсортировать объекты в этом списке в алфавитном порядке по атрибуту имени.

Вот один из способов сделать это:

  L.sort (key = lambda x: x.name)
print ([имя элемента для элемента в L])
# output: ['Alice', 'Bob', 'Leo']  

Если вы хотите отсортировать объекты на основе атрибута возраста, вам нужно сделать следующее:

  L.sort (key = лямбда x: x.age)
print ([имя элемента для элемента в L])
# output: ['Leo', 'Bob', 'Alice']  

И точно так же вы можете определить любую настраиваемую сортировку для любого объекта python, о котором вы только можете подумать.

Удачной сортировки! 🙂

Изучение Python?

Загляните в раздел Курсы!

Избранные сообщения

Вы начинаете карьеру программиста?

Я предлагаю свои лучшие материалы для новичков в информационном бюллетене.

• Советы по Python для начинающих, среднего и продвинутого уровней.
• CS Советы и рекомендации по карьере.
• Специальные скидки на мои премиальные курсы при их запуске.

И многое другое…

Подпишитесь сейчас.Это бесплатно.

.

Python отсортировано ()

Функция sorted () сортирует элементы заданной итерации в определенном порядке ( по возрастанию или по убыванию ) и возвращает отсортированную итерацию в виде списка.

Синтаксис функции sorted () :

отсортировано (итерация, ключ = Нет, обратный = Ложь) 

Параметры для функции sorted ()

sorted () может принимать максимум три параметра:

• iterable - Последовательность (строка, кортеж, список) или коллекция (набор, словарь, замороженный набор) или любой другой итератор.
• в обратном направлении (необязательно) - Если True , отсортированный список переворачивается (или сортируется в порядке убывания). По умолчанию . Ложь , если не указано.
• ключ (необязательно) - функция, которая служит ключом для сравнения сортировки. По умолчанию Нет .

Пример 1. Сортировка строки, списка и кортежа

  # список гласных
py_list = ['e', 'a', 'u', 'o', 'i']
печать (отсортировано (py_list))

# строка
py_string = 'Python'
печать (отсортировано (py_string))

Кортеж # гласных
py_tuple = ('е', 'а', 'и', 'о', 'я')
печать (отсортировано (py_tuple))  

Выход

  ['a', 'e', ​​'i', 'o', 'u']
['P', 'h', 'n', 'o', 't', 'y']
['a', 'e', ​​'i', 'o', 'u']  

Обратите внимание, что во всех случаях возвращается отсортированный список.

Примечание: В списке также есть метод sort (), который работает так же, как sorted () . Единственное отличие состоит в том, что метод sort () не возвращает никакого значения и изменяет исходный список.

Пример 2: Сортировка по убыванию

Функция sorted () принимает параметр reverse в качестве необязательного аргумента.

Настройка reverse = True сортирует итерацию в порядке убывания.

  # набор
py_set = {'e', 'a', 'u', 'o', 'i'}
печать (отсортировано (py_set, reverse = True))

# Словарь
py_dict = {'e': 1, 'a': 2, 'u': 3, 'o': 4, 'i': 5}
печать (отсортировано (py_dict, reverse = True))

# замороженный набор
Frozenset (('е', 'а', 'и', 'о', 'я'))
print (sorted (frozen_set, reverse = True))  

Выход

  ['u', 'o', 'i', 'e', ​​'a']
['u', 'o', 'i', 'e', ​​'a']
['u', 'o', 'i', 'e', ​​'a']  

key Параметр в функции Python sorted ()

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

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

отсортировано (итерация, ключ = len) 

Здесь len () - это встроенная функция Python для подсчета длины объекта.

Список сортируется по длине элемента от наименьшего количества к наибольшему.

Пример 3: Сортировка списка с помощью sorted () с ключевой функцией

  # берем второй элемент для сортировки
def take_second (elem):
    вернуть элемент [1]


# случайный список
random = [(2, 2), (3, 4), (4, 1), (1, 3)]

# сортировать список с ключом
sorted_list = sorted (случайный, ключ = take_second)

# распечатать список
print ('Отсортированный список:', sorted_list)  

Выход

  Отсортированный список: [(4, 1), (2, 2), (1, 3), (3, 4)]  

Пример 4: Сортировка с использованием нескольких ключей

Допустим, у нас есть следующий список:

  # Вложенный список информации об учащемся в научной олимпиаде
# Элементы списка: (Имя студента, оценки из 100, возраст)

members_list = [
    ('Элисон', 50, 18),
    ('Теренс', 75, 12),
    ('Давид', 75, 20),
    ('Джимми', 90, 22),
    ('Джон', 45, 12)
]  

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

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

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

  >>> (1,3)> (1, 4)
Ложь
>>> (1, 4) <(2,2)
Правда
>>> (1, 4, 1) <(2, 1)
Правда  

Давайте воспользуемся этой логикой для построения нашей логики сортировки.

  # Вложенный список информации об учащемся в научной олимпиаде
# Элементы списка: (Имя студента, оценки из 100, возраст)
members_list = [
    ('Элисон', 50, 18),
    ('Теренс', 75, 12),
    ('Давид', 75, 20),
    ('Джимми', 90, 22),
    ('Джон', 45, 12)
]


def sorter (элемент):
    # Поскольку сначала самые высокие оценки, наименьшая ошибка = наибольшее количество оценок
    error = 100 - элемент [1]
    возраст = элемент [2]
    возврат (ошибка, возраст)


sorted_list = отсортированный (список участников, ключ = сортировщик)
print (sorted_list)  

Выход

  [('Джимми', 90, 22), ('Теренс', 75, 12), ('Дэвид', 75, 20), ('Элисон', 50, 18), ('Джон', 45, 12 )]  

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

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

  # Вложенный список информации об учащемся в научной олимпиаде
# Элементы списка: (Имя студента, оценки из 100, возраст)
members_list = [
    ('Элисон', 50, 18),
    ('Теренс', 75, 12),
    ('Давид', 75, 20),
    ('Джимми', 90, 22),
    ('Джон', 45, 12)
]

sorted_list = sorted (список участников, ключ = лямбда-элемент: (100-элемент [1], элемент [2]))
print (sorted_list)  

Выход

  [('Джимми', 90, 22), ('Теренс', 75, 12), ('Дэвид', 75, 20), ('Элисон', 50, 18), ('Джон', 45, 12 )]  

Чтобы узнать больше о лямбда-функциях, посетите Python Lambda Functions.

.