Frage zur Klausur SS2010 - Aufgabe 5 (Sortieren)

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Frage zur Klausur SS2010 - Aufgabe 5 (Sortieren)
Hallo zusammen,

kann mir irgendjemand bei der Aufgabe 5 helfen, es geht nicht um die Beantwortung (mir ist klar das es ein Bubblesort ist :slight_smile: sondern warum es keinen unterschied macht ob in der 2. for-Schleife im Kopf ++i oder i++ steht. Beide Male ist der erste Wert den i hat 0, was doch eigentlich nicht stimmen kann, denn wenn “++i” gilt wird doch i sofort auf 1 gesetzt, was zur Folge hätte das i niemals 0 wäre…

Vielen vielen Dank schonmal :slight_smile:

3

das i++ / ++i, wird erst am ende des Schleifenrumpfs ausgeführt, daher ist es augenscheinlich erstmal egal was man nimmt.
Warum ++i i++ vorzuziehen ist mach mer dann im kommenden Semester in GRa :wink:

4

Das wird wahrscheinlich klarer, wenn du dir vorstellst, wie so eine Schleife abgearbeitet wird:

Eine for-Schleife sieht ca. so aus:
[m]for ([/m]Initialisierung[m];[/m] Abbruchbedingung[m];[/m] Nachbehandlung[m]) {[/m]
body…
[m]}[/m]

transformiert in while der gleiche Code:
Initialisierung
[m]while ([/m]Abbruchbedingung[m]) {[/m]
body…
Nachbehandlung
[m]}[/m]

Die Nachbehandlung wird also immer nach Bearbeitung des Schleifenrumpfes durchgefuehrt. Ob da [m]i++[/m] oder [m]++i[/m] steht, ist egal: in beiden Faellen wird i um 1 erhoeht, in keinem Fall wird die Initialisierung von i veraendert.

5

Alles klar, danke :slight_smile:

6

Weil der Compilerbauer versagt hat?

7

Meistens ja, gelegentlich ist aber auch die Sprachspezifikation ausreichend hirntot, dass es nicht anders geht als auf die langsame bescheuerte Art ohne Optimierung.

8

Ich habe eine Frage zur 5.a.iv)

Ich meine der worst-case in eine absteigend-sortierte Reihe.
Wie soll ich das nun in einer Zeile verbessern?
Ich hätte gedacht indem ich einen Index nehme der von 0 hochzählt und einen anderen der von length nach unten zählt, damit die Zahlen am Anfang der Reihe direkt mit den Zahlen am Ende vertauscht werden.
Dies ist aber mit der Korrektur nur einer Zeile nicht zu bewerkstelligen, da im code mehrmals mit dem direkten Nachbarn i vs. i+1 verglichen wird.

if (m[i] >m[i+1]) {

int temp =m[i]; 
m[i] =m[i+1]; 
m[ i+1] = temp;
done = false ;

}
9

Du kannst die Laufzeit um die Hälfte verringern, indem man die Schritte der inneren for-Schleife nach jedem Durchlauf erniedrigt, da nach jedem Schritt der hoch-geblubberte Wert an seiner richtigen Stelle steht.
Also:
Z.14. } n–;

(siehe auch http://en.wikipedia.org/wiki/Bubblesort)