Komme bei folgender Aufgabe nicht wirklich weiter
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?
Überlegen Sie sich ein Eingabearray der Länge n, das diesem Worst Case entspricht, und geben Sie die Anzahl der für das Sortieren erforderlichen Rechenoperationen als Funktion / Formel von n an.
b) Geben Sie für ein Array des oben skizzierten Typs einen Sortieralgorithmus an, der das Sortieren in O(n) Rechenschritten schafft
Komme bei folgender Aufgabe nicht wirklich weiter
Hi,
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?
Überlegen Sie sich ein Eingabearray der Länge n, das diesem
Worst Case entspricht, und geben Sie die Anzahl der für das
Sortieren erforderlichen Rechenoperationen als Funktion /
Formel von n an.
Worst case z.B. Array a{1,0,0,0,0,0,0}
n^2
http://de.wikipedia.org/wiki/Insertionsort
b) Geben Sie für ein Array des oben skizzierten Typs einen
Sortieralgorithmus an, der das Sortieren in O(n)
Rechenschritten schafft
z.B. Bubblesort http://de.wikipedia.org/wiki/Bubblesort
Gruß.Timo
Komme bei folgender Aufgabe nicht wirklich weiter
Hi,
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?
Überlegen Sie sich ein Eingabearray der Länge n, das diesem
Worst Case entspricht, und geben Sie die Anzahl der für das
Sortieren erforderlichen Rechenoperationen als Funktion /
Formel von n an.
Worst case z.B. Array a{1,0,0,0,0,0,0}
n^2
GEnau hier leigt mein Problem „::Überlegen Sie sich ein Eingabearray der Länge n, das diesem
Worst Case entspricht, und geben Sie die Anzahl der für das
Sortieren erforderlichen Rechenoperationen als Funktion /
Formel von n an.“
Wie mache ich das??
http://de.wikipedia.org/wiki/Insertionsort
b) Geben Sie für ein Array des oben skizzierten Typs einen
Sortieralgorithmus an, der das Sortieren in O(n)
Rechenschritten schafft
z.B. Bubblesort http://de.wikipedia.org/wiki/Bubblesort
Gruß.Timo
Komme bei folgender Aufgabe nicht wirklich weiter
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.
Einser zählen, löschen und von vorne Anzahl Einser
reinschreiben. Fertig. 
Alex