Insertionsort: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) |
Thomas (Diskussion | Beiträge) |
||
| Zeile 45: | Zeile 45: | ||
Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort: | Eine sortierte Liste in umgekehrter Reihenfolge ist das Worst Case Szenario für den InsertionSort: | ||
[11,7,5,3,2,0] | <math>[11,7,5,3,2,0]</math> | ||
Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n. | Wir betrachten nur die Vergleichsoperationen, die wir mit der Variable c messen. Die Anzahl der zu sortierenden Elemente ist entspricht n. | ||
| Zeile 51: | Zeile 51: | ||
Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also: | Beim ersten äußeren Schleifendurchlauf ist c = 1. Denn wir müssen nur die Zahl 7 mit der Zahl 11 vergleichen. 7 wird einsortiert und es bildet sich der bereits sortierte Teil (siehe oben) der Datenstruktur. Beim zweiten Durchlauf der äußeren Schleife benötigen wir zwei Vergleiche , c = 2. Beim dritte Mal, c = 3 bis zum letzten Mal, wenn c = n-1. Es gilt also: | ||
c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1)) | <math>c⋅1+c⋅2+c⋅3+⋯c⋅(n−1)=c⋅(1+2+3+⋯+(n−1))</math> | ||
Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe|arithmetische Reihen]], erhalten wir: | Hierbei handelt es sich um eine [[Arithmetische-reihe|arithmetische Reihe]], mit der Ausnahme, dass sie bis zu n-1 anstatt n ansteigt. Unter Verwendung unserer Formel für [[Arithmetische-reihe|arithmetische Reihen]], erhalten wir: | ||
c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2 | <math>c⋅(n−1+1)*((n−1)/2)=cn2/2 − cn/2</math> | ||
Für sehr große n können wir den niederwertigen Term cn/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt: | Für sehr große n können wir den niederwertigen Term cn/2 und die konstanten Faktoren c und 1/2 verwerfen, so dass gilt: | ||