Sortieren durch Einfügen / Algorithmus InsertionSort |
| 02.08.2006, 14:54 | 030 | Auf diesen Beitrag antworten » | ||
Sortieren durch Einfügen / Algorithmus InsertionSort
, ich hoffe mir kann jemand bei folgendem Problem weiterhelfen:Die Aufgabe lautet: In einem ungeordneten Array der Länge n mögen nur die Schlüsselwerte 0 und 1 vorkommen, nach denen das Array aufsteigend sortiert werden soll. a) Wie wirkt sich das auf das Worst-Case-Verhalten des „Sortierens durch Einfügen“ aus? (s. Kap. 3.3.3 des Moduls) Geben Sie ein Eingabearray an, das diesem Worst Case entspricht, und geben Sie die Anzahl der für das Sortieren erforderlichen Rechenoperationen an. b) Geben Sie für ein Array des oben skizzierten Typs einen Sortieralgorithmus an, der das Sortieren in O(n) Rechenschritten schafft. Meine Ansätze: a) Wie wirkt sich das auf das Worst-Case-Verhalten des „Sortierens durch Einfügen“ aus? -Die Frage verstehe ich nicht. Geben Sie ein Eingabearray an, das diesem Worst Case entspricht, und geben Sie die Anzahl der für das Sortieren erforderlichen Rechenoperationen an. -bei n=6 wäre ein WorstCaseArray so: {111000} -wie komme ich jetzt jedoch auf die Anzahl der Rechenoperationen, das sind doch einerseits die Vergleiche u. andererseits die Zuweisungen bzw. Vertauschungen??Muss man sich den Ablauf des Algorithmus komplett aufschreiben oder gibt es da einen anderen Weg das rauszubekommen? 111000 111000 111000 110100 110100 101100 101100 011100 011100 011010 011010 010110 010110 001110 001110 001101 001101 001011 001011 000111 da komme ich auf 20 "Rechenoperationen"... stimmt dasoder macht man das anders??? 
b)- dazu habe ich leider keinen Ansatz... Ich hoffe es kann mir jemand weiterhelfen... danke im voraus.... |
||||
| 02.08.2006, 15:05 | Dual Space | Auf diesen Beitrag antworten » | ||
Klingt mir sehr nach Informatik, hast du schon im Infoboard gefragt? |
||||
| 02.08.2006, 15:47 | 030 | Auf diesen Beitrag antworten » | ||
nein hab ich noch nicht, bei mir habe ich es in Mathe unter dem Thema Algorithmen (spez. Sortieralgorithmen), aber ich werd dort auch mal posten.... |
||||
| 02.08.2006, 17:10 | Dual Space | Auf diesen Beitrag antworten » | ||
Um die allgemeine Höflichkeit zu wahren , schließe ich erstmal hier. Falls sich bei den Informatikern nichts tut, schick mir eine PN und ich öffne hier wieder. *temporär geschlossen* Edit: Hier der Link zum gleichen Thread beim Infoboard: http://www.informatikerboard.de/ptopic,4...5e7fc.html#4306 |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
