Function for ordering a list alphabetically?

Question

I need a function that will order my list in alphabetical order, returning False if the list is not ordered alphabetically and True if it is.

It should work like this:

>>> ordered(['Cilka', 'Berta', 'Dani', 'Ana', 'Ema'])
False
>>> ordered(["Ana", "Berta", "Cilka", "Dani", "Ema"])
True

Names are in Slovenian language, don't mind them.

I have written this:

def ordered(s):

s is the name of the list. Can you help me?

Answer 1

Since the ordering on strings is already the alphabetical one, you can just use sorted:

def ordered(lst):
    return lst == sorted(lst)

Example

>>> ordered(['Cilka', 'Berta', 'Dani', 'Ana', 'Ema'])
False
>>> ordered(["Ana", "Berta", "Cilka", "Dani", "Ema"])
True

The problem with this approach is that it produces the sorted version of the list before comparing. So, if the list is really big you can just check if every element precedes the following in the lexicographic order:

def ordered2(lst):
    return all(lst[i] <= lst[i + 1] for i in xrange(len(lst) - 1))

Example

The side effect is that this one produces the sorted version of the list. If the list is really big you can just check if every element precedes the following in the lexicographic order:

>>> ordered2(['Cilka', 'Berta', 'Dani', 'Ana', 'Ema'])
False
>>> ordered2(["Ana", "Berta", "Cilka", "Dani", "Ema"])
True

Or if you really want to be super-lazy and super-pythonic you can use izip and islice:

from itertools import izip, islice

def ordered3(lst):
    return all(x <= y for x, y in izip(islice(lst, 0), islice(lst, 1)))

Time comparison

Let's generate a big list of shuffled numbers (the method works for everything that is comparable and has an ordering):

In [20]: from random import shuffle

In [21]: lst = range(10000)

In [22]: shuffle(lst)

In [23]: %timeit ordered(lst)
1000 loops, best of 3: 1.48 ms per loop

In [24]: %timeit ordered2(lst)
1000000 loops, best of 3: 696 ns per loop

In [25]: %timeit ordered3(lst)
1000000 loops, best of 3: 602 ns per loop

As you can see ordered2 and ordered3 are way faster than ordered. That's because the initial sort operation implies an O(n·ln) cost, not implied in the other two methods.