Pythonic way to check if a list is sorted or not

Question

Is there a pythonic way to check if a list is already sorted in ASC or DESC  listtimestamps    1  2  3  5  6  7    something like isttimestamps isSorted   that returns True or False   I want to input a list of timestamps for some messages and check if the the transactions appeared in the correct order

User · Answer

Not very Pythonic at all  but we need at least one reduce   answer  right   def is sorted iterable       prev or inf   lambda prev  i  i if prev  lt   i else float  inf       return reduce prev or inf  iterable  float  -inf     lt  float  inf     The accumulator variable simply stores that last-checked value  and if any value is smaller than the previous value  the accumulator is set to infinity  and thus will still be infinity at the end  since the  previous value  will always be bigger than the current one

User · Answer

With the upcoming Python 3 10 release schedule  the new pairwise function provides a way to slide through pairs of consecutive elements  and thus find if all of these pairs satisfy the same predicate of ordering  from itertools import pairwise  all x  lt   y for x  y in pairwise  1  2  3  5  6  7      True   The intermediate result of pairwise  pairwise  1  2  3  5  6  7       1  2    2  3    3  5    5  6    6  7

User · Answer

I would just use  if sorted lst     lst        code here   unless it s a very big list in which case you might want to create a custom function   if you are just going to sort it if it s not sorted  then forget the check and sort it   lst sort     and don t think about it too much   if you want a custom function  you can do something like  def is sorted lst  key lambda x  x       for i  el in enumerate lst 1             if key el   lt  key lst i      i is the index of the previous element             return False     return True   This will be O n  if the list is already sorted though  and O n  in a for loop at that   so  unless you expect it to be not sorted  and fairly random  most of the time  I would  again  just sort the list

User · Answer

Lazy  from itertools import tee  def is sorted l       l1  l2   tee l      next l2  None      return all a  lt   b for a  b in zip l1  l2

User · Answer

I use this one-liner based on numpy diff     def issorted x          Check if x is sorted        return  numpy diff x   gt   0  all     is diff between all consecutive entries  gt   0    I haven t really timed it against any other method  but I assume it s faster than any pure Python method  especially for large n  since the loop in numpy diff  probably  runs directly in C  n-1 subtractions followed by n-1 comparisons    However  you need to be careful if x is an unsigned int  which might cause silent integer underflow in numpy diff    resulting in a false positive  Here s a modified version   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   gt   0  all

User · Answer

A beautiful way to implement this is to use the imap function from 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     This implementation is fast and works on any iterables

User · Answer

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   lt   lst 1  and is Sorted lst 1      any list    1 2 3 4   print is Sorted any list

User · Answer

As noted by  aaronsterling the following solution is the shortest and seems fastest when the array is sorted and not too small      def is sorted lst           return  sorted lst     lst   If most of the time the array is not sorted  it would be desirable to use a solution that does not scan the entire array and returns False as soon as an unsorted prefix is discovered  Following is the fastest solution I could find  it is not particularly elegant   def is sorted lst       it   iter lst      try          prev   it next       except StopIteration          return True     for x in it          if prev  gt  x              return False         prev   x     return True   Using Nathan Farrington s benchmark  this achieves better runtime than using sorted lst  in all cases except when running on the large sorted list   Here are the benchmark results on my computer   sorted lst   lst solution   L1  1 23838591576 L2  4 19063091278 L3  1 17996287346 L4  4 68399500847   Second solution    L1  0 81095790863 L2  0 802397012711 L3  1 06135106087 L4  8 82761001587

User · Answer

more itertools is sorted I m not sure when this was added  but this hasn t been mentioned yet  import more itertools  ls    1  4  2   print more itertools is sorted ls    ls2     quot ab quot    quot c quot    quot def quot    print more itertools is sorted ls2  key len

User · Answer

Python 3 6 8  from more itertools import pairwise  class AssertionHelper       classmethod     def is ascending cls  data  iter  - gt  bool          for a  b in pairwise data               if a  gt  b                  return False         return True       classmethod     def is descending cls  data  iter  - gt  bool          for a  b in pairwise data               if a  lt  b                  return False         return True       classmethod     def is sorted cls  data  iter  - gt  bool          return cls is ascending data  or cls is descending data     gt  gt  gt  AssertionHelper is descending  1  2  3  4   False  gt  gt  gt  AssertionHelper is ascending  1  2  3  4   True  gt  gt  gt  AssertionHelper is sorted  1  2  3  4   True

User · Answer

Just to add another way  even if it requires an additional module   iteration utilities all monotone    gt  gt  gt  from iteration utilities import all monotone  gt  gt  gt  listtimestamps    1  2  3  5  6  7   gt  gt  gt  all monotone listtimestamps  True   gt  gt  gt  all monotone  1 2 1   False   To check for DESC order    gt  gt  gt  all monotone listtimestamps  decreasing True  False   gt  gt  gt  all monotone  3 2 1   decreasing True  True   There is also a strict parameter if you need to check for strictly  if successive elements should not be equal  monotonic sequences   It s not a problem in your case but if your sequences contains nan values then some methods will fail  for example with sorted   def is sorted using sorted iterable       return sorted iterable     iterable   gt  gt  gt  is sorted using sorted  3  float  nan    1      definetly False  right  True   gt  gt  gt  all monotone  3  float  nan    1   False   Note that iteration utilities all monotone performs faster compared to the other solutions mentioned here especially for unsorted inputs  see benchmark

User · Answer

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

User · Answer

A solution using assignment expressions  added in Python 3 8    def is sorted seq       seq iter   iter seq      cur   next seq iter  None      return all  prev    cur   lt    cur    nxt  for nxt in seq iter   z   list range 10   print z  print is sorted z    import random random shuffle z  print z  print is sorted z    z      print z  print is sorted z     Gives    0  1  2  3  4  5  6  7  8  9  True  1  7  5  9  4  0  8  3  2  6  False    True

User · Answer

How about this one   Simple and straightforward    def is list sorted al        llength  len al        for i in range  llength           if  al i-1   gt  al i                print al i               print al i 1               print  Not sorted               return -1      else           print  sorted           return  true

User · Answer

Although I don t think there is a guarantee for that the sorted built-in calls its cmp function with i 1  i  it does seem to do so for CPython    So you could do something like   def my cmp x  y      cmpval   cmp x  y     if cmpval  lt  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     Or this way  without if statements -  EAFP gone wrong   -      def my cmp x  y      assert x  gt   y     return -1  def is sorted lst      try        sorted lst  cmp my cmp        return True    except AssertionError        return False

User · Answer

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

User · Answer

Simplest way   def isSorted arr     i   1   while i  lt  len arr       if result i   lt  result i - 1          return False     i    1   return True

User · Answer

Actually we are not giving the answer anijhaw is looking for  Here is the one liner   all l i   lt   l i 1  for i in xrange len l -1     For Python 3   all l i   lt   l i 1  for i in range len l -1

User · Answer

If you want the fastest way for numpy arrays  use numba  which if you use conda should be already installed  The code will be fast because it will be compiled by numba  import numba  numba jit def issorted vec  ascending True       if len vec   lt  2          return True     if ascending          for i in range 1  len vec                if vec i-1   gt  vec i                   return False         return True     else          for i in range 1  len vec                if vec i-1   lt  vec i                   return False         return True   and then    gt  gt  gt  issorted array  4 9 100     gt  gt  gt  True

User · Answer

As I don t see this option above I will add it to all the answers  Let denote the list by l  then   import numpy as np    Trasform the list to a numpy array x   np array l     check if ascendent sorted  all x  -1   lt   x 1       check if descendent sorted  all x  -1   gt   x 1

User · Answer

I d do this  stealing from a lot of answers here  Aaron Sterling  Wai Yip Tung  sorta from Paul McGuire  and mostly 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  lt   b       return all key a  b  for a  b in pairwise iterable     One nice thing  you don t have to realize the second iterable for the series  unlike with a  list slice

User · Answer

This is similar to the top answer  but I like it better because it avoids explicit indexing  Assuming your list has the name lst  you can generate  item  next item  tuples from your list with zip   all x  lt   y for x y in zip lst  lst 1       In Python 3  zip already returns a generator  in Python 2 you can use itertools izip for better memory efficiency   Small demo    gt  gt  gt  lst    1  2  3  4   gt  gt  gt  zip lst  lst 1      1  2    2  3    3  4    gt  gt  gt  all x  lt   y for x y in zip lst  lst 1     True  gt  gt  gt    gt  gt  gt  lst    1  2  3  2   gt  gt  gt  zip lst  lst 1      1  2    2  3    3  2    gt  gt  gt  all x  lt   y for x y in zip lst  lst 1     False   The last one fails when the tuple  3  2  is evaluated   Bonus  checking finite     generators which cannot be indexed    gt  gt  gt  def gen1            yield 1         yield 2         yield 3         yield 4           gt  gt  gt  def gen2            yield 1         yield 2         yield 4         yield 3       gt  gt  gt  g1 1   gen1    gt  gt  gt  g1 2   gen1    gt  gt  gt  next g1 2  1  gt  gt  gt  all x  lt   y for x y in zip g1 1  g1 2   True  gt  gt  gt   gt  gt  gt  g2 1   gen2    gt  gt  gt  g2 2   gen2    gt  gt  gt  next g2 2  1  gt  gt  gt  all x  lt   y for x y in zip g2 1  g2 2   False   Make sure to use itertools izip here if you are using Python 2  otherwise you would defeat the purpose of not having to create lists from the generators

User · Answer

This iterator form is 10-15  faster than using integer indexing     python2 only if str is bytes      from itertools import izip as zip  def is sorted l       return all a  lt   b for a  b in zip l  l 1

User · Answer

I ran a benchmark and sorted lst  reverse True     lst was the fastest for long lists  and all l i   gt   l i 1  for i in xrange len l -1   was the fastest for short lists  These benchmarks were run on a MacBook Pro 2010 13   Core2 Duo 2 66GHz  4GB 1067MHz DDR3 RAM  Mac OS X 10 6 5    UPDATE  I revised the script so that you can run it directly on your own system  The previous version had bugs  Also  I have added both sorted and unsorted inputs    Best for short sorted lists  all l i   gt   l i 1  for i in xrange len l -1   Best for long sorted lists  sorted l  reverse True     l Best for short unsorted lists  all l i   gt   l i 1  for i in xrange len l -1   Best for long unsorted lists  all l i   gt   l i 1  for i in xrange len l -1     So in most cases there is a clear winner   UPDATE  aaronsterling s answers   6 and  7  are actually the fastest in all cases   7 is the fastest because it doesn t have a layer of indirection to lookup the key      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  gt   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   gt   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  gt   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  gt   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  gt   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  gt   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

User · Answer

SapphireSun is quite right  You can just use lst sort    Python s sort implementation  TimSort  check if the list is already sorted  If so sort   will completed in linear time  Sounds like a Pythonic way to ensure a list is sorted

[python] Pythonic way to check if a list is sorted or not

Examples related to python

Examples related to algorithm

Examples related to list

Examples related to sorting