Sortieralgorithmen

Aus ProgrammingWiki

Archivierte Version vom 2018-06-11T11:07:22+00:00. Aktuelle Version

Zwei sehr unterschiedliche Sortierverfahren im Vergleich:

// 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;

Bogo Sort

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

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, ergebnis zurückgeben, sonst nochmal probieren
    if(geordnet) return a; 
  }
}

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

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).