How would I write a function that takes a list as an argument and verifies whether or not the list is sorted?
I want it to return true if sorted and false otherwise. For example:
>>> is_sorted([1, 5, 8, 10])
True
>>> is_sorted([4, 1, 7, 8])
False
However, I'm unsure of how to do this with any kind of list at all
The simplest version that gets O(n) performance:
def is_sorted(lst):
return all(a <= b for a,b in zip(lst, lst[1:]))
An obvious way is to sort it and compare for equality with the original list:
#!/usr/bin/env python
def is_sorted(mylist):
testlist = sorted(mylist[:])
return testlist == mylist
print is_sorted([1, 4, 6, 7])
print is_sorted([1, 7, 6, 5])
outputs:
paul@horus:~/src/sandbox$ ./sorted.py
True
False
paul@horus:~/src/sandbox$
If you want something slightly more efficient (presuming you want to check if it's sorted in ascending order):
def is_sorted(mylist):
last_item = mylist[0]
for item in mylist:
if item < last_item:
return False
last_item = item
return True
This should be a O(n) solution by iterating through the list to check for values out of order. O(n) is worst case since it returns false the first element it finds out of order.
#!/usr/bin/env python
def is_sorted(mylist):
for i, val in enumerate(mylist):
if (i > 0 and mylist[i] < mylist[i-1]):
return False
return True
print is_sorted([1, 4, 6, 7])
print is_sorted([1, 7, 6, 5])
Output:
True
False
def is_sorted(mylist):
return False not in [sorted(mylist)[idx] == val for idx, val in enumerate(mylist)]
>>> is_sorted([1, 2, 3, 4])
True
>>> is_sorted([1, 2, 4, 3])
False
Here is the most simplest way to do this:
def is_sorted(l):
return True if l == sorted(l) else False
