목록이 정렬되었는지 여부를 확인하는 Pythonic 방법

목록이 정렬되었는지 여부를 확인하는 Pythonic 방법

---

목록이 이미 정렬되어 있는지 확인하는 파이썬 방법이 ASC또는DESC

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

같은 isttimestamps.isSorted()그 반환 True또는 False.

일부 메시지의 타임 스탬프 목록을 입력하고 트랜잭션이 올바른 순서로 나타나는지 확인하고 싶습니다.

---

실제로 우리는 anijhaw가 찾고있는 해답을주지 않습니다. 하나의 라이너는 다음과 같습니다.

all(l[i] <= l[i+1] for i in xrange(len(l)-1))

파이썬 3의 경우 :

all(l[i] <= l[i+1] for i in range(len(l)-1))

---

난 그냥 사용할거야

if sorted(lst) == lst:
    # code here

매우 큰 목록이 아닌 경우 사용자 정의 함수를 만들 수 있습니다.

정렬되지 않은 경우 정렬하려는 경우 확인을 잊고 정렬하십시오.

lst.sort()

그것에 대해 너무 많이 생각하지 마십시오.

사용자 정의 기능을 원하면 다음과 같은 작업을 수행 할 수 있습니다

def is_sorted(lst, key=lambda x: x):
    for i, el in enumerate(lst[1:]):
        if key(el) < key(lst[i]): # i is the index of the previous element
            return False
    return True

목록이 이미 정렬되어 있으면 for루프 (O (n) 입니다!)이므로 대부분 정렬되지 않을 것으로 예상하지 않는 한, 다시 목록을 정렬하십시오.

---

이 반복자 형식은 정수 색인 작성보다 10-15 % 빠릅니다.

# python2 only
if str is bytes:
    from itertools import izip as zip

def is_sorted(l):
    return all(a <= b for a, b in zip(l, l[1:]))

---

이것을 구현하는 아름다운 방법 imap은 itertools다음 에서 함수 를 사용하는 것입니다 .

from itertools import imap, tee
import operator

def is_sorted(iterable, compare=operator.le):
  a, b = tee(iterable)
  next(b, None)
  return all(imap(compare, a, b))

이 구현은 빠르며 모든 iterable에서 작동합니다.

---

나는 벤치 마크를 실행 하고 sorted(lst, reverse=True) == lst긴 목록에 대한 가장 빠른, 그리고 all(l[i] >= l[i+1] for i in xrange(len(l)-1))가장 빠른 짧은 목록에 대한이었다 . 이 벤치 마크는 MacBook Pro 2010 13 "(Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5)에서 실행되었습니다.

업데이트 : 스크립트를 수정하여 자신의 시스템에서 직접 실행할 수 있습니다. 이전 버전에는 버그가있었습니다. 또한 정렬 된 입력과 정렬되지 않은 입력을 모두 추가했습니다.

• 짧은 정렬 목록에 가장 적합 : all(l[i] >= l[i+1] for i in xrange(len(l)-1))
• 긴 정렬 목록에 가장 적합 : sorted(l, reverse=True) == l
• 분류되지 않은 짧은 목록에 가장 적합 : all(l[i] >= l[i+1] for i in xrange(len(l)-1))
• 정렬되지 않은 긴 목록에 가장 적합 : all(l[i] >= l[i+1] for i in xrange(len(l)-1))

따라서 대부분의 경우 확실한 승자가 있습니다.

업데이트 : aaronsterling의 답변 (# 6 및 # 7)은 실제로 모든 경우에서 가장 빠릅니다. # 7은 키를 조회 할 수있는 간접 계층이 없기 때문에 가장 빠릅니다.

#!/usr/bin/env python

import itertools
import time

def benchmark(f, *args):
    t1 = time.time()
    for i in xrange(1000000):
        f(*args)
    t2 = time.time()
    return t2-t1

L1 = range(4, 0, -1)
L2 = range(100, 0, -1)
L3 = range(0, 4)
L4 = range(0, 100)

# 1.
def isNonIncreasing(l, key=lambda x,y: x >= y): 
    return all(key(l[i],l[i+1]) for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 2.47253704071
print benchmark(isNonIncreasing, L2) # 34.5398209095
print benchmark(isNonIncreasing, L3) # 2.1916718483
print benchmark(isNonIncreasing, L4) # 2.19576501846

# 2.
def isNonIncreasing(l):
    return all(l[i] >= l[i+1] for i in xrange(len(l)-1))
print benchmark(isNonIncreasing, L1) # 1.86919999123
print benchmark(isNonIncreasing, L2) # 21.8603689671
print benchmark(isNonIncreasing, L3) # 1.95684289932
print benchmark(isNonIncreasing, L4) # 1.95272517204

# 3.
def isNonIncreasing(l, key=lambda x,y: x >= y): 
    return all(key(a,b) for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.65468883514
print benchmark(isNonIncreasing, L2) # 29.7504849434
print benchmark(isNonIncreasing, L3) # 2.78062295914
print benchmark(isNonIncreasing, L4) # 3.73436689377

# 4.
def isNonIncreasing(l):
    return all(a >= b for (a,b) in itertools.izip(l[:-1],l[1:]))
print benchmark(isNonIncreasing, L1) # 2.06947803497
print benchmark(isNonIncreasing, L2) # 15.6351969242
print benchmark(isNonIncreasing, L3) # 2.45671010017
print benchmark(isNonIncreasing, L4) # 3.48461818695

# 5.
def isNonIncreasing(l):
    return sorted(l, reverse=True) == l
print benchmark(isNonIncreasing, L1) # 2.01579380035
print benchmark(isNonIncreasing, L2) # 5.44593787193
print benchmark(isNonIncreasing, L3) # 2.01813793182
print benchmark(isNonIncreasing, L4) # 4.97615599632

# 6.
def isNonIncreasing(l, key=lambda x, y: x >= y): 
    for i, el in enumerate(l[1:]):
        if key(el, l[i-1]):
            return False
    return True
print benchmark(isNonIncreasing, L1) # 1.06842684746
print benchmark(isNonIncreasing, L2) # 1.67291283607
print benchmark(isNonIncreasing, L3) # 1.39491200447
print benchmark(isNonIncreasing, L4) # 1.80557894707

# 7.
def isNonIncreasing(l):
    for i, el in enumerate(l[1:]):
        if el >= l[i-1]:
            return False
    return True
print benchmark(isNonIncreasing, L1) # 0.883186101913
print benchmark(isNonIncreasing, L2) # 1.42852401733
print benchmark(isNonIncreasing, L3) # 1.09229516983
print benchmark(isNonIncreasing, L4) # 1.59502696991

---

나는 이것을 할 것입니다 ([Aaron Sterling, Wai Yip Tung, Paul McGuire의 일종 ) 및 대부분 Armin Ronacher )

from itertools import tee, izip

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

def is_sorted(iterable, key=lambda a, b: a <= b):
    return all(key(a, b) for a, b in pairwise(iterable))

한 가지 좋은 점은 시리즈에 대해 두 번째 반복 가능을 구현할 필요가 없다는 것입니다 (목록 조각과는 달리).

---

사파이어 선 이 옳습니다. 당신은 그냥 사용할 수 있습니다 lst.sort(). Python의 정렬 구현 (TimSort)은 목록이 이미 정렬되어 있는지 확인합니다. 그렇다면 sort ()는 선형 시간으로 완료됩니다. 목록이 정렬되도록하는 파이썬 방식처럼 들립니다.)

---

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

또는이 방법 (문장없이-> 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

---

전혀 Pythonic은 아니지만 적어도 하나의 reduce()대답이 필요합니다 .

def is_sorted(iterable):
    prev_or_inf = lambda prev, i: i if prev <= i else float('inf')
    return reduce(prev_or_inf, iterable, float('-inf')) < float('inf')

누산기 변수는 단순히 마지막으로 확인 된 값을 저장하며, 값이 이전 값보다 작은 경우 누산기는 무한대로 설정됩니다 (따라서 '이전 값'이 항상 현재 하나).

---

numpy.diff ()를 기반으로 한이 라이너를 사용합니다.

def issorted(x):
    """Check if x is sorted"""
    return (numpy.diff(x) >= 0).all() # is diff between all consecutive entries >= 0?

나는 다른 방법에 대해 실제로 시간을 정하지 않았지만 numpy.diff의 루프가 아마도 C (n-1 빼기 다음에 n이 있기 때문에) 특히 순수한 n에 대해 순수한 파이썬 방법보다 빠르다고 가정합니다. -1 비교).

그러나 x가 부호없는 int 인 경우주의해야합니다. 이로 인해 numpy.diff ()에서 자동 정수 언더 플로가 발생하여 오 탐지가 발생할 수 있습니다. 수정 된 버전은 다음과 같습니다.

def issorted(x):
    """Check if x is sorted"""
    try:
        if x.dtype.kind == 'u':
            # x is unsigned int array, risk of int underflow in np.diff
            x = numpy.int64(x)
    except AttributeError:
        pass # no dtype, not an array
    return (numpy.diff(x) >= 0).all()

---

이것은 최상위 답변과 비슷하지만 명시 적 인덱싱을 피하기 때문에 더 좋습니다. 리스트에 이름이 있다고 가정하면 다음 을 사용하여리스트에서 튜플을 lst생성 할 수 있습니다 .
(item, next_item)zip

all(x <= y for x,y in zip(lst, lst[1:]))

Python 3에서는 zip이미 생성기를 반환하고 Python 2 itertools.izip에서는 더 나은 메모리 효율성을 위해 사용할 수 있습니다 .

작은 데모 :

>>> lst = [1, 2, 3, 4]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 4)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
True
>>> 
>>> lst = [1, 2, 3, 2]
>>> zip(lst, lst[1:])
[(1, 2), (2, 3), (3, 2)]
>>> all(x <= y for x,y in zip(lst, lst[1:]))
False

튜플 (3, 2)을 평가할 때 마지막 것은 실패합니다 .

보너스 : 인덱싱 할 수없는 유한 (!) 생성기 점검 :

>>> def gen1():
...     yield 1
...     yield 2
...     yield 3
...     yield 4
...     
>>> def gen2():
...     yield 1
...     yield 2
...     yield 4
...     yield 3
... 
>>> g1_1 = gen1()
>>> g1_2 = gen1()
>>> next(g1_2)
1
>>> all(x <= y for x,y in zip(g1_1, g1_2))
True
>>>
>>> g2_1 = gen2()
>>> g2_2 = gen2()
>>> next(g2_2)
1
>>> all(x <= y for x,y in zip(g2_1, g2_2))
False

itertools.izipPython 2 를 사용하는 경우 여기 에서 사용 하십시오. 그렇지 않으면 생성기에서 목록을 작성할 필요가 없다는 목적을 잃게됩니다.

---

@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

Nathan Farrington의 벤치 마크를 사용하면 큰 정렬 목록에서 실행하는 경우를 제외하고 모든 경우에 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

---

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

---

다른 방법을 추가하기 만하면됩니다 (추가 모듈이 필요한 경우에도) : 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수행 빨리 다른 솔루션에 비해 특히 정렬되지 않은 입력 (참조 여기 언급 된 벤치 마크 ).

---

게으른

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

---

파이썬 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

---

가장 간단한 방법 :

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

---

from functools import reduce

# myiterable can be of any iterable type (including list)
isSorted = reduce(lambda r, e: (r[0] and (r[1] or r[2] <= e), False, e), myiterable, (True, True, None))[0]

The derived reduction value is a 3-part tuple of (sortedSoFarFlag, firstTimeFlag, lastElementValue). It initially starts with (True, True, None), which is also used as the result for an empty list (regarded as sorted because there are no out-of-order elements). As it processes each element it calculates new values for the tuple (using previous tuple values with the next elementValue):

[0] (sortedSoFarFlag) evaluates true if: prev_0 is true and (prev_1 is true or prev_2 <= elementValue)
[1] (firstTimeFlag): False
[2] (lastElementValue): elementValue

The final result of the reduction is a tuple of:

[0]: True/False depending on whether the entire list was in sorted order
[1]: True/False depending on whether the list was empty
[2]: the last element value

The first value is the one we're interested in, so we use [0] to grab that from the reduce result.

---

This is in fact the shortest way to do it using recursion:

if it's Sorted will print True else will print out 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)

---

How about this one ? Simple and straightforward.

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

---

Definitely works in Python 3 and above for integers or strings:

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

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

Another way of finding if the given list is sorted or not

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

참고URL : https://stackoverflow.com/questions/3755136/pythonic-way-to-check-if-a-list-is-sorted-or-not