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

Пирамидальная сортировка

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

Алгоритм

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

Этот процесс построения кучи повторяется, пока все вершины дерева не будут удалены.

Реализация

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

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 > nums:
        largest = left_child

    # То же самое для правого потомка корня
    if right_child < heap_size and nums > nums:
        largest = right_child

    # Если наибольший элемент больше не корневой, они меняются местами
    if largest != root_index:
        nums, nums = nums, nums
        # 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, т.е.
    # перед первым элементом списка
    # 3-й аргумент означает повторный проход по списку в обратном направлении, 
    # уменьшая счётчик i на 1 
    for i in range(n, -1, -1):
        heapify(nums, n, i)

    # Перемещаем корень Max Heap в конец списка
    for i in range(n - 1, 0, -1):
        nums, nums = nums, nums
        heapify(nums, i, 0)

# Проверяем, что оно работает
random_list_of_nums =   
heap_sort(random_list_of_nums)  
print(random_list_of_nums)

5.1.4. Анонимные функции¶

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

lambda

lambda parameters expression

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

• выражение не может содержать условных инструкций или циклов (условные выражения — допустимы), а также не может содержать инструкцию ;

• результатом лямбда-выражения является анонимная функция.

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

Пример записи лямбда-функции приведен в Листинге 5.1.15.

Пользовательская логика для сортировки списка

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

В последнем примере мы использовали возраст как ключевой элемент для сортировки нашего списка.

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

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

Итак, нам нужно импортировать библиотеку под названием functools. Мы будем использовать функцию cmp_to_key(), чтобы преобразовать compare_function в key.

import functools


def compare_function(person_a, person_b):
    if person_a == person_b:  # if their gender become same
        return person_a - person_b  # return True if person_a is younger
    else:  # if their gender not matched
        if person_b == 'F':  # give person_b first priority if she is female
            return 1
        else:  # otherwise give person_a first priority
            return -1

persons = , , , ]

print(f'Before sorting: {persons}')

persons.sort(key=functools.cmp_to_key(compare_function))

print(f'After sorting: {persons}')

Вывод:

Before sorting: , , , ]
After sorting: , , , ]

Список сначала сортируется по полу. Затем он сортируется по возрасту людей.

ФОРМЫ

Форма входаФорма регистрацииФорма оформления заказаКонтактная формаФорма входа в соц сетиРегистрацияФорма с иконкамиРассылка по почтеСложенная формаАдаптивная формаФорма всплывающаяФорма линейнаяОчистить поле вводаКопирование текста в буфер обменаАнимированный поискКнопка поискаПолноэкранный поискПоле ввода в менюФорма входа в менюПользовательский флажок/радиоПользовательский выборТумблер перключательУстановить флажокОпределить Caps LockКнопка запуска на EnterПроверка пароляПереключение видимости пароляМногоступенчатая формаФункция автозаполнения

Сортировка методом пузырька

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

Алгоритм сортировки пузырьком:

• нерекурсивный;
• устойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(n2);

def bubbleSort(array):
    swapped = False
    for i in range(len(array)-1,0,-1):
        for j in range(i):
            if array>array:
                array, array = array, array
                swapped= True
        if swapped:
            swapped=False
        else:
            break
    return array

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.

Концепция сортировки вставкой

Массив разделился практически на две части при сортировке вставками – несортированная часть и отсортированная часть.

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

Он фокусируется на вставке элементов путем перемещения всех элементов, если правое значение меньше левого.

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

Ниже приведен алгоритм сортировки массива с помощью вставки.

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

Разберемся в следующем примере.

Рассмотрим первый элемент отсортированного массива.

Первый шаг к добавлению 10 в отсортированный подмассив.

Теперь берем первый элемент из несортированного массива – 4. Это значение сохраняем в новой переменной temp. Теперь мы видим, что 10> 4, перемещаем 10 вправо, и это перезаписывает 4, которые были ранее сохранены.

(темп = 4)

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

У нас есть два элемента в отсортированном подмассиве.

Теперь проверьте число 25. Мы сохранили его во временной переменной. 25> 10, а также 25> 4, затем мы помещаем его в третью позицию и добавляем в отсортированный подмассив.

Снова проверяем цифру 1. Сохраняем в темп. 1 меньше 25. Он перезаписывает 25.

10> 1, затем перезаписывается снова

4> 1 теперь ставим значение temp = 1

Теперь у нас есть 4 элемента в отсортированном подмассиве. 5 <25, затем сместите 25 в правую сторону и передайте temp = 5 в левую сторону.

положите temp = 5

Теперь мы получаем отсортированный массив, просто помещая временное значение.

Данный массив отсортирован.

sorted() With a key Argument

One of the most powerful components of is the keyword argument called . This argument expects a function to be passed to it, and that function will be used on each value in the list being sorted to determine the resulting order.

To demonstrate a basic example, let’s assume the requirement for ordering a specific list is the length of the strings in the list, shortest to longest. The function to return the length of a string, , will be used with the argument:

>>>

The resulting order is a list with a string order of shortest to longest. The length of each element in the list is determined by and then returned in ascending order.

Let’s return to the earlier example of sorting by first letter when the case is different. can be used to solve that problem by converting the entire string to lowercase:

>>>

The output values have not been converted to lowercase because does not manipulate the data in the original list. During sorting, the function passed to is being called on each element to determine sort order, but the original values will be in the output.

There are two main limitations when you’re using functions with the argument.

First, the number of required arguments in the function passed to must be one.

The example below shows the definition of an addition function that takes two arguments. When that function is used in on a list of numbers, it fails because it is missing a second argument. Each time is called during the sort, it is only receiving one element from the list at a time:

>>>

The second limitation is that the function used with must be able to handle all the values in the iterable. For example, you have a list of numbers represented as strings to be used in , and is going to attempt to convert them to numbers using . If a value in the iterable can’t be cast to an integer, then the function will fail:

>>>

Each numeric value as a can be converted to , but can’t. This causes a to be raised and explain that can’t be converted to because it is invalid.

The functionality is extremely powerful because almost any function, built-in or user-defined, can be used to manipulate the output order.

If the ordering requirement is to order an iterable by the last letter in each string (and if the letter is the same, then to use the next letter), then a function can be defined and then used in the sorting. The example below defines a function that reverses the string passed to it, and then that function is used as the argument for :

>>>

The slice syntax is used to reverse a string. Each element will have applied to it, and the sorting order will be based on the characters in the backwards word.

Instead of writing a standalone function, you can use a function defined in the argument.

A is an anonymous function that:

1. Must be defined inline
2. Doesn’t have a name
3. Can’t contain statements
4. Will execute just like a function

In the example below, the is defined as a with no name, the argument taken by the is , and is the operation that will be performed on the argument:

>>>

is called on each element and reverses the word. That reversed output is then used for sorting, but the original words are still returned.

If the requirement changes, and the order should be reversed as well, then the keyword can be used alongside the argument:

>>>

functions are also useful when you need to sort objects based on a property. If you have a group of students and need to sort them by their final grade, highest to lowest, then a can be used to get the property from the :

>>>

This example uses to produce classes with and attributes. The calls on each element and returns the value for .

is set to to make the ascending output flipped to be descending so that the highest grades are ordered first.

The possibilities are endless for how ordering can be done when you leverage both the and keyword arguments on . Code can be kept clean and short when you use a basic for a small function, or you can write a whole new function, import it, and use it in the key argument.

Python sort list of namedtuples

In the next example, we sort namedtuples.

namedtuple_sort.py

#!/usr/bin/env python3

from typing import NamedTuple


class City(NamedTuple):
    id: int
    name: str
    population: int


c1 = City(1, 'Bratislava', 432000)
c2 = City(2, 'Budapest', 1759000)
c3 = City(3, 'Prague', 1280000)
c4 = City(4, 'Warsaw', 1748000)
c5 = City(5, 'Los Angeles', 3971000)
c6 = City(6, 'Edinburgh', 464000)
c7 = City(7, 'Berlin', 3671000)

cities = 

cities.sort(key=lambda e: e.name)

for city in cities:
    print(city)

The namedtuple has three attributes: ,
, and . The example sorts the
namedtuples by their names.

cities.sort(key=lambda e: e.name)

The anonymous function returns the name property of the namedtuple.

$ ./namedtuple_sort.py 
City(id=7, name='Berlin', population=3671000)
City(id=1, name='Bratislava', population=432000)
City(id=2, name='Budapest', population=1759000)
City(id=6, name='Edinburgh', population=464000)
City(id=5, name='Los Angeles', population=3971000)
City(id=3, name='Prague', population=1280000)
City(id=4, name='Warsaw', population=1748000)

This is the output.

Сортировать с помощью настраиваемой функции с помощью клавиши

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

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

list.sort(key=len)

В качестве альтернативы для сортировки:

sorted(list, key=len)

Здесь len ‒ это встроенная функция Python для подсчета длины элемента.

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

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

Python sort list of grades

There are various grading systems around the world. Our example contains
grades such as A+ or C- and these cannot be ordered lexicographically. We use
a dictionary where each grade has its given value.

grades.py

#!/usr/bin/env python3


data = 'A+ A A- B+ B B- C+ C C- D+ D'
grades = { grade: idx for idx, grade in enumerate(data.split()) } 

def mc(e):
    return grades.get(e)

students = 

print(grades)

students.sort(key=mc)
print(students)


# from operator import itemgetter
# students.sort(key=lambda e: itemgetter(e)(grades))

We have a list of students. Each student has a name and a grade in a nested
tuple.

data = 'A+ A A- B+ B B- C+ C C- D+ D'
grades = { grade: idx for idx, grade in enumerate(data.split()) } 

We build the dictionary of grades. Each grade has its value. The grades will
be sorted by their dictionary value.

def mc(e):
    return grades.get(e)

The key function simply returns the value of the grade.

# from operator import itemgetter
# students.sort(key=lambda e: itemgetter(e)(grades))

This solution uses an anonymous function.

$ ./grades.py 
{'A+': 0, 'A': 1, 'A-': 2, 'B+': 3, 'B': 4, 'B-': 5, 'C+': 6, 'C': 7, 'C-': 8, 'D+': 9, 'D': 10}

This is the output.

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

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

Алгоритм

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

Реализация

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

def partition(nums, low, high):  
    # Выбираем средний элемент в качестве опорного
    # Также возможен выбор первого, последнего
    # или произвольного элементов в качестве опорного
    pivot = nums[(low + high) // 2]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums < pivot:
            i += 1

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

        if i >= j:
            return j

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

def quick_sort(nums):  
    # Создадим вспомогательную функцию, которая вызывается рекурсивно
    def _quick_sort(items, low, high):
        if low < high:
            # This is the index after the pivot, where our lists are split
            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 =   
quick_sort(random_list_of_nums)  
print(random_list_of_nums) 

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

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

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

Пример 1. Сортировка списка чисел в формате строковых данных

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

Зададим список из 6 элементов. Лямбду будем использовать внутри функции для сортировки списка.

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

n_list = 
# Sort the list using lambda and sorted function
sorted_list = sorted(n_list, key=lambda x: int(x))
# Print the sorted list
print("The list of the sorted values are:")
for value in sorted_list:
    print(value, end=' ')

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

The list of the sorted values are:
1 5 11 19 37 50 

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:

Техника 1: Использование функции сортировки () для сортировки словаря по значению в Python

вместе с Python Может использоваться для сортировки словаря по значению в Python.

Модуль оператора Python имеет различные встроенные функции для манипулирования данными и значениями. Метод OPERADE.ITEMGETTER (M) учитывает входной объект в качестве итогеровке и извлекивает все значения «M» из потенциала.

Синтаксис: Python Operator.itemgetter (M)

operator.itemgetter(value)

Scorted () Python Sorted () сортирует DICT в порядке возрастания/убывания.

Синтаксис: Python Sorted () Метод

sorted(iterable, key)

• : Это представляет элементы, которые будут отсортированы.
• (Необязательно): функция для решения порядка сортировки элементов.

Пример:

from operator import itemgetter
inp_dict = { 'a':3,'ab':2,'abc':1,'abcd':0 }
print("Dictionary: ", inp_dict)
sort_dict= dict(sorted(inp_dict.items(), key=operator.itemgetter(1))) 
print("Sorted Dictionary by value: ", sort_dict)

В приведенной выше функции мы установили параметр. TITEMGETTER (1), потому что здесь «1» представляет значения DICT, а «0» представляет собой ключи диктов. Таким образом, мы сортировали Dict по ценностям в порядке возрастания.

Выход:

Dictionary:  {'a': 3, 'ab': 2, 'abc': 1, 'abcd': 0}
Sorted Dictionary by value:  {'abcd': 0, 'abc': 1, 'ab': 2, 'a': 3}

Пузырьковая сортировка

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

Алгоритм

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

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

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

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

Реализация

def bubble_sort(nums):  
    # Устанавливаем swapped в True, чтобы цикл запустился хотя бы один раз
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums > nums:
                # Меняем элементы
                nums, nums = nums, nums
                # Устанавливаем swapped в True для следующей итерации
                swapped = True

# Проверяем, что оно работает
random_list_of_nums =   
bubble_sort(random_list_of_nums)  
print(random_list_of_nums)

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

Время сортировки

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

Создание списка List для сортировки

Допустим нам необходимо хранить данные пользователей: их имя и год рождения. Для этого создадим в языке программирования C# список List, элементами которого, является строковый массив. Имя переменной: people.

C#

List<string[]> people = new List<string[]>();

Добавим в него четыре элемента с информацией о пользователях:

C#

people.Add(new string[] { «Иван», «1980» });
people.Add(new string[] { «Яна», «1987» });
people.Add(new string[] { «Михаил», «1979» });
people.Add(new string[] { «Анна», «1992» });

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

Вспомогательный метод для вывода списка в консоль

Напишем также метод OutputList, который выводит все элементы коллекции на экран в консоль.

C#

static void OutputList(List<string[]> list, string label)
{
Console.WriteLine(label);
Console.WriteLine();

foreach (string[] item in list)
Console.WriteLine(item + «, дата рождения: » + item);

Console.WriteLine();
}

Аргументы метода: list – сам список, который нужно вывести в консоль и label – строка с информацией (она будет выведена перед списком).

Выведем на экран текущее содержимое списка people (запустим программу комбинацией клавиш Ctrl + F5):

C#

OutputList(people, «Список до сортировки»);

Техника 3: Python Sorted () Метод наряду с Dict.items ()

Функция Scorted () Python может быть использована для сортировки словаря по значению в Python, передавая значения через Dict.Items () к способу.

Получает ключи/значения из словаря.

Синтаксис:

dict.items()

Пример:

inp_dict = { 'a':3,'ab':2,'abc':1,'abcd':0 }
print("Dictionary: ", inp_dict)
sort_dict= dict(sorted((value, key) for (key,value) in inp_dict.items())) 
print("Sorted Dictionary by value: ", sort_dict)

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

Выход:

Dictionary:  {'a': 3, 'ab': 2, 'abc': 1, 'abcd': 0}
Sorted Dictionary by value:  {0: 'abcd', 1: 'abc', 2: 'ab', 3: 'a'}

Пример 4. Сортировка списка словарей

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

Каждый словарь внутри списка содержит три пары ключ-значение.

Рассмотрим четыре типа сортировки. Первый использует сортировку на основе ключа . Второй – на основе ключа . Третий способ демонстрирует сортировку на основе обоих этих ключей. В четвертом случае мы видим сортировку в порядке убывания на основе ключа .

dic_list = 

# Print the sorted dictionary based on code
print("Sorting based on the code:\n", sorted(dic_list, key=lambda i: i))
# Print the sorted dictionary based on name
print("Sorting based on the name:\n", sorted(dic_list, key=lambda i: (i)))
# Print the sorted dictionary based on code and name
print("Sorting based on the code and name:\n", sorted(dic_list, key=lambda i: (i, i)))
# Print the sorted dictionary in descending based on name
print("Sorting in descending order based on the name:\n", sorted(dic_list, key=lambda i: i, reverse=True))

Запустим нашу программу и получим следующий результат.

Sorting based on the code:
 
Sorting based on the name:
 
Sorting based on the code and name:
 
Sorting in descending order based on the name:
 

Пирамидальная сортировка («сортировка кучей»)

Как и в двух предыдущих алгоритмах, мы создаем два сегмента списка: отсортированный и несортированный.

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

Метод heapify в примере кода использует рекурсию для получения элемента с максимальным значением на вершине.

Алгоритм пирамидальной сортировки:

• нерекурсивный;
• неустойчивый;
• преобразует входные данные без использования вспомогательной структуры данных (in place);
• имеет сложность O(nlog(n));

def heapify(array, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    
    if l < n and array < array:
        largest = l
    if r < n and array < array:
        largest = r
    
    if largest != i:
        array, array = array, array
        heapify(array, n, largest)
        
def heapSort(array):
    n = len(array)
    for i in range(n//2, -1, -1):
        heapify(array, n, i)
    for i in range(n-1, 0, -1):
        array, array = array, array
        heapify(array, i, 0)
    return array

От: admin

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