Letzte Änderung: 01.09.2015 18:20 Uhr

Valid HTML 4.01! Valid CSS!

www.brain4.de > Scripts and more... > JavaScript: Elemente eines Array mischen  

Elemente eines Array mischen

Download Day - German

Im Gegensatz zum Sortieren eines Array sucht man beim Array-Objekt lange nach einer Methode "shuffle()". Man kann sich jedoch eine solche Methode selbst schreiben und sie dann dem Array-Objekt am Besten via prototyping zuordnen.

Der hier vorgestellte Algorithmus arbeitet nach folgende Maßgaben:

Der Algorithmus hat zur Folge, dass jedes Element mindestens einmal vertauscht und an eine zufällig ausgewählte Position gesetzt wird. Allerdings kann ein Element dabei auch mehrfach vertauscht werden, was den Algorithmus dagegen sicher nicht schwächer macht.
Das Script dazu sieht folgendermaßen aus:

function arrayShuffle(){
  var tmp, rand;
  for(var i =0; i < this.length; i++){
    rand = Math.floor(Math.random() * this.length);
    tmp = this[i]; 
    this[i] = this[rand]; 
    this[rand] =tmp;
  }
}

Array.prototype.shuffle =arrayShuffle;

Durch zuweisen dieser Funktion an den Array Prototypen, lässt sich jedes Array durch arrayInstance.shuffle() mischen. Beispiel:

var zahlen = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
zahlen.shuffle();

var ausgabe = zahlen.join(", ");
alert(ausgabe);

Die Performance ist natürlich abhängig vom Rechner, auf dem diese Methode ausgeführt wird. Vor einigen Jahren (ich denke es war 2002) habe ich einen Performance-Test auf einem AMD K6/2 mit 128 MB RAM ausgeführt. Die Ergebnisse damals lauteten:

# Arrayeinträge MSIE 5.5 [Win95] NN 4.6 [Win95] Opera 6.0 [Win95] Mozilla 0.97 [Win95]
Test auf einem AMD K6/2 mit 128 MB RAM
50050 ms110 ms270 ms160 ms
5.000110 ms550 ms1.820 ms1.380 ms
10.000330 ms1.480 ms4.670 ms2.750 ms
50.0001.650 ms7.750 ms23.780 ms14.120 ms

2005 habe ich den Test wiederholt:

# Arrayeinträge MSIE 5.5 [Win2k] Firefox [Linux] Opera 8.5 [Linux] Konquerer 3.4 [Linux]
Test auf einem AMD Athlon(tm) XP 2600+ mit 512 MB RAM
500--2 ms1 ms7 ms
5.000--22 ms23 ms63 ms
10.000--69 ms44 ms125 ms
50.000--484 ms236 ms1095 ms

Das Skript zum Performance-Test auf dem eigenen Rechner steht auch zur Verfügung.

Die hier vorgestellte Lösung wurde von mir am 30. Juni 2000 in der Newsgroup dcljs gepostet und von Thomas Fischer in diese Form gebracht. Das Original findet sich unter der Msg. Id <8ji56q$llhh$1@ID-19598.news.cis.dfn.de>

zur Navigation