You can go through the example given: # using naive method to # check sorted list flag = 0 i = 1 while i < len(test_list): if(test_list[i] < test_list[i - 1]): flag = 1 i += 1 # printing result if (not flag) : print ("Yes, List is sorted.") else : print ("No, List is not sorted.")
GetItems(true) returns an ordered list of items, then test that. But don't test that items. OrderBy(x => x, new YourComparer()) does indeed sort the list. However, do unit test that YourComparer does indeed compare correctly.
4.1.reverseOrder() to check if a list is sorted in reverse order. In addition, we can use natural(). nullFirst() and natural(). nullLast() to check if null appears to the first or the last of the sorted list.
Actually we are not giving the answer anijhaw is looking for. Here is the one liner:
all(l[i] <= l[i+1] for i in xrange(len(l)-1))
For Python 3:
all(l[i] <= l[i+1] for i in range(len(l)-1))
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) < 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.
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 <= b for a, b in zip(l, l[1:]))
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.
I ran a benchmark and . These benchmarks were run on a MacBook Pro 2010 13" (Core2 Duo 2.66GHz, 4GB 1067MHz DDR3 RAM, Mac OS X 10.6.5).sorted(lst, reverse=True) == lst
was the fastest for long lists, and all(l[i] >= l[i+1] for i in xrange(len(l)-1))
was the fastest for short lists
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.
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))
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 >= 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
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 <= 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).
I use this one-liner based on numpy.diff():
def issorted(x):
"""Check if x is sorted"""
return (numpy.diff(x) >= 0).all() # is diff between all consecutive entries >= 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) >= 0).all()
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With