If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Selectionsort Pseudocode

Es gibt viele verschiedene Möglichkeiten, die Karten zu sortieren. Wir stellen hier eine davon vor, die Selectionsort heißt. Sie ähnelt evtl. der Methode mit der du die Karten oben sortiert hast:
  1. Finde die kleinste Karte. Vertausche sie mit der ersten Karte.
  2. Finde die zweitkleinste Karte. Vertausche sie mit der zweiten Karte.
  3. Finde die drittkleinste Karte. Vertausche sie mit der dritten Karte.
  4. Wiederhole die Suche nach der nächstkleinsten Karte und tausche sie in die richtige Position, bis das Array sortiert ist.
Dieser Algorithmus wird Selectionsort genannt, weil er immer wieder das nächst-kleinere Element selektiert (auswählt) und es an der richtigen Stelle einsetzt.
Du kannst dir den Algorithmus unten selbst anschauen. Verwende den Button "Step", damit du jeden Schritt des Algorithmus sehen kannst. Sobald du ihn verstanden hast, kannst du mit "Automatic" alle Schritte bis am Schluss ansehen.
Nachdem du den Algorithmus nun selbst gesehen hast, was hältst du davon? Welche Teile davon dauern am längsten? Wie wird er wohl mit großen Arrays funktionieren? Behalte diesen Fragen im Hinterkopf, während du dieses Tutorial machst und diesen Algorithmus implementierst.

Den Index des kleinsten Elements in einem Sub-Array finden

Einer der Schritte im Selectionsort ist es, die nächst-kleinere Karte zu finden und diese an der richtigen Stelle einzusetzen. Wenn das Array z.B. anfangs die Werte [13, 19, 18, 4, 10] enthält, müssen wir zuerst den Index des kleinsten Elementes im Array ermitteln. Da 4 der kleinste Wert ist, ist der Index des kleinsten Wertes 3.
Der Selectionsort vertauscht nun das Element mit Index 3 mit dem Element mit Index 0, was [4, 19, 18, 13, 10] ergibt. Nun müssen wir den Index des zweit-kleinsten Wertes finden und diesen mit dem Element bei Index 1 vertauschen.
Es kann etwas schwierig sein, Code zu schreiben, welcher den Index des zweit-kleinsten Elements im Array ermittelt. Ich bin mir sicher du kannst dies, aber es gibt noch einen besseren Weg. Beachte, da das kleinste Element schon an den Index 0 vertauscht wurde, müssen wir nur das kleinste Element im Array welches bei Index 1 beginnt finden. Wir nennen einen Teil eines Arrays ein Subarray. Daher suchen wir in diesem Fall den Index des kleinsten Elements im Subarray welches bei Index 1 beginnt. In unserem Beispiel, in welchem das ganze Array [4, 19, 18, 13, 10] ist, ist daher das kleinste Element beginnend bei Index 1 die 10, welche im ursprünglichen Array einen Index von 4 hat. Daher ist 4 die Stelle des zweit-kleinsten Elements im ganzen Array.
Versuche in der nächsten Challenge diese Strategie zu implementieren. Dann verstehst du schon fast alles um den kompletten Selectionsort-Algorithmus zu implementieren.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.