Sortieren und Suche in Python

Stellen Sie sich vor, Sie haben ein Stück Papier in der Hand mit 1.000 aufgeführten Namen und müssen eine davon finden, aber diese Liste befindet sich nicht in alphabetischer Reihenfolge. Es wäre sehr frustrierend, nicht wahr? Während es lange dauert, um diese Liste zu klären, erleichtert es viel einfacher, Namen zu finden. Das Sortieren von Dingen ist also unser menschliches natürliches Verlangen, und die Suche nach sortierten Listen ist offensichtlich mehr arbeitssparend als die Suche nach ungeordneten Listen.

In der Computerwelt kann die Liste der Suchvorgänge sehr groß sein, und sogar schnelle Computer kann die Leistung beeinträchtigt werden. In diesem Fall wäre ein geeigneter Sortier- und Suchalgorithmus die Lösung für solche Probleme. Sortieren ist der Prozess der Sortierung einer Liste von Werten in der Reihenfolge, während die Suche der Prozess des Findens der Werteposition in der Liste ist.

Um die Bedeutung dieser Ausgabe zu veranschaulichen, lassen Sie mich Ihnen zeigen, was der große amerikanische Informatiker Donald Knuth sagte:

Computerhersteller in den 1960er Jahren schätzten, dass bei allen Kunden mehr als 25% ihrer Computerrunzleiter für die Sortierung aufgewendet wurden. In vielen Installationsfällen nimmt die Sortieraufgabe mehr als die Hälfte der Berechnungszeit ein. Aus diesen Statistiken können wir schließen, dass (i) Sortierung viele wichtige Anwendungen hat oder (ii) viele Menschen sortieren, wenn sie nicht sollten oder (iii) ineffiziente Sortieralgorithmen weit verbreitet sind. —— "Die Kunst des Computerprogrammierens" Band 3: Sortieren und Suche, Seite 3

In diesem Tutorial werde ich Ihnen zeigen, wie Sie den Auswahl -Sortieralgorithmus und den linearen Suchalgorithmus implementieren.

Aber bevor wir anfangen, wenn Sie nur in Ihrem Python-Code sortieren und suchen möchten, zeige ich Ihnen die integrierte Methode.

integrierte Sortiermethoden und Funktionen in Python

Sie können mit Python viele Sortieralgorithmen erstellen. Dies ist eine gute Lernübung, aber für Produktionsanwendungen sollten Sie sich an integrierte gespeicherte Funktionen und Methoden in Python halten.

Python hat eine list.sort() -Methode, mit der Sie die Liste an Ort und Stelle sortieren können. Der Sortieralgorithmus, der hinter den Kulissen von Python verwendet wird, heißt Timsort. Es ist ein Hybridsortieralgorithmus, der auf Sortier- und Zusammenführungssortierungen basiert und in vielen Leben im realen Leben eine hervorragende Leistung bietet. Hier ist ein Beispiel für die Verwendung dieser beiden Funktionen und Methoden:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

Sie können einige Situationen im obigen Code bemerken. Die Funktion sorted() gibt eine neue sortierte Liste zurück, ohne die ursprüngliche Liste marks_a zu ändern. Die ursprüngliche Liste bleibt jedoch gleich. Wenn wir dagegen die marks_b -Methode auf sort() aufrufen, gibt es None zurück.

Sie können einige Parameter übergeben, um das Sortierverhalten zu ändern. Übergeben Sie beispielsweise eine Funktion an den Parameter reverse, der unsere Liste der Wörter alphabetisch ohne Parameter sortiert. Im zweiten Fall verwenden wir sorted(), um die Reihenfolge sortierter Wörter umzukehren. reverse=True

Wählen Sie Sortieralgorithmus

Wählen Sie sortieren Der Algorithmus basiert auf einer kontinuierlichen Auswahl des Minimal- oder Maximalwerts. Angenommen, wir haben eine Liste, die wir in aufsteigender Reihenfolge sortieren möchten (klein bis groß). Das kleinste Element befindet sich am Anfang der Liste und das größte Element befindet sich am Ende der Liste.

Angenommen, die ursprüngliche Liste sieht folgendermaßen aus:

| 7 | 5 | 3.5 | 4 | 3.1 |

Das erste, was wir tun müssen, ist, den Wert

minimal in der Liste in diesem Fall zu finden. 3.1

Wenn der Mindestwert gefunden wird, tauschen Sie den Mindestwert mit dem ersten Element in der Liste

aus. Das heißt, wechseln Sie mit aus. Die Liste sieht jetzt so aus: 3.1 7

| 3.1 | 5 | 3.5 | 4 | 7 | Jetzt, da wir die richtige Position des ersten Elements in der Liste bestimmen, wiederholen wir die obigen Schritte (finden Sie den Mindestwert) aus dem zweiten

-Element der Liste. Wir können feststellen, dass der Mindestwert in der Liste (ab dem zweiten Element)

beträgt. Also werden wir jetzt mit austauschen. Die Liste wird jetzt: 3.5 3.5 5

Zu diesem Zeitpunkt stellen wir sicher, dass das erste Element und das zweite Element in ihrer richtigen Position sind. | 3.1 | 3.5 | 5 | 4 | 7 |

Jetzt überprüfen wir den Mindestwert im Rest der Liste, d. H. Beginnend mit dem dritten Element

. Der Mindestwert im Rest der Liste ist

, den wir jetzt mit

tauschen. Daher wird die Liste: 5 4 5

Daher bestimmen wir nun, dass die ersten drei | 3.1 | 3.5 | 4 | 5 | 7 | Elemente in der richtigen Position sind und der Prozess auf diese Weise fortgesetzt wird.

Lassen Sie uns sehen, wie der Auswahl -Sortieralgorithmus in Python (basierend auf Isai Damier) implementiert wird:

Testen wir den Algorithmus, indem Sie die folgende Anweisung am Ende des obigen Skripts hinzufügen:

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

In diesem Fall sollten Sie die folgende Ausgabe erhalten:

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

linearer Suchalgorithmus

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

Linearsuche

Algorithmus ist ein einfacher Algorithmus, bei dem jedes Element in der Liste überprüft wird (ab dem ersten Element), bis das gewünschte Element gefunden oder das Ende der Liste erreicht ist.

Der lineare Suchalgorithmus wird wie folgt in Python implementiert (basierend auf der Python -Schule):

testen wir den Code. Geben Sie die folgende Anweisung am Ende des obigen Python -Skripts ein:

Stellen Sie bei der Eingabe von

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print(my_list)

sicher, dass es zwischen einzelnen oder doppelten Zitaten liegt (d. H.

). Wenn Sie beispielsweise

eingeben, sollten Sie die folgende Ausgabe erhalten:

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

input 'pencil' 'pencil' und wenn Sie

als Eingabe eingeben, erhalten Sie die folgende Ausgabe:

Oops, your item seems not to be in the bag

Schlussfolgerung

Wie wir gesehen haben, erweist sich Python wieder als Programmiersprache, die das Konzept der Algorithmen leicht programmieren kann, genau wie wir es mit Sortier- und Suchalgorithmen hier zu tun haben.

Es ist zu beachten, dass es andere Arten der Sortier- und Suchalgorithmen gibt. Wenn Sie mit Python tiefer in diese Algorithmen eintauchen möchten, können Sie sich auf das kostenlose python-objektorientierte Programmierlehrbuch beziehen.

Das obige ist der detaillierte Inhalt vonSortieren und Suche in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!