Kursthemen

  • Sortieren von Zahlen und Wörtern

    Alles einklappen Alles aufklappen

    • Das Sortieren von Zahlen und Wörtern gehört zu den grundlegenden Algorithmen. Hier ist besonders spannend, dass es selbst bei so grundlegenden Aufgabenstellungen bereits ganz unterschiedliche Verfahren entstehen können.

      Das Sortieren von Zahlen und Buchstaben ist quasi identisch, während das Sortieren von Wörtern deutlich schwerer ist.

      Die Entwicklung einer eigenen Lösung ist eine sehr gute Übung. Es ist also sinnvoll, hierfür etas Zeit einzuplanen. Meistens hilft es bei der Entwicklung einer Lösung, wenn man die Aufgabe erst einmal händisch, also mit Papier und Bleistift, durchspielt.

  • Zahlen sortieren

    • Es soll ein Programm geschrieben werden, das die Zahlenfolge .... auf- und/oder absteigend sortiert. Auf die Verwendung von modernen Listen soll aus didaktischen Gründen verzichtet werden (es wird später noch darauf eingegangen), und lediglich einfache Arrays zum Einsatz kommen.

    • // Sortiert ein Zahlen-Array und verändert dabei das übergebene Array.
      // SelectionSort basiert auf der Idee, dass gefundene Elemente aus der Quelle gelöscht (herausgenommen) werden.
      // Dies ist intuitiv, und lässt sich unter Verwendung von "modernen" Listen recht einfach implementieren.
      // In dieser Beispiellösung sollte aber bewusst auf die modernen Listen verzichtet werden, da diese schon voll
      // objektorientiert sind
      // UND
      // da so deutlicher wird, dass die für Menschen intuitivere Lösung deutlich aufwändiger und komplexer in der Implementierung ist.
      public static void ZahlenArraySortierenMitSelectionSort(int[] liste, bool aufsteigend)
      {
          int  selIdx;
          int  zielIdx = 0;
          bool neuesGefunden;
          int  extremWert = liste[0];
          
          int[] tmpListe = new int[liste.Length];                                                     // Kopiere Quell-Array in ein temp. Array, damit später
          for(int i=0;i<liste.Length;i++)                                                             // im temp. Array gefundene Einträge "markiert" werden können.
          {
              tmpListe[i] = liste[i];
              if(aufsteigend && liste[i] > extremWert)                                                // Speichere dabei den extremsten im Array vorkommenden Wert
                  extremWert = liste[i];                                                              // ab. Bei aufsteigender Sortierung ist des der größte Wert,
              if(!aufsteigend && liste[i] < extremWert)                                               // Bei absteigender Sortierung der kleinste Wert.
                  extremWert = liste[i];
          }
          
          for(int j=0;j<liste.Length;j++)
          {
              neuesGefunden = false;
              selIdx = 0;                                                                             // Nimm an, dass das gesuchte Element zufällig schon an 
              for(int i=0;i<tmpListe.Length;i++)                                                      // Position 0 im Quell-Array steht. Bei bereits verarbeiteten
              {                                                                                       // Werten steht hier der Extremwert (siehe unten).                                                                                
                  if ( (tmpListe[i]<=tmpListe[selIdx] && aufsteigend) ||                              // Ist der Wert am aktuellen Index kleiner als der bisher
                       (tmpListe[i]>=tmpListe[selIdx] && !aufsteigend) )                              // gefundene, so speichere den Index.
                  {
                      selIdx = i;
                      neuesGefunden = true;
                  }
              }
              if(neuesGefunden)                                                                       // Falls ein neues Element gefunden wurde, so
              {                                                                                        
                  liste[zielIdx] = tmpListe[selIdx];                                                  // kopiere es an die nächste Stelle des Ziel-Arrays UND
                  tmpListe[selIdx] = extremWert;                                                      // überschreibe den gefundenen Wert im Quell-Array mit dem
                  zielIdx++;                                                                          // Extremwert, damit er bei der nächsten Durchlauf
              }                                                                                       // "übersprungen" wird.
                  
          }
      }

  • Wörter sortieren