Pythonic способ проверить, отсортирован ли список или нет

Question

Есть ли питонный способ проверить, отсортирован ли список уже в ASC или DESC

listtimestamps = [1, 2, 3, 5, 6, 7]

что-то вроде isttimestamps.isSorted(), которое возвращает True или False.

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

Answer 1

Хотя я не думаю, что есть гарантия, что встроенная функция sorted вызывает свою функцию cmp с i+1, i, похоже, она делает это для CPython.

Так что вы можете сделать что-то вроде:

def my_cmp(x, y):
   cmpval = cmp(x, y)
   if cmpval < 0:
      raise ValueError
   return cmpval

def is_sorted(lst):
   try:
      sorted(lst, cmp=my_cmp)
      return True
   except ValueError:
      return False

print is_sorted([1,2,3,5,6,7])
print is_sorted([1,2,5,3,6,7])

Или вот так (без операторов if -> EAFP пошло не так? ;-)):

def my_cmp(x, y):
   assert(x >= y)
   return -1

def is_sorted(lst):
   try:
      sorted(lst, cmp=my_cmp)
      return True
   except AssertionError:
      return False

Answer 2

Просто для добавления другого способа (даже если для этого требуется дополнительный модуль): iteration_utilities.all_monotone:

>>> from iteration_utilities import all_monotone
>>> listtimestamps = [1, 2, 3, 5, 6, 7]
>>> all_monotone(listtimestamps)
True

>>> all_monotone([1,2,1])
False

Для проверки заказа DESC:

>>> all_monotone(listtimestamps, decreasing=True)
False

>>> all_monotone([3,2,1], decreasing=True)
True

Существует также параметр strict, если необходимо строго проверить (если последовательные элементы не должны быть равными) монотонные последовательности.

В вашем случае это не проблема, но , если ваша последовательность содержит nan значений, то некоторые методы не будут работать, например, с сортировкой:

def is_sorted_using_sorted(iterable):
    return sorted(iterable) == iterable

>>> is_sorted_using_sorted([3, float('nan'), 1])  # definetly False, right?
True

>>> all_monotone([3, float('nan'), 1])
False

Обратите внимание, что iteration_utilities.all_monotone работает быстрее по сравнению с другими решениями, упомянутыми здесь, особенно для несортированных входов (см. тест ).

Answer 3

Если вы хотите самый быстрый способ для массивов numpy, используйте numba , который, если вы используете conda, должен быть уже установлен

Код будет быстрым, потому что он будет скомпилирован numba

import numba
@numba.jit
def issorted(vec, ascending=True):
    if len(vec) < 2:
        return True
    if ascending:
        for i in range(1, len(vec)):
            if vec[i-1] > vec[i]:
                return False
        return True
    else:
        for i in range(1, len(vec)):
            if vec[i-1] < vec[i]:
                return False
        return True

, а затем:

>>> issorted(array([4,9,100]))
>>> True

Answer 4

Как отмечает @aaronsterling, следующее решение является самым коротким и кажется самым быстрым, когда массив отсортирован и не слишком мал: def is_sorted (lst): return (sorted (lst) == lst)

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

def is_sorted(lst):
    it = iter(lst)
    try:
        prev = it.next()
    except StopIteration:
        return True
    for x in it:
        if prev > x:
            return False
        prev = x
    return True

Используя эталонный тест Натана Фаррингтона, это обеспечивает лучшее время выполнения, чем использование sorted (lst) во всех случаях, кроме случаев, когда выполняется большой отсортированный список..

Вот результаты тестов на моем компьютере.

отсортировано (lst) == lst решение

• L1: 1.23838591576
• L2: 4.19063091278
• L3: 1.17996287346
• L4: 4.68399500847

Второй раствор:

• L1: 0,81095790863
• L2: 0,802397012711
• L3: 1,06135106087
• L4: 8,82761001587

Answer 5

Ленивый

from itertools import tee

def is_sorted(l):
    l1, l2 = tee(l)
    next(l2, None)
    return all(a <= b for a, b in zip(l1, l2))

Answer 6

Python 3.6.8

from more_itertools import pairwise

class AssertionHelper:
    @classmethod
    def is_ascending(cls, data: iter) -> bool:
        for a, b in pairwise(data):
            if a > b:
                return False
        return True

    @classmethod
    def is_descending(cls, data: iter) -> bool:
        for a, b in pairwise(data):
            if a < b:
                return False
        return True

    @classmethod
    def is_sorted(cls, data: iter) -> bool:
        return cls.is_ascending(data) or cls.is_descending(data)

>>> AssertionHelper.is_descending((1, 2, 3, 4))
False
>>> AssertionHelper.is_ascending((1, 2, 3, 4))
True
>>> AssertionHelper.is_sorted((1, 2, 3, 4))
True

Answer 7

Самый простой способ:

def isSorted(arr):
  i = 1
  while i < len(arr):
    if(result[i] < result[i - 1]):
      return False
    i += 1
  return True

Answer 8

Как насчет этого?Просто и понятно.

def is_list_sorted(al):

    llength =len(al)


    for i in range (llength):
        if (al[i-1] > al[i]):
            print(al[i])
            print(al[i+1])
            print('Not sorted')
            return -1

    else :
        print('sorted')
        return  true

Answer 9

На самом деле это самый короткий способ сделать это с помощью рекурсии:

если отсортировано, будет напечатано True, иначе будет напечатано False

 def is_Sorted(lst):
    if len(lst) == 1:
       return True
    return lst[0] <= lst[1] and is_Sorted(lst[1:])

 any_list = [1,2,3,4]
 print is_Sorted(any_list)

Answer 10

Определенно работает в Python 3 и выше для целых чисел или строк:

def tail(t):
    return t[:]

letters = ['a', 'b', 'c', 'd', 'e']
rest = tail(letters)
rest.sort()
if letters == rest:
    print ('Given list is SORTED.')
else:
    print ('List NOT Sorted.')

==========================================================================

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

trees1 = list ([1, 4, 5, 3, 2])
trees2 = list (trees1)
trees2.sort()
if trees1 == trees2:
    print ('trees1 is SORTED')
else:
    print ('Not sorted')