Sortieralgorithmen mit Arrays und Listen in Java: Insertion Sort, Selection Sort und Bubble Sort

  • Beitrag veröffentlicht:10. April 2021
  • Beitrags-Kategorie:Java / Programmierung
  • Beitrags-Kommentare:0 Kommentare
  • Lesedauer:3 min Lesezeit
  • 880 Wörter

In diesem Artikel möchte ich dir gerne einmal die wohl drei gängigsten Sortieralgorithmen zeigen, ein bisschen erklären und sie miteinander vergleichen. Dabei werde ich vor allem den Quelltext für die verschiedenen Anwendungsbeispiele zeigen, da dieser oft hilfreicher ist als Umschreibungen und Erklärungen ;-).

Meistens sind die Implementierungen in Java mit Arrays ein wenig einfacher als mit Listen, da es sich dabei ja auch um statische anstatt dynamische Datenstrukturen handelt. Die Laufzeiten werde ich dir aber auch noch am Ende zeigen.

Insertion Sort

Beim Insertion Sort (oder auch „Sortieren durch Einfügen“) wird grob gesagt immer das erste Element von einer unsortierten Liste herausgenommen und dann an der passenden Stelle in eine sortierte Liste eingefügt.

Die durchschnittliche Laufzeit ist dabei quadratisch, also O(n²) ist die quadrierte Anzahl der zu sortierenden Elemente.

Array

List

Selection Sort

Beim Selection Sort (oder auch „Sortieren durch Auswählen“) wird immer das kleinste Element der unsortierten Liste ausgewählt und dieses dann an die sortierte Liste angehangen.

Die Laufzeit ist dabei im Schnitt ebenfalls quadratisch, also O(n²) ist die quadrierte Anzahl der zu sortierenden Elemente.

Array

List

Bubble Sort

Beim Bubble Sort (oder auch „Sortieren durch Vertauschen“) wird ein Element immer mit seinem Nachbarelement verglichen und getauscht, wenn es entsprechend größer ist. Das wird so lange wiederholt bis bei einem kompletten Durchlauf der Liste kein Tausch mehr stattgefunden hat.

Die durchschnittliche Laufzeit ist dabei quadratisch, also O(n²) ist die quadrierte Anzahl der zu sortierenden Elemente.

Array

List

Ich hoffe, dass ich dir damit ein wenig helfen konnte. Falls du Fehler oder Optimierungspotenzial im Quellcode feststellen solltest, kannst du natürlich gerne einen Kommentar schreiben ;-).

Hinweis: Mit Sternchen (*) markierte Links auf dieser Seite sind Werbelinks. Beim Kauf darüber erhalte ich eine kleine Provision, der Preis bleibt für dich aber gleich. Damit unterstützt du mich, sodass ich weiterhin kostenlosen Inhalt auf diesem Blog anbieten kann ;-).

Hast du Fragen, Anregungen oder einen einfachen Kommentar dazu? Dann poste es hier!

Bitte bedenke, dass alle Kommentare manuell freigeschaltet werden müssen. Das kann teilweise ein bisschen dauern, du kannst dich aber mit der unten aufgeführten Funktion benachrichtigen lassen, wenn er beantwortet wurde. Das heißt auch, dass Beleidigungen, Spam oder pure Werbung keine Chance haben, auf die Website zu kommen. Deine Email-Adresse wird selbstverständlich nicht veröffentlicht. Erforderliche Felder sind mit * oder (erforderlich) markiert.