Wie kann ich überprüfen, ob eine Liste sortiert ist?

Question

Mögliches Duplikat:
Pythonische Art zu prüfen, ob eine Liste sortiert ist oder nicht

Wie kann ich in Python testen, ob eine Liste von Zahlen bereits sortiert ist oder nicht?

Answer 1

Dies ist nur durch Iteration über die Liste (implizit oder explizit) möglich:

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

Aber warum sollte man sie nicht einfach sortieren, wenn man sie sortieren muss? Der Sortieralgorithmus von Python ist bei einer bereits sortierten Liste sehr günstig - möglicherweise günstiger als der obige Test.

EDIT: Da dies in eine Diskussion über die Leistung wurde, hier ist eine Version mit Lazy Iteratoren:

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

Bei einer zufällig geordneten Liste mit einer Million Einträgen ist dies mehr als 10000 Mal schneller als the_list == sorted(the_list) .

Answer 2

some_list == sorted(some_list)

Answer 3

Normalerweise sollten Sie bereits wissen, ob eine Liste sortiert ist (weil Ihre Eingabe so definiert ist oder Sie sie zuvor sortiert haben).

Wenn Sie überprüfen müssen, ob eine Liste sortiert ist, weil Sie sie sortieren wollen, wenn sie es nicht ist, sortieren Sie sie einfach. Das ist eine billige Operation, wenn die Liste bereits sortiert ist, und nicht viel teurer als die explizite Überprüfung der Reihenfolge.

Mit anderen Worten:

mylist.sort()

jetzt Sie wissen Es ist alles geregelt.

Answer 4

Mehr ein Kommentar zu den anderen Antworten als eine Antwort, aber diese Website macht richtige Kommentare unmöglich.

Die Sortierlösungen sind schneller, wenn die Liste bereits teilweise oder vollständig sortiert ist. Die iterativen Lösungen sind schneller, wenn die Liste wahrscheinlich in zufälliger Reihenfolge ist oder wenn die Liste von Anfang an ungeordnet ist.

Dafür gibt es zwei Gründe. Erstens ist Pythons Sortierfunktion sehr gut, wenn die Daten in einer Reihenfolge vorliegen, die sie versteht (teilweise sortiert, umgekehrt usw.), aber wenn die Daten zufällig oder anderweitig unvorhersehbar sind, kann sie nicht besser sein als jede andere Sortierfunktion. Zweitens kann die iterative Lösung einen Kurzschluss erzeugen, der so gut wie keine Arbeit macht, wenn sie frühzeitig feststellt, dass die Liste unsortiert ist.

Dies zeigt die entgegengesetzten Extreme:

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)

was auf meinem System zu diesen Zeitangaben führt:

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

Bei diesen Extremen ist der Sortieransatz also etwa dreimal schneller, und der lineare Ansatz ist etwa ... zweihunderttausendmal schneller.

Beachten Sie, dass der eigentliche Unterschied hier ist no O(n) vs. O(n log n); der Unterschied zwischen diesen Komplexitäten ist nicht annähernd so groß. Der Hauptunterschied besteht darin, dass die lineare Version einen Kurzschluss verursachen kann, sobald sie zwei Werte findet, die nicht in der richtigen Reihenfolge sind, während die Sortierversion immer die ganze Arbeit machen muss.

Eine systemeigene Implementierung könnte die ideale Leistung von beidem erreichen, indem sie die Komplexität von O(n), die Möglichkeit eines Kurzschlusses und den geringen Overhead von systemeigenem Code bietet, der den Sortieransatz schneller macht. Wenn (und nur wenn!) die Leistung wirklich wichtig ist, wäre dies die richtige Lösung.

(Beachten Sie, dass ich normalerweise nicht empfehlen würde, eine Lösung auf der Grundlage der Leistung zu wählen, es sei denn, die Leistung ist tatsächlich ein Problem, aber hier ist es erwähnenswert, da keiner der beiden Ansätze so viel einfacher ist als der andere. Die Sortiervariante ist etwas einfacher zu verstehen, aber auch die iterative Variante ist keineswegs komplex).

Answer 5

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"