Übungsaufgabe algorithmen

[Heyoka955]

hallo liebe Community, ich bin neu hier und habe mich angemeldet weil ich dachte man könne mir mit den uni Stoff helfen. Also ich hack an einer Aufgabe und weiß nicht wie es geht.
Die Aufgabe ist man soll einen Algorithmus mit linearer Laufzeiten(n) in Pseudo Code schreiben ( am besten an c oder Java orientiert) und man kriegt ein Array übergeben wo man n Elemente sortieren muss aber Achtung die Elemente bestehen nur aus 0, 1 und 2. also

Bsp A [ 0,0,0,0,2,,2,2,1]
Hoffe ihr habt die Frage verstanden und könnt helfen. Ich weiß nur das man das mit 2 for schleifne lösen knn aber keine verschachtelte und außerdem muss man die tausch Operation anwenden.

Also es wäre gut wenn ihr mir das so erklärt dass es ein Anfänger versteht danke lm vorausb

 

[MoxxiManagarm]

Das geht nur wenn du dich entschieden hast welchen Sortalgorithmus du verwenden willst. Ein Entscheidungsträger ist dir dabei vorgegeben.
Entscheide dich hier: https://de.wikipedia.org/wiki/Sortierverfahren

Wenn du dich entschieden hast verinnerliche was der Algorithmus tut. Ich denke der Pseudocode geht dir dann fast von Hand.

 

[mihe7]

Ich weiß nur das man das mit 2 for schleifne lösen knn aber keine verschachtelte und außerdem muss man die tausch Operation anwenden.

Du kennst zu jedem Zeitpunkt den Anfang (Index) des noch unsortierten Arrays. D. h. es gibt einen Index ix, der das Array in einen sortierten und einen unsortierten Bereich einteilt. Invariante: alle Elemente, die im Array vor diesem Index stehen, sind bereits sortiert. Zu Beginn ist dieser Index 0, da es noch keine sortierten Elemente gibt.

Jetzt kannst Du in einer Schleife jedes Element mit 0 vergleichen. Hast Du eine 0 gefunden, vertauschst Du dieses Element mit dem Element an Position ix. Damit hast Du die 0 nach vorne gezogen und das Array ist jetzt bis einschließlich ix sortiert. Um die Invariante wieder herzustellen, musst Du ix einfach um 1 erhöhen.

Nach der Schleife stehen alle 0en am Anfang des Arrays. Den Spaß wiederholst Du (Invariante beachten) für die 1 und das Thema ist erledigt.