Insertionsort: Unterschied zwischen den Versionen

Aus KGS-Wiki
Keine Bearbeitungszusammenfassung
(Seite angelegt)
Zeile 5: Zeile 5:
* Unterteile die Liste in einen sortierten und einen unsortierten Bereich.
* Unterteile die Liste in einen sortierten und einen unsortierten Bereich.
* Der sortierte Bereich ist zu Beginn leer, der unsortierte Bereich enthält die ganze Liste
* Der sortierte Bereich ist zu Beginn leer, der unsortierte Bereich enthält die ganze Liste
* Wiederhole <code>n</code> Mal:
* Gehe durch die ganze Liste durch:
** Gehe durch den gesamten unsortierten Bereich durch und finde das kleinste Element
** Betrachte das erste Element des unsortierten Bereichs.
** Füge dieses Element am Ende des sortierten Bereichs ein
** Gehe durch den ganzen sortierten Bereich
** Finde die Position, an der dieses Element in den sortierten Bereich gehört, und sortiere es dort ein.


== Laufzeit ==
== Laufzeit ==
Die Liste mit <code>n</code> Elementen muss <code>n</code> Mal durchlaufen werden, wobei beim ersten Durchgang <code>n</code> Elemente betrachtet werden, beim zweiten Durchgang <code>n-1</code> Elemente, beim dritten Durchgang <code>n-2</code> Elemente und so weiter, bis beim letzten Durchgang nur noch ein Element betrachtet wird. Insgesamt werden also <math>1+2+3+\cdots+n = \frac{n^2 + n}{2}</math> Elemente betrachtet. Damit liegt die Laufzeit in <math>\mathcal{O}(n^2)</math>.
Die gesamte Liste wird einmal durchlaufen, wobei für jedes betrachtete Element im schlechtesten Fall der gesamte unsortierte Bereich durchlaufen werden muss. Beim ersten Element hat dieser unsortierte Bereich die Größe <code>0</code>, beim zweiten Element die Größe <code>1</code>, beim dritten Element die Größe <code>3</code> und so weiter, bis der sortierte Bereich am Ende <code>n-1</code> Elemente enthält.
 
Insgesamt werden also <math>1+2+3+\cdots + (n-1) = \frac{n^2-n}{2}</math> Elemente betrachtet, die Laufzeit liegt also insgesamt in <math>\mathcal{O}(n^2)</math>.
{{Navigationsleiste Sortieralgorithmen}}
{{Navigationsleiste Sortieralgorithmen}}

Version vom 16. Januar 2024, 17:42 Uhr

Selectionsort ist ein Sortieralgorithmus und arbeitet wie folgt:

Gegeben: Eine Liste A der Länge n:

  • Unterteile die Liste in einen sortierten und einen unsortierten Bereich.
  • Der sortierte Bereich ist zu Beginn leer, der unsortierte Bereich enthält die ganze Liste
  • Gehe durch die ganze Liste durch:
    • Betrachte das erste Element des unsortierten Bereichs.
    • Gehe durch den ganzen sortierten Bereich
    • Finde die Position, an der dieses Element in den sortierten Bereich gehört, und sortiere es dort ein.

Laufzeit

Die gesamte Liste wird einmal durchlaufen, wobei für jedes betrachtete Element im schlechtesten Fall der gesamte unsortierte Bereich durchlaufen werden muss. Beim ersten Element hat dieser unsortierte Bereich die Größe 0, beim zweiten Element die Größe 1, beim dritten Element die Größe 3 und so weiter, bis der sortierte Bereich am Ende n-1 Elemente enthält.

Insgesamt werden also Elemente betrachtet, die Laufzeit liegt also insgesamt in .


Weblinks


Abgerufen von „https://wiki.kah.gs/index.php?title=Insertionsort&oldid=3464“