Insertion sort

[MUPI]

Kann mir jemand sagen was die maximale und die durchschnittliche vergleichzahl von insertion sort ist?

schonmal im vorraus danke für die hilfe

 

[maki]

Google?

http://www.google.com.au/search?num=50&hl=en&safe=off&q=insertion+sort&btnG=Search&meta=

 

[MUPI]

hab ich nachgeschaut...da hab ich nix dazu gefunden..wenn du was findest sag es mir..lass mich gerne eines besseren belehren.... aber ich hab nix gefunden....

 

[maki]

Klick doch mal den Link bevor du sagst da es da nix gibt... der erste Treffer beantwortet deine Fragen schon.

 

[MUPI]

ja..wie lauten denn die zahlen? ich find da nix..

danke

 

[MUPI]

ich sag doch...da findet man nix...ihr habt anscheinend auch nix gefunden..nicht böse gemeint..aber sieht halt danach aus...

 

[masta // thomas]

Im best case linear, also O(n). Im worst case quadratisch, O(n^2).

Du willst doch jetzt nicht wirklich konkrete Zahlen hören?

 

[MUPI]

also ist das so zusagen die formel...also wenn es konkrete zahlen gibt dafür,dann schon.....wenn nicht,dann nicht...

 

[masta // thomas]

Nein, gibt es nicht. Das kommt immer drauf an, wieviele Werte sortiert werden. Einmal über Sortieralgorithmen informieren, bitte

 

[MUPI]

danke...vielen dank

 

[Marco13]

Najaa.....

Wenn man sich die Frage mal ansieht:
Kann mir jemand sagen was die maximale und die durchschnittliche vergleichzahl von insertion sort ist?

Eine vollständige und richtige Antwort auf diese Frage ist: "JA". Aber Selbst wenn die Frage gewesen wäre
"Was ist die maximale und die durchschnittliche Vergleichzahl von InsertionSort?"
wäre die beantwortung der Frage nicht so einfach, wie es sich die bisherigen Antworter gemacht haben.

Die Frage war ja nicht
"Was ist die asymptotische Worst- und Average-Case-Laufzeit von Insertion Sort?"

Die tatsächliche Anzahl für den average case ist ein bißchen diffizil, aber für den worst case ist sie ja vielleicht sowas wie 3n^2+2n+4 oder so... (Ich WEISS die genaue Anzahl nicht. Ich weiß aber, dass ich sie herausfinden könnte. Ist aber nicht meine Aufgabe :wink: )

 

[masta // thomas]

Deine Antwort würde trotzdem eine Unbekannte enhalten, somit gäbe es keine konkrete Zahl

 

[Marco13]

Klar. Aber ... in diesem Sinne: Wenn man jetzt ein Array mit 10 Elementen hat, wieviele Vergleiche werden dann im Worst case durchgeführt? O(100) = O(1) :wink: Ich denke, es eht um etwas, woraus man (bei gegebener Arraygröße) die genaue Zahl ausrechnen kann......

 

[SlaterB]

es wurde doch ziemlich genau das geantwortet, was du haben wilst:
> Im worst case quadratisch, O(n^2).

genau so eine Formel wie von dir genannt ("für den worst case ist sie ja vielleicht sowas wie 3n^2+2n+4 oder so")

was versuchst du also noch nachzuhaken?