• Ein Sortierverfahren entwickeln
  • BNB
  • 27.01.2022
  • Informatik
  • Qualifikationsphase 1
Um die Lizenzinformationen zu sehen, klicken Sie bitte den gewünschten Inhalt an.

Ein Sortierverfahren entwickeln

Sortierverfahren sind zentral für viele Anwendungen in der Informatik. Manche Algorithmen wären sehr viel langsamer oder würden überhaupt nicht funktionieren, wenn die verarbeiteten Daten nicht sortiert werden könnten. Beispielsweise lassen sich bestimmte Datensätze in großen Datenmengen sehr viel schneller finden, wenn die Daten vorher in eine bestimmte Reihenfolge gebracht worden sind.

Dies ist vergleichbar mit einem Telefonbuch: Wären die Namen nicht alphabetisch sortiert, würde es sehr viel länger dauern, eine bestimmte Person zu finden.

Aufgaben

1
Der folgende Datensatz soll sortiert werden:





  • Sortiere die Buchstaben des abgebildeten Wortes aufsteigend alphabetisch (d.h. angefangen bei A usw.)

    Wichtig: Beachte dabei, dass du Schritt für Schritt und wie ein Computer vorgehst: Du kannst zur selben Zeit immer nur zwei Werte miteinander vergleichen. Außerdem kannst du stets nur einen einzigen Wert auf einmal greifen und dann bewegen. Es gibt nur die abgebildeten sechs Speicherplätze sowie einen einzigen zusätzlichen Speicherplatz zum Zwischenspeichern. Tauschen zweier Buchstaben ist also möglich, ein Auseinanderziehen-und-dazwischen-Einfügen jedoch nicht.

  • Notiere dein Vorgehen in der unten stehenden Tabelle (Schritt für Schritt):

Schritt Nr.

Was wird geprüft?
Was wird geändert?

Neue Reihenfolge der Buchstaben

1

2

3

4

5

6

7

8

9

10

2
Verallgemeinerung deines Algorithmus
  • Formuliere den von dir entwickelten Algorithmus allgemeingültig, d.h. losgelöst vom konkreten Beispiel. Notiere den Algorithmus als Pseudocode:



















  • Wende dein Pseudocode-Programm aus Teilaufgabe (2) a) auf den folgenden Datensatz an:
    Schritt 0: H A N D Y
    Schritt 1:
    Schritt 2:
    Schritt 3:
    Schritt 4:
    Schritt 5:
    Schritt 6:
    Schritt 7: ...
  • Kreuze an. Konnte der Pseudocode ohne Änderungen auch auf das zweite Beispiel angewendet werden?
    Ja
    Nein

    Falls nicht: Passe deinen Pseudocode so an, dass der darin notierte Algorithmus jede beliebige Buchstabenfolge sortieren kann (statt nur ein konkretes Beispiel).