Sortieralgorithmen

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
Zwei sehr unterschiedliche Sortierverfahren im Vergleich:

<code id="5b1e50a5b44ed">
// Eine Liste mit 10 zufällige Zahlen soll aufsteigend sortiert werden
var Liste = [
  81, 98, 73, 80, 3, 56, 65, 42, 97, 3
];
var AnzahlVersuche = 0;
</code>

== Bogo Sort ==
Es wird solange zufällige sortiert, bis die Liste geordnet ist.

<run id="5b1e50a5b4595">
function BogoSort(a){
  while(true){
    AnzahlVersuche++;
    // zufällig ordnen
    for(var i =0; i < a.length; i++){
      var rand = Math.floor(Math.random() * a.length);
      var tmp = a[i]; 
      a[i] = a[rand]; 
      a[rand] = tmp;
    }    // auf geordnet überprüfen
    var geordnet = true;
    var zuletzt = -1;
    for(var i=0; i < a.length; i++){
      if(zuletzt > a[i]) {
        geordnet = false; 
        break;
      }
      zuletzt = a[i];
    }
    // wenn geordnet, beenden, sonst nochmal probieren
    if(geordnet) return; 
  }
}

var start = new Date();
BogoSort(Liste);
console.log(Liste);
var ende = new Date();
console.log("Zeit: "+(ende.getTime() - start.getTime())+ " ms in "+AnzahlVersuche+" Versuchen.");
</run>

Bereits bei 10 Elementen dauert die Suche sehr lange. Bei 10 Elementen ergeben sich 3‘628‘800 mögliche Listen (Varianten) wovon genau 1 die richtige Lösung darstellt (wenn keine Zahlen doppelt vorhanden sind).
Wieviel Varianten gäbe es dann bei 100 Elementen in der Liste? (Lösung: 9.3e+157).

== Sortieren als allgemeines Problem ==
Bei Zahlen können wir mit einem Blick abschätzen, ob die Sortierung funktioniert hat. Nehmen wir für uns eher unbekannte Daten, wird das schon schwieriger. Im Folgenden wird das russische Alphabet verwendet und erneut 10 zufällige Buchstaben daraus in eine Liste gelegt. Die Liste soll nun aufsteigend nach dem Alphabet sortiert werden. Erfinde einen Sortieralgorithmus dafür.

<code id="5b1e5be84b60d">
var russischesAlphabet = [
  "а", "б", "в", "г", "д", "е", "ё", "ж", "з", "і", "й", "к", "л", "м", "н", "о", 
  "п", "р", "с", "т", "у", "ў", "ф", "х", "ц", "ч", "ш", "ы", "ь", "э", "ю", "я"
];

var russischeListe = ["с", "ц", "ф", "ы", "ш", "й", "з", "у", "я", "н"];
</code>

<run id="5b1e5be84b684">
function Sortieren(a){
  // schreibe hier deinen Algorithmus, der die Liste a alphabetisch ordnet
}

var start = new Date();
Sortieren(russischeListe);
console.log(russischeListe);
var ende = new Date();
console.log("Zeit: "+(ende.getTime() - start.getTime())+ " ms.");
</run>