blatt 1 beispiel 8

[gonzo69]

leider, wird hier bis jetzt wenig über lösungen diskutiert, ich mach mal einen anfang, vielleicht interessierts doch wen :)

also zu beispiel 8)
ich weiß nicht genau, was sie mit schlüsselvergleiche und bewegungen mein, vielleicht kann mich da wer aufklären

aber wenn die liste (50,60,12,45,101,18,1,67) nach dem verfahren sortiert wird, brauch ich 13 "durchläufe" ... hab sie einzelnt aufgeschrieben, vl is das auch mit schlüsselvergleiche und bewegungen gemeint... ?

dann is im ersten unterpunktquasi die rede vom best case, das wären dann O(n) ... die komplexität is linear hier
im zweiten unterpunkt wärs dann der worst case, hier is die komplexität quadratisch, also O(n²)

das mal mein senf dazu

[davide]

schlüsselvergleich ist immer dann wenn du zwei einträge aus der liste vergleichst
bewegung ist immer dann wenn du einen eintrag in der liste verschiebst

du musst in deinen 13 durchläufen also jeweils mitzählen wie oft verglichen, und wie oft bewegt wird, und das am ende zusammenaddieren

[gonzo69]

besten dank, jetzt is alles klar

[manül]

bewegung ist immer dann wenn du einen eintrag in der liste verschiebst
Meiner Meinung nach auch wenn du einen Schlüssel kopierst. Zumindest steht das auch so im Skriptum auf Seite 26, vorletzter Absatz. Auch wenn das bei großen Folgen nicht ins Gewicht fällt, soll man es wohl bei der Angabe mitzählen bzw. berechnen. Also Zeile 2 und 9 mit zählen.

Ergibt bei mir C=20, M=29.
C(Best)=n-1=7, M(Best)=2(n-1)=14
C_{Worst}= \sum^{n-1}_{i=0}i = \frac{n(n-1)}{2} = 28
M_{Worst}= 2(n-1) + \frac{n(n-1)}{2} = 42

[babs80]

für den best case = sortierte reihenfolge

lt skriptum findet ein schlüsselvergleich in der zeile 5 statt: dh ich hab im best case 7 vergleiche

datenbewegungen finden in zeile 2,6,9 statt - damit komm ich im best case auf 14 bewegungen (7 in zeile 2, 0 in zeile 6, 7 in zeile 9)

müssen wir nur den best/worst case analysieren - oder auch den fall, wenn die liste so aussieht wie in der angabe?

[babs80]

Meiner Meinung nach auch wenn du einen Schlüssel kopierst. Zumindest steht das auch so im Skriptum auf Seite 26, vorletzter Absatz. Auch wenn das bei großen Folgen nicht ins Gewicht fällt, soll man es wohl bei der Angabe mitzählen bzw. berechnen. Also Zeile 2 und 9 mit zählen.

Ergibt bei mir C=20, M=29.
C(Best)=n-1=7, M(Best)=2(n-1)=14
C_{Worst}= \sum^{n-1}_{i=0}i = \frac{n(n-1)}{2} = 28
M_{Worst}= 2(n-1) + \frac{n(n-1)}{2} = 42

bei M(worst) komm ich auch auf 42

C(worst) hab ich so gerechnet:

C_{Worst}= \sum^{n}_{j=2}j = \frac{n(n+1)}{2} -1 = 35

[manül]

oder auch den fall, wenn die liste so aussieht wie in der angabe?
auch die liste. aber abzählen.


C(worst) hab ich so gerechnet: C_{Worst}= \sum^{n}_{j=2}j = \frac{n(n+1)}{2} -1 = 35
Die Laufzeit der Zeile 5 darfst nicht verwenden, da wird auch i gecheckt. Musst Zeile 6 nehmen.

[Pmed++]

Wenn man es aber nach Insert Sort sortiert komme ich auf 7 Vergleiche und 5 Bewegungen. Ich habs öfters durchsortiert aber komm auf die gleichen Ergebnisse.

[Dunderdon]

Wieso schreibt ihr hier alle Summen, deren Indizes nicht im betreffenden Term vorkommen :confused:

Pmed: Bedenke, dass
* ein (einfacher) Tausch drei Schlüsselbewegungen sind,
* In Zeile 2 und Zeile 9 auch je eine Schlüsselbewegung stattfindet
* Jede Zahl mit allen Zahlen, die links von ihr stehen und größer sind plus einer verglichen werden muss.

So müsste man das eigentlich lösen können, ohne den Algorithmus ganz zurchzulaufen, oder? :devil:

Moment, es muss ja jedes mal auch i > 0 überprüft werden:distur:


Edit 2:

Seite 26 im Skriptum steht: "Dereinzige Schlüsselvergleich findet in Zeile 5 statt" und "Datenbewegungen gibt es in den Zeilen 2, 6 und 9".

Das heißt alle Vergleiche und Bewegungen mit i und j zählen nicht.

Wir haben also:
* Pro Zahl so viele Vergleiche, wie größere Zahlen links von ihr stehen (maximal aber so viele wie links von ihr stehen)
* Pro Zahl so viele Bewegungen, wie größere Zahlen links von ihr stehen plus zwei

Das ergibt bei mir 22 Vergleiche und 30 Bewegungen.

[manül]

Das ergibt bei mir 22 Vergleiche und 30 Bewegungen.

Ich unterstütz jetzt mal meine Werte mit bisserl Code:

#!/usr/bin/perl

use Data::Dumper;
use strict;

my @a = (50, 60, 12, 45, 101, 18, 1, 67);

my $i;
my $cmp = 0;
my $mv = 0;
for(my $j = 1; $j < scalar(@a); $j++)
{
my $key = $a[$j];
$mv++;
$i = $j - 1;
while($i >= 0 && ($cmp++) && $a[$i] > $key)
{
$a[$i + 1] = $a[$i];
$mv++;
$i = $i - 1;
}
$a[$i + 1] = $key;
$mv++;
}
print Dumper(@a);

print "keycnt=", scalar(@a), " moves=", $mv, " keycmp=", $cmp, $/;ergibt: keycnt=8 moves=29 keycmp=20

[Dunderdon]

Sollte das nicht heißen i>0 statt i>=0 ?

[manül]

Sollte das nicht heißen i>0 statt i>=0 ?
Indizes fangen in Perl bei 0 an. Net bei 1 :)
Aber ich hab die selben Werte auch beim händischen abzählen bekommen.

[Dunderdon]

Ähm.. ja du hast mit deinen Werten Recht :hail:

Aber es funktioniert auch mit meiner Methode, vorausgesetzt man verzählt sich nicht. :hewa:

[symm3try]

kurze frage,
wie kommt ihr eigentlich auf 13 durchläufe ? wenn ichs mir aufzeichne dann bekomm ich 8 zeilen :confused:

[babs80]

auch die liste. aber abzählen.


Die Laufzeit der Zeile 5 darfst nicht verwenden, da wird auch i gecheckt. Musst Zeile 6 nehmen.

warum muss ich zeile 6 nehmen - hier findet ja gar kein schlüsselvergleich statt sondern nur eine zuweisung...

[manül]

warum muss ich zeile 6 nehmen - hier findet ja gar kein schlüsselvergleich statt sondern nur eine zuweisung...
In Zeile 5 wird auch i gecheckt, daher fällt die Laufzeit dieser Zeile schon mal weg. Zeile 6 deshalb, weil im Worst-Case jedesmal verschoben werden muss, also der Key-Vergleich stimmt nie.

[babs80]

kurze frage,
wie kommt ihr eigentlich auf 13 durchläufe ? wenn ichs mir aufzeichne dann bekomm ich 8 zeilen :confused:

so ich hab die grafik eigentlich so wie du ...

überlege nur wie ich richtig abzähle:

schlüsselvergleiche:

also ich nehm mal zeile 1 her: ich schau mir 60 an und merke dass es grösser als 50 ist - dh ein schlüsselvergleich

zeile 2: ich muss mit 60 und 50 vergleichen + einmal wird noch die schleife durchlaufen - aber da seh ich, dass ich schon am linken rand angekommen bin - deswegen abbruch

zählt das als dritter schlüsselvergleich oder nicht???

zeille 3: vergleiche mit 60, 50 und 12 - dh ich brauche drei schlüsselvergleiche um zu sehen, wo ich meine 45 einfügen muss

datenbewegungen:

zeile 1: 2 datenbewegungen (komme in die for-schleife - aber nicht in die solange schleife)
zeile 2: habe wieder 2 datenbewegungen + 2 datenbewegungen aus der inneren schleife durch die verschiebungen...

[Augilandum]

Hi, hab das Gleiche wie symm3try und komme auf 20 Vergleiche und 15 Verschiebungen.
Weiß nicht ob wenn i=0 in der Schleife auch als Vergleich zählt.

[babs80]

Hi, hab das Gleiche wie symm3try und komme auf 20 Vergleiche und 15 Verschiebungen.
Weiß nicht ob wenn i=0 in der Schleife auch als Vergleich zählt.

welche zeile meinst du genau?

wenn es zeile 5 ist denke ich schon - hier wird ja nur überprüft ob die bedingung zutrifft - wenn nicht dann abbruch....

schlüsselvergleiche

zeile 1: 1 (vergleich von 60 u 50)
zeile 2: 3 (vergleich von 12 mit 50 und 60 + ein vergleich wo rauskommt, daß man links ansteht - weiss nicht ob das mitgezählt werden muss - aber denke die programmzeile wird komplett ausgeführt, auch wenn die erste bedingung schon nicht erfüllt ist)
zeile 3: 3 (vergleich mit 60 u 50)
zeile 4: 5 (vergleich mit 101,60,50,45,12)
zeile 5: 1 (vergleich mit 60)
zeile 6: 7 (vergleich mit 101,60,50,45,18,12 + man ist schon wieder am linken rand, wo ich nicht weiss ob das mitgezählt werden muss)
zeile 7: 2 (vergleich mit 101,60)
zeile 8: 0 kein vergleich mehr, da die for schleife abbricht...

damit komm ich auf 22 schlüsselvergleiche
ohne die vergleiche wo ich schon "am linken rand anstehe" sind es 20

datenbewegungen:

zeile 1: 2 (zeile 2 + 9 vom pseudocode werden durchlaufen)
zeile 2: 2 (für zeile 2 + 9) + 2 für den solange-schleifendurchlauf
zeile 3: 2+2
zeile 4: 2+4
zeile 5: 2
zeile 6: 2+6
zeile 7: 2 + 1
zeile 8: 0

damit komm ich auf 29 datenbewegungen

[symm3try]

schlüsselvergleiche

zeile 1: 1 (vergleich von 60 u 50)
zeile 2: 3 (vergleich von 12 mit 50 und 60 + ein vergleich wo rauskommt, daß man links ansteht - weiss nicht ob das mitgezählt werden muss - aber denke die programmzeile wird komplett ausgeführt, auch wenn die erste bedingung schon nicht erfüllt ist)
zeile 3: 3 (vergleich mit 60 u 50)
zeile 4: 5 (vergleich mit 101,60,50,45,12)
zeile 5: 1 (vergleich mit 60)
zeile 6: 7 (vergleich mit 101,60,50,45,18,12 + man ist schon wieder am linken rand, wo ich nicht weiss ob das mitgezählt werden muss)
zeile 7: 2 (vergleich mit 101,60)
zeile 8: 0 kein vergleich mehr, da die for schleife abbricht...

damit komm ich auf 22 schlüsselvergleiche
ohne die vergleiche wo ich schon "am linken rand anstehe" sind es 20

datenbewegungen:

zeile 1: 2 (zeile 2 + 9 vom pseudocode werden durchlaufen)
zeile 2: 2 (für zeile 2 + 9) + 2 für den solange-schleifendurchlauf
zeile 3: 2+2
zeile 4: 2+4
zeile 5: 2
zeile 6: 2+6
zeile 7: 2 + 1
zeile 8: 0

damit komm ich auf 29 datenbewegungen



ja das hört sich schon mal gut an :) komm aufs gleiche.
bin mir zwar auch net sicher, ob man das ankommen am linken rand mitzählt...
aber ich glaube, dass das nicht als schlüsselvergleich zählt.

in jeder zeile ( außer der letzen ) gibt es 2 datenbewegungen (-->wegen codezeile 2 u. 9) .... und die restlichen bewegungen (=die bewegungen, die in der while schleife stattfinden) ergeben sich durch die anzahl der "nach rechts rutschenden" elemente. unterm strich wären das dann 29 datenbewegungen :)

@babs ich glaub du hast die zeile 5 und 4 vertauscht...

[Augilandum]

Hi!
Würde auch sagen das die Zeilen 4 und 5 vertauscht sind. Hab mir den Rest des Bsp angesehen und komme im Best Case (alle schon geordnet) auf 7 Vergleiche und 14 Verschiebungen.
Im Worst Case (absteigend geordnet) auf 28 Vergleiche und 42 Verschiebungen.

[Troy]

Ich glaub nicht, dass "i>0" als Vergleich zählt, bloß "A[i] > key", da ja nur Schlüsselvergleiche gefragt sind und nicht allgemeine Vergleiche.

[gonzo69]

Hi!
... komme im Best Case (alle schon geordnet) auf 7 Vergleiche und 14 Verschiebungen.
Im Worst Case (absteigend geordnet) auf 28 Vergleiche und 42 Verschiebungen.

best case kommich auch auf das ... beim worst case komm ich aber auf 28 vergleiche, wie du, aber auf 35 verschiebungen ? habs aufgezeichnet, glaub nicht dass ich mich verzählt hab ... was könnt mir fehlen?