Share
Wenn Sie ein Blatt Papier mit einer Liste von 1.000 Namen erhalten und nach einem Namen gefragt werden, aber diese Liste war nicht in einer beliebigen Reihenfolge (z. B. alphabetisch), wäre dies sehr frustrierend, oder? Wenn Sie diese Liste in die richtige Reihenfolge bringen, wird der Name viel einfacher gefunden, auch wenn dies lange dauert. Es ist daher ein natürlicher Wunsch, die Dinge in Ordnung zu haben, die wir Menschen haben, und das Durchsuchen dieser Liste würde eindeutig weniger Aufwand erfordern als das Durchsuchen einer ungeordneten Liste.
Lassen Sie uns zur Computerwelt übergehen, wo die Listen, für die eine Suche erforderlich ist, sehr groß sind und die Leistung selbst bei schnellen Computern beeinträchtigt werden kann. In diesem Fall eine geeignete sortieren und suchen Algorithmus wäre eine Lösung für ein solches Problem. Während Sortierung Es geht darum, eine Liste von Werten in Ordnung zu bringen, suchen ist der Vorgang des Ermittelns der Position eines Werts innerhalb einer Liste.
Um zu verdeutlichen, wie kritisch dieses Problem sein kann, möchte ich Ihnen zeigen, was Donald Knuth, ein US-amerikanischer Informatiker, Mathematiker und emeritierter Professor an der Stanford University, erwähnt hat Die Kunst der Computerprogrammierung, Band 3, Sortieren und Suchen, Seite 3:
Computerhersteller der 1960er Jahre schätzten, dass mehr als 25 Prozent der Laufzeit auf ihren Computern für das Sortieren aufgewendet wurde, wenn alle ihre Kunden berücksichtigt wurden. Tatsächlich gab es viele Installationen, bei denen die Sortieraufgabe für mehr als die Hälfte der Rechenzeit verantwortlich war. Aus diesen Statistiken können wir schlussfolgern, dass entweder (i) es viele wichtige Anwendungen für das Sortieren gibt oder (ii) viele Leute sortieren, wenn sie nicht sollten, oder (iii) ineffiziente Sortieralgorithmen allgemein verwendet wurden.
In diesem Tutorial werde ich das speziell beschreiben Auswahl sortieren Algorithmus (Sortierung) und die Lineare Suche Algorithmus (Suche).
Das Auswahl sortieren Der Algorithmus basiert auf einer aufeinanderfolgenden Auswahl von Minima oder Maxima. Angenommen, wir haben eine Liste, die wir in aufsteigender Reihenfolge sortieren möchten (von kleineren zu größeren Werten). Das kleinste Element befindet sich am Anfang der Liste und das größte Element am Ende der Liste.
Nehmen wir an, die ursprüngliche Liste sieht folgendermaßen aus:
| 7 | 5 | 3,5 | 4 | 3.1 |
Das erste, was wir tun, ist das zu finden Minimum Wert in der Liste, die in unserem Fall ist 3.1.
Nachdem Sie den Mindestwert gefunden haben, Wechsel dieser Mindestwert mit dem ersten Element in der Liste. Das heißt, tauschen 3.1 mit 7. Die Liste sieht nun folgendermaßen aus:
| 3.1 | 5 | 3,5 | 4 | 7 |
Nun, da wir sicher sind, dass sich das erste Element an der richtigen Position in der Liste befindet, wiederholen wir den obigen Schritt (Ermitteln des Mindestwerts), beginnend mit dem zweite Element in der Liste. Wir können feststellen, dass der Mindestwert in der Liste (ausgehend vom zweiten Element) ist 3,5. Wir tauschen also jetzt 3,5 mit 5. Die Liste wird nun wie folgt:
| 3.1 | 3,5 | 5 | 4 | 7 |
An diesem Punkt sind wir sicher, dass sich das erste Element und das zweite Element in ihrer korrekten Position befinden.
Jetzt prüfen wir den Mindestwert in der restlichen Liste, der vom dritten Element ausgeht 5. Der Mindestwert in der restlichen Liste ist 4, und wir tauschen es jetzt mit 5. Die Liste wird somit wie folgt:
| 3.1 | 3,5 | 4 | 5 | 7 |
Wir sind uns jetzt sicher, dass der erste drei Elemente befinden sich an den richtigen Positionen und der Prozess wird auf diese Weise fortgesetzt.
Sehen wir uns an, wie der Selection-Sort-Algorithmus in Python (basierend auf Isai Damier) implementiert wird:
def selectionSort (aList): für i im Bereich (len (aList)): am wenigsten = i für k im Bereich (i + 1, len (aList)): wenn 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
Testen Sie den Algorithmus, indem Sie am Ende des obigen Skripts die folgenden Anweisungen hinzufügen:
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
In diesem Fall sollten Sie folgende Ausgabe erhalten:
[4,6, 4,7, 5,76, 7,3, 7,6, 25,3, 32,4, 43,5, 52,3, 55,3, 86,7]
Das Lineare Suche aDer Algorithmus ist ein einfacher Algorithmus, bei dem jedes Element in der Liste (beginnend mit dem ersten Element) untersucht wird, bis das erforderliche Element gefunden ist oder das Ende der Liste erreicht ist.
Der lineare Suchalgorithmus wird in Python wie folgt implementiert (basierend auf Python School):
def linearSearch (item, my_list): gefunden = Falsche Position = 0 während der Position < len(my_list) and not found: if my_list[position] == item: found = True position = position + 1 return found
Lassen Sie uns den Code testen. Geben Sie die folgende Anweisung am Ende des Python-Skripts ein:
Accentsconagua
bag = ['Buch', 'Bleistift', 'Stift', 'Notizbuch', 'Spitzer', 'Gummi'] item = Eingabe ('Welches Element möchten Sie in der Tasche prüfen?') itemFound = linearSearch (item, bag) if itemFound: print "Ja, der Artikel befindet sich in der Tasche" ansonsten: print "Hoppla, Ihr Artikel scheint nicht in der Tasche zu sein"Wenn Sie das eingeben Eingang, Stellen Sie sicher, dass es zwischen einfachen oder doppelten Anführungszeichen steht (d. h. 'Bleistift'). Wenn du eingibst 'Bleistift', Zum Beispiel sollten Sie die folgende Ausgabe erhalten:
Ja, der Artikel befindet sich in der Tasche
Während, wenn Sie eintreten 'Lineal' Als Eingabe erhalten Sie folgende Ausgabe:
Hoppla, Ihr Gegenstand scheint nicht in der Tasche zu sein
Wie wir sehen, erweist sich Python wieder als Programmiersprache, die es einfach macht, algorithmische Konzepte so zu programmieren, wie wir es hier gemacht haben Sortierung und suchen Algorithmen.
Es ist wichtig zu beachten, dass es andere Arten von Sortier- und Suchalgorithmen gibt. Wenn Sie mit Python tiefer in solche Algorithmen eintauchen möchten, können Sie diese Seite aufrufen.
