Informatik Abituraufgabe Erklärung

Informatik Abituraufgabe Erklärung

Abitur 2022, Teil III

Aufgabe 4a), b)

 
            Methode sortieren(array)
                n = array.länge
                wiederhole solange n größer 1
                    i=0
                    tauschen = falsch
                    wiederhole solange i kleiner n − 1
                        wenn array[i] größer array[i + 1] dann
                            c = array[i]
                            array[i] = array[i + 1]
                            array[i + 1] = c
                            tauschen = wahr
                        endeWenn
                        i=i+1
                    endeWiederhole
                    wenn tauschen gleich falsch dann
                        beende sortieren
                    endeWenn
                    n=n−1
                endeWiederhole
            endeMethode
        

→ Bubblesort Algorithmus

Schrittweise Ausführung bei folgender Zahlenreihe:  8756 

• 8
• 7
• 6
• 5

• 7
• 8
• 6
• 5

• 7
• 6
• 8
• 5

• 7
• 6
• 5
• 8

• 6
• 7
• 5
• 8

• 6
• 5
• 7
• 8

• 5
• 6
• 7
• 8

• 5
• 6
• 7
• 8

Feld ist aufsteigend, da

• größere Werte nach rechts verschoben werden
• kleine Werte links, Große Werte rechts
→ aufsteigend

Laufzeiten?

1. Günstigster Fall: Werte schon vorsortiert

• Äußere Schleife: Nur einmal
• Innere Schleife: n-1 mal

→ Laufzeitverhalten: Linear mit n-1

Laufzeiten?

2. Ungünstigster Fall: Werte falschherum sortiert

Äußere Schleife: 1-n mal

Innere Schleife: jedes Mal: (n-1)-1

Bsp: (n-1) + (n-2) + (n-3) + ... + (n-(n-1))

Andersherum: 1 + 2 + 3 + ... + n-1

→ Laufzeitverhalten: Laut Lösung quadratisch?