Dein Fortschritt:
0 / 0 Aufgaben
1
Startliste im Schwimmverein
AFB I–IIEin Schwimmverein speichert die 50-m-Zeiten (in Sekunden) von sechs Schwimmerinnen in der Reihung zeiten. Für die Startliste sollen die Zeiten aufsteigend sortiert werden; dazu wird die Grundversion von Bubblesort verwendet.
Reihung zeiten vor dem Sortieren
- Beschreiben Sie das Vorgehen von Bubblesort in einem Durchlauf und nennen Sie, was nach dem k-ten Durchlauf über die Reihung feststeht.
- Stellen Sie die Belegung von
zeitennach jedem der fünf Durchläufe in einer Tabelle dar und notieren Sie jeweils die Anzahl der Vertauschungen. - Leiten Sie eine Formel für die Anzahl der Vergleiche der Grundversion bei n Elementen her und geben Sie den Wert für diese Reihung an.
- Erläutern Sie am Ergebnis aus b), wie eine Variante mit einer booleschen Variable
getauschtArbeit einsparen kann, und geben Sie an, wie viele Vergleiche sie hier benötigt.
Hinweise
Hinweis zu Aufgabe a)
Achten Sie auf zwei Dinge: welches Paar jeweils verglichen wird und wohin das größte Element wandert.
Hinweis zu Aufgabe b)
Beginnen Sie jeden Durchlauf bei Index 0 und vergleichen Sie nur bis zur Grenze des unsortierten Teils. Der fünfte Durchlauf vergleicht nur noch ein Paar.
Hinweis zu Aufgabe c)
Durchlauf 1 vergleicht n − 1 Paare, jeder weitere eines weniger. Schreiben Sie die Summe einmal vorwärts und einmal rückwärts.
Hinweis zu Aufgabe d)
Suchen Sie in Ihrer Tabelle den ersten Durchlauf ohne Vertauschung.