Hilfe beim Ansatz für folgendes Aufgabe

Wissenschaft Informatik
#1

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

#2

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

#3

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

#4

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. :wink:

Alex