Алгоритмы сортировки данных с Python3, нестандартная сортировка

newbie

Опубликован:  2018-11-02T10:43:00.469587Z

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

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

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

Заданное условие сортировки необходимо выразить кодом.

>>> def compare(a, b):
...     return a + b > b + a
... 
>>> 

Функция compare оценивает последовательность двух переданных аргументами строк, и в зависимости от результата сравнения выдаёт булево значение True или False. Возьмём два целых числа в строковом выражении и оценим их последовательность в двух вариантах.

>>> compare('990', '9')
False
>>> compare('9', '990')
True
>>> 

Из примера видно, что с последовательностью '9', '990' функция compare возвращает истину, а с последовательностью '990', '9' - ложь. В численном выражении 9990 больше, чем 9909 - что удовлетворяет условиям задачи, эта функция и будет использована для сравнения элементов исходного списка далее.

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

>>> a = ['00', '123', '126', '0823', '9', '90', '99', '990']
>>> 

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

>>> def find_first(list_):
...     i = 0
...     for each in range(len(list_)):
...             if compare(list_[each], list_[i]):
...                     i = each
...     return i
... 
>>> 

Определяем индекс искомого элемента.

>>> find_first(a)
4
>>> 

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

>>> a[find_first(a)]
'9'
>>> 

Функция find_first вкупе с соответствующими стандартными средствами Питона даёт возможность отсортировать исходный список простыми действиями в цикле.

>>> def enrank(list_):
...     box = []
...     while list_:
...             m = find_first(list_)
...             box.append(list_[m])
...             list_.remove(list_[m])
...     list_.extend(box)
...     return None
... 
>>> 

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

>>> enrank(a)
>>> a
['9', '99', '990', '90', '126', '123', '0823', '00']
>>> 

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

>>> int(''.join(a))
99999090126123082300
>>> 

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

RYZKDenasJ.png

Метки:  python3x, str, int, list, sort
Комментарии: