Как проверить, отсортирован ли список?

Question

Можно создать дубликат:
Pythonic way to check if a list is sorted or not

В Python, как я могу проверить, является ли список номеров уже отсортированы или нет?

Answer 1

some_list == sorted(some_list) 

Answer 2

Это возможно только итерацию по списку (явно или неявно):

all(b >= a for a, b in zip(the_list, the_list[1:]) 

Но почему бы не просто разбирайтесь, если вам это нужно, чтобы быть отсортирован? Алгоритм сортировки Python будет действительно дешевым в уже отсортированном списке - возможно, дешевле, чем выше.

EDIT: Потому что это превратилось в дискуссию о производительности, вот версия с использованием ленивых итераторов:

it = iter(the_list) 
it.next() 
all(b >= a for a, b in itertools.izip(the_list, it)) 

Для случайного образом упорядоченного списка с миллионами записей, это более чем в 10000 раз быстрее, чем the_list == sorted(the_list).

Answer 3

Как правило, вы уже должны знать, отсортирован ли список (потому что именно так определяется ваш ввод или вы его отсортировали ранее).

Если вам нужно проверить, отсортирован ли список, потому что, если это не так, вы хотите его отсортировать, просто выполните сортировку. Это дешевая операция, если список уже отсортирован, и не намного дороже, чем проверка заказа явно.

Другими словами:

mylist.sort() 

теперь вы знаете это сортируется.

Answer 4

if L == (lambda pp=[]: reduce(lambda p, i: pp.append(reduce(lambda t, i: 
     (lambda t, i, j: (lambda l=[]: map(lambda x: (lambda xx=l.append(1): 
     t[sum(l) - 1] if sum(l) not in map(1..__radd__, (i, j)) else (t[i] if 
     sum(l) == j + 1 else t[j]))(), t))())(t, i, i + 1) if t[i] >= t[i + 1] 
     else t, xrange(len(p) - 1), p)) or pp[-1], iter(lambda: len(pp) >= 2 
     and list.__eq__(*pp[-2:]), True), L))(): 
    print "yeah, it's sorted" 

Answer 5

Еще комментарий к другим ответам, чем ответ, но этот сайт делает правильные комментарии невозможными.

Решения сортировки выполняются быстрее, если список уже частично или полностью отсортирован. Итеративные решения быстрее, если список, вероятно, будет в случайном порядке или если список не работает раньше.

Это по двум причинам. Во-первых, сорт Python очень хорош, когда он получает данные в том порядке, который он понимает (частично отсортированный, обратный и т. Д.), Но если данные случайны или непредсказуемы, то он может сделать не лучше, чем любой другой вид. Во-вторых, итеративное решение может замыкаться на короткое замыкание, не работая, если оно обнаруживает на ранней стадии, что список не отсортирован.

Это показывает противоположные крайности:

import timeit, random, itertools 

def a(data): 
    return all(b >= a for a, b in itertools.izip(data, itertools.islice(data, 1, None))) 

def b(data): 
    return data == sorted(data) 

def main(): 
    data = range(1000000) 
    print "Sorted, iterative:", timeit.timeit(lambda: a(data), number=10) 
    print "Sorted, sort:", timeit.timeit(lambda: b(data), number=10) 

    random.shuffle(data) 
    print "Random, iterative:", timeit.timeit(lambda: a(data), number=10) 
    print "Random, sort:", timeit.timeit(lambda: b(data), number=10) 

в результате этих тайминги на моей системе:

Sorted, iterative: 1.42838597298 
Sorted, sort: 0.498414993286 
Random, iterative: 0.000043 
Random, sort: 10.5548219681 

Таким образом, в этих экстремальных сортировочный подход примерно в три раза быстрее, а линейный подход есть примерно ... двести тысяч раз быстрее.

Обратите внимание, что реальная разница здесь не O (n) против O (n log n); различие между этими сложностями не так велико. Основное отличие состоит в том, что линейная версия может быть короткой, как только обнаружится два значения, которые не соответствуют порядку, где версия сортировки всегда должна выполнять всю работу.

Натуральная реализация может обеспечить идеальную производительность обоих, обеспечивая сложность O (n), способность к короткому замыканию и низкую накладную часть собственного кода, что ускоряет сортировку. Если (и только если!) Производительность действительно имеет значение, это было бы правильным решением.

(Обратите внимание, что обычно я бы не рекомендовал выбирать решение на основе производительности, если только производительность не была проблемой, но стоит отметить это, поскольку ни один из подходов не намного проще, чем другой. Сортировочная версия немного проще понимайте, но нет ничего сложного и в итеративной версии.)