Sortieralgorithmen

Aus ProgrammingWiki

Archivierte Version vom 2018-06-11T11:33:47+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, 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.");

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

Quick Sort

function QuickSort(a) {
  if (a.length <= 1) return a;
  var zufall = Math.floor(Math.random()*a.length);
  var wert = a[zufall];
  
  var links = []; 
  var rechts = [];

  for (var i = 0; i < a.length; i++) {
    if(i == zufall) continue; // überspringen
    if(a[i] < wert) links.push(a[i]); else rechts.push(a[i]);
  }

  return QuickSort(links).concat(wert, QuickSort(rechts));
};

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

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.

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

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

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