Sortieralgorithmen

Aus ProgrammingWiki

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, 8
];
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;

  // zufälliges Element auswählen
  var zufall = Math.floor(Math.random()*a.length);
  var wert = a[zufall];
  
  // verbleibende Elemente in kleinere und grössere Aufteilen
  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]);
  }

  // die sortierten Teillisten wieder zusammenfügen 
  return QuickSort(links).concat(a[zufall], 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 russischen Alphabet sortiert werden. Wir erfinden eine Sortierfunktion, die eine Liste mit Werten und ein Alphabet entgegennimmt. Damit haben wir eine allgemeine Sortierfunktion, die für beliebige Alphabete funktioniert.

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

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

function Sortieren(a,alphabet){
  if (a.length <= 1) return a;

  // zufälliges Element auswählen
  var zufall = Math.floor(Math.random()*a.length);
  var wert = alphabet.indexOf(a[zufall]);
  
  // verbleibende Elemente in kleinere und grössere Aufteilen
  var links = []; 
  var rechts = [];

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

  // die sortierten Teillisten wieder zusammenfügen 
  return Sortieren(links,alphabet).concat(a[zufall], Sortieren(rechts,alphabet));
};

var start = new Date();
russischeListe = Sortieren(russischeListe,russischesAlphabet);
console.log(russischeListe);
var ende = new Date();
console.log("Zeit: "+(ende.getTime() - start.getTime())+ " ms.");

Noch mal ein Beispiel mit einem anderen Alphabet:

var deutschesAlphabet = [
  "a","b","c","d","e","f","g","h","i","j","k","l","m","n",
  "o","p","q","r","s","t","u","v","w","x","y","z"
];
var deutscheListe = ["x","a","c","f","q","l","u","k","v","m"];

deutscheListe = Sortieren(deutscheListe,deutschesAlphabet);
console.log(deutscheListe);

Natürlich könnten wir auch ein Zahlenalphabet aufschreiben

var zahlenAlphabet = [
  "1","2","3","4","5","6","7","8","9","10",
  "11","12","13","14","15","16","17","18","19","20"
];
var zahlenListe = ["3","12","16","8","7","1","10","5","9","18"];

zahlenListe = Sortieren(zahlenListe,zahlenAlphabet);
console.log(zahlenListe);