Algorithmus entwickeln und implementieren

Die Aufgabenstellung

Entwickeln Sie einen Algorithmus, der ...
Implementieren Sie den Algorithmus.

ist im Zentralabitur sehr häufig. In der Regel gibt es für die Entwicklung des Algorithmus 40% der Punkte und für die Implementierung 60%.

Auf dieser Seite werden Beispiele gegeben, wie man die Aufgabe angehen kann.

Hinweis:
Am SIBI darf man den Algorithmus mit Spiegelstrichen entwickeln; es müssen keine ganzen Sätze formuliert werden.
Die Darstellung des Algorithmus muss aber verständlich sein, ohne dass man die Implementierung anschaut!

Beispiel 1: Sortieren durch Einfügen

Aufgabenstellung:
Gegeben ist eine Liste teilnehmerListe, die Objekte vom Typ Person enthält.
Diese Liste soll mit dem Insertionsort-Verfahren nach dem Namen der Personen sortiert werden.

1. Entwickeln Sie einen Algorithmus, der teilnehmerListe nach dem Namen sortiert.
2. Implementieren Sie den Algorithmus.

Lösung Entwickeln Sie einen Algorithmus...

Zwei Methoden:

• Hilfsmethode anRichtigerStelleEinfügen
• Hauptmethode insertionSort

Hilfsmethode anRichtigerStelleEinfuegen:

• fügt eine Person an alphabetisch richtigen Stelle in eine Liste ein.
• Die Parameter sind eine Liste pList, in die eingefügt werden soll, und pPerson, die einzufügende Person.
• pList mit einer Schleife durchlaufen.
  • Wenn pPerson im Alphabet VOR der Person ist, auf die der Listenzeiger steht,
    dann pPerson mit insert VOR dem aktuellen Element einfügen
    und die Methode verlassen.
• Wenn das Ende der Schleife erreicht wurde, dann pPerson hinten anhängen.

Hauptmethode insertionSort:

• kein Parameter, gibt eine sortierte Liste zurück.
• eine leere Liste ergebnis erzeugen.
• teilnehmerListe mit einer Schleife durchlaufen.
  • für jede Person in der Liste die Hilfsmethode anRichtigerStelleEinfuegen aufrufen, um sie an die richtige Stelle in ergebnis einzufügen.

Lösung: Implementieren Sie den Algorithmus.

  private List<Person>teilnehmerListe;
  
  public List<Person> insertionSort(){
       List<Person> ergebnis = new List<>();
       teilnehmerListe.toFirst();
       while(teilnehmerListe.hasAccess()){
           Person aktuell = teilnehmerListe.getContent();
           anRichtigerStelleEinfugen(ergebnis, aktuell);
           teilnehmerListe.next();
       }
       return ergebnis;
  }
   
  public void anRichtigerStelleEinfugen(List<Person> pList, Person pPerson){
       pList.toFirst();
       while(pList.hasAccess()){
           Person aktuell = pList.getContent();
           // pPerson mit der aktuellen person vergleichen
           if(pPerson.getName().compareTo(aktuell.getName()) < 0){
               pList.insert(pPerson);
               return;
           }
           pList.next();
       }
       // pPerson wurde noch nicht eingefuegt!
       pList.append(pPerson);
   }