Sortierung von Javascript Arrays

Live-Sortierung von HTML-Tabellen

Eine der häufigsten Arbeiten mit Arrays ist die Sortierung. Auf dieser Seite finden sie einige Hinweise zur Sortierung mit PHP.
Javascript ECMAScript für HTML und XML (Arrays)
Array.sort Sortieren einfacher Arrays
Hilfs-Funktionen Individuelles Sortieren mit Callback-Funktionen
Array.reverse Umkehrung einfacher Arrays
Mehrdimensionale Arrays Sortieren mehrdimensionaler Arrays
● Webseiten-Tabellen Interaktives (Live)-Sortieren von Tabellen
Programmierung von interaktiven HTML-Tabellen mit Javascript
Dynamischer Speicher Verwaltung von Objekten begrenzter Lebensdauer
Verwandte Themen Sortieren von Arrays in Perl, PHP

Javascript Methode Array.sort

Methode sort

Sortiert ein Array in jedem Fall .alphabetisch.
Texte (strings) werden richtig sortiert.
var t = new Array("Rita","Zara","Dora");
t.sort();
ergibt ["Dora","Rita","Zara]
Zahlen werden (ohne spezielle Maßnahmen) zur Sortierung in Texte umgewandelt und sortiert - Das ist normalerweise unerwünscht.
var z = new Array(1,5,15,25);
z.sort();
ergibt [1,15,25,5]
Zahlen als Strings konstanter Länge mit führenden Nullen
werden korrekt sortiert. Allerdings müssen alle Zahlen zur Speicherung codiert und danach (zur Verwendung) wieder decodiert werden.

• Das Beispiel rechts ist stark vereinfacht. Es verwendet nur positive ganze Zahlen im Bereich 0...999 (d.h. Texte aus 3 Ziffern). Das Array wird mit Funktion tencode aufgebaut.
♦ Details zu Regulären Ausdrücken

• In dieser Form wird das Array mit Methode sort korrekt sortiert.

• Zur Verwendung müssen die Texte wieder in Zahlen umgewandelt werden.
Achten sie bei Verwendung von parseInt auf die Angabe des Dezimal-Systems, sonst werden Zahlen-Strings mit führenden Nullen als Octal-Zahlen interpretiert ! 		► Array aus Zahlen-Strings aufbauen:
var az=new Array();
az[0]=tencode(123);
az[1]=tencode(23);
az[2]=tencode(5);

function tencode(i) {
var t="000"+i.toString();
t.match(/(.{3})$/);
return RegExp.$1;
}
ergibt ["123","023","005"]
► Array sortieren:
az.sort();
ergibt ["005","023","123"]
► Array-Elemente zur Verwendung der Zahlen decodieren:
i = parseInt(az[0],10);
ergibt i=5
Zahlen mit Hilfs-Funktion sortieren
Diese Methode wird zum Sortieren von Zahlen-Arrays empfohlen. 		♦ Details dazu im Kapitel Sortier-Hilfs-Funktionen dieser Seite.

Sortieren mit Hilfs-Funktion (Callback function)
Methode sort vergleicht je 2 Array-Elemente.
Ohne weitere Angaben wird als Vergleichs-Regel der Text-(String)-Vergleich verwendet. Je nach Ergebnis des Vergleichs werden die beiden Elemente vertauscht oder nicht. 		Man kann die Standard Vergleichs-Funktion durch eine eigene Funktion ersetzen. Der Name dieser Funktion (Callback function) wird als Argument übergeben.
In diesem Fall kann man beliebige Regeln zur Sortierung programmieren.

Callback Function

Eine eigene Sortier-Hilfsfunktion muss 2 Bedingungen erfüllen.
▲ Die Funktion erhält 2 Argumente - die beiden zu prüfenden Array-Elemente.
▲ Die Funktion muss ein Ergebnis zurückgeben: Wenn dieser Wert >0 ist, dann werden die beiden Elemente vertauscht. 		Beispiel: Zahlen aufsteigend sortieren:
var az = new Array(123,23,5);
az.sort(numasc);

function numasc(a,b) {
return (a-b);
}
ergibt [5,23,123]

Zahlen-Arrays sortieren

Mit Hilfs-Funktionen lassen sich Zahlen rasch und einfach sortieren. Die Beispiele rechts zeigen Funktionen zum aufsteigenden (ascending) und absteigenden (descending) Sortieren von Zahlen.
function numasc(a,b) {
return (a-b);
}
function numdsc(a,b) {
return (b-a);
}

Umlaute

Umlaute (ÄÖÜäöü) werden in Texten entsprechend ihrem → Zeichen-Code sortiert, d.h. nach allen anderen lateinischen Zeichen.
Im deutschen Sprachraum wird die Sortierung zusammen mit den jeweiligen Stamm-Zeichen (AOUaou) bevorzugt.
Dieses Verhalten kann fast immer toleriert werden, außer bei Anfangs-Buchstaben: Man erwartet "Österreich" zwischen "Oman" und "Polen", nicht jedoch nach "Zimbabwe"
Callback-Funktionen bieten die Möglichkeit, ein anderes Sortier-Verhalten festzulegen.

Leere Elemente

Leere Texte "" werden ohne weitere Angaben an den Anfang, null-Elemente an das Ende von Arrays sortiert.
Callback-Funktionen bieten die Möglichkeit, ein anderes Sortier-Verhalten festzulegen. 		Beispiel:
var ae=new Array(12,"ab",null,"",0);
ae.sort();
ergibt ["",0,12,"ab",null]

Javascript Methode Array.reverse

Methode reverse

Kehrt die Reihenfolge der Elemente eines Arrays ohne Sortierung um.

Wenn sie absteigende Sortierung wünschen, dann wenden sie zuerst Methode sort an, danach reverse 		Umkehrung:
var s = new Array("xy",12,"ab");
s.reverse();
ergibt ["ab",12,"xy"]
Absteigende Sortierung:
s.sort()
s.reverse();
ergibt ["xy","ab",12]

Sortieren mehrdimensionaler Arrays
Mehrdimensionale Arrays können nach jedem einzelnen Element sortiert werden - Im Beispiel rechts z.B. wahlweise nach Namen oder nach (Punkte)-Zahlen, und zwar jeweils aufsteigend oder absteigend.
Die Sortierung erfordert besondere Maßnahmen: Eine der zahlreichen Möglichkeiten wird hier vorgestellt. 		Beispiel (Punktezahl in einem Spiel):
var amul = new Array();
var i=0;
amul[i++] = new Array("Doris",12);
amul[i++] = new Array("Otto",23);
amul[i++] = new Array("Erich",12);
amul[i++] = new Array("Rita",12);
Funktion array_sort_multidim sortiert jedes mehrdimensionale Array amul nach dem Element mit Index idx

• Beispiel: Für idx=1 wird nach dem 2.Element sortiert, weil die Zählung der Elemente mit 0 beginnt.

• Wenn eine Vertauschung notwendig ist, d.h. wenn amul[j][idx]<amul[i][idx] dann werden die betreffenden Array-Elemente vertauscht.

• Die Funktion gibt nichts zurück, weil das übergebene Array amul direkt geändert wird.

♣ Ein Live-Beispiel finden sie im nächsten Kapitel ↓ Interaktive HTML-Tabellen 		Sortier-Funktion (vereinfacht) sortiert das Array amul nach seinem Element amul[idx]
function array_sort_multidim(amul,idx) {
var i=0; var j=0; var tmp=null;
for(i=0;i<(amul.length-1);i++) {
for(j=i+1;j<amul.length;j++) {
if(amul[j][idx]<amul[i][idx]) {
tmp = amul[j];
amul[j] = amul[i];
amul[i] = tmp;
}
}
}
}

Vorsicht - Vereinfachung !

Das Beispiel wurde zur übersichtlichen Demonstration stark vereinfacht:
• Alle Elemente des Demo-Arrays ma haben die gleiche Länge. - Es sind keine Vorkehrungen für kürzere/längere Elemente getroffen.
• Die Zahlen sind alle 2stellig, daher liefert die alphabetische Sortierung das richtige Ergebnis. In realen Anwendungen müssen Zahlen numerisch sortiert werden (Kapitel ↑ Hilfs-Funktionen auf dieser Seite).

Hilfs-Array

Für allgemeine Anwendung muss die vorgestellte Methode in vielen Punkten erweitert werden. Dazu wird häufig ein (gleich langes) Hilfs-Array verwendet:
• Man kopiert veränderte oder zusammengefasste Daten aus dem mehrdimensionalen Array in das Hilfs-Array.
• Danach sortiert man die beiden Arrays parallel, wobei sich die Reihenfolge der Vertauschung nach den Elementen des Hilfs-Arrays richtet.

Umlaute
Sonderzeichen wie z.B. Umlaute kann man vor der Eintragung in das Hilfs-Array umwandeln. Man kann die übliche Umwandlung verwenden, z.B. ä → ae oder andere Varianten, da man die Lesbarkeit nicht berücksichtigen muss: ä → aaa sortiert ä vor a, ä → azz sortiert ä nach a usw.
Zur Umwandlung verwendet man am besten → Reguläre Ausdrücke (replace).

Leere Texte und leere Elemente
Leere Texte "" werden ohne weitere Angaben an den Anfang, null-Elemente an das Ende von Arrays sortiert. Wenn man leere Texte an das Ende sortieren will, dann ersetzt man sie im Hilfs-Array, z.B. "" → "zzzzz"
Sortierung über mehrere Felder
Oft enthalten Arrays identische Elemente - Im Beispiel etwa 2 oder mehr gleiche Namen und/oder die gleiche Anzahl von Punkten. In solchen Fällen muss man mehrere Elemente zur Sortierung verwenden.
Das kann man z.B. erreichen, wenn die Daten mehrerer Elemente des mehrdimensionalen Arrays in das Hilfs-Array eingetragen werden:
Das + Zeichen verkettet Strings:
ahilf[i] = amul[i][0]+amul[i][1];
Wenn die Felder Zahlen enthalten, dann kann man diese vor der Eintragung in das Hilfs-Array mit Methode .toString() in Texte umwandeln und mit führenden Nullen auf gleiche Länge bringen.

Index-Vector

Es ist nicht immer erwünscht, ein Array zur Sortierung auch tatsächlich zu verändern. Wenn das Array im Original erhalten bleiben soll, dann kann man zur Sortierung ein 1-dimensionales Array (Index-Vector) der gleichen Länge erzeugen.
Beispiel:
var aidx = new Array();
for(var i=0;i<amul.length) {
aidx[i]=i;
}

Danach wird der Index-Vector nach den Werten des Arrays (oder eines seiner Elemente) sortiert, d.h. die Elemente von aidx werden entsprechend vertauscht.
Zur Verarbeitung (z.B. Ausgabe) des Arrays verwendet man dann nicht den fortlaufenden Index (hier i) sondern den Wert aus dem Index-Vector (hier j):
for(var i=0;i<amul.length) {
j=aidx[i];
sortiertes_element=amul[j];
}

Interaktive HTML Tabellen
HTML-Tabellen lassen sich in mehrdimensionalen Javascript-Arrays speichern und verarbeiten.
► Klicken sie die Überschriften im Live-Beispiel rechts, um die Tabelle zu sortieren !

Zur besseren Verständlichkeit sind mehr Daten enthalten als im Kapitel ↑ Sortieren mehrdimensionaler Arrays demonstriert. Wiederholungen von Elemente mit gleichen Namen sind absichtlich zugelassen. Die Zufallszahlen ergeben meist auch einige Daten-(Zeilen) mit gleich vielen Punkten.

Zusätzliche Bedienungs-Elemente:
Zeigt den aktuellen Zustand von Array amul in einem Meldungs-Fenster an.
Trägt neue → Zufallszahlen in das Array amul ein.

♦ Details der Programmierung finden sie im Kapitel ↓ Programmierung interaktiver HTML-Tabellen dieser Seite:.

♦ Die meisten in diesem Web enthaltenen Daten-Tabellen werden Live mit Javascript erzeugt. Allerdings ist die Sortierung nicht immer sinnvoll. Ein Beispiel für die praktische Anwendung mit Sortierung: → Standard-Codes für Staaten
Name Punkte

Programmierung interaktiver HTML-Tabellen
Im HTML Quelltext wird anfangs nur eine leere Tabelle - ohne Daten-Zeilen - angelegt.
• Das <colgroup>-Element dient zur rascheren Formatierung der Tabelle.

• Im <thead>-Element wird die Überschrift mit den Bedienungs-Elementen untergebracht.
Die Bedienung der beiden Funktionen sort_name und sort_pts erfolgt mit Hilfe einfacher → Hyperlinks.

• Das <tbody>-Element bleibt leer und erhält ein eindeutiges id-Attribut (hier tab ) zur → Adressierung mit DOM-Methoden. In dieses Element werden später die Daten Live eingetragen.

♣ Tipp: Man kann mehrere <tbody>-Elemente anlegen und damit mehrere Teile einer Tabelle getrennt verwalten. 		HTML (vereinfacht):
<table>
<colgroup>
<col style="width:50%" />
<col style="width:50%" />
</colgroup>
<thead>
<tr>
<th>
<a href="javascript:sort_name()">Name</a>
</th>
<th>
<a href="javascript:sort_pts()">Punkte</a>
</th>
</tr>
</thead>
<tbody id="tab"></tbody>
</table>
Daten
Das <tbody>-Element der Tabelle bleibt im HTML-Quelltext leer.
Die Daten (Zeilen der Tabelle) werden mit Javascript → DOM-Methoden verwaltet, d.h. mit JS werden die Daten-Zeilen Live in der gewünschten Reihenfolge erzeugt. 		Beispiel: Mit JS werden Daten-Zeilen nach diesem Muster erzeugt:
<tbody id="tab" >
<tr><td>Anton</td><td>123</td></tr>
<tr><td>Britta</td><td>456</td></tr>
</tbody>

Sortieren

Der Kern dieses Beispiels ist die oben vorgestellte Sortierung mehrdimensionaler Arrays.
Mit Klick auf die Überschriften werden die beiden Sortier-Funktionen ausgelöst.
Darüber hinaus sind jedoch einige Probleme zu lösen, um die Daten in geänderter Reihenfolge auf einer Webseite anzuzeigen.

Tabelle löschen

Bevor eine neue Tabelle erzeugt wird, ist es am einfachsten und am schnellsten, alle Daten-Zeilen der aktuellen Tabelle zu löschen.
Dazu werden alle childNodes des <tbody>-Elements gelöscht.
Diese Methode ist vorteilhaft, weil sie unabhängig von der aktuellen Anzahl von Daten-Zeilen arbeitet - Auch anfangs, wenn noch keine childNodes vorhanden sind.
Löschen aller Sub-Elemente von <tbody>, d.h. aller Daten-Zeilen der Tabelle:
var n=document.getElementById("tab");
while(n.childNodes.length) {
n.removeChild(n.firstChild);
}

Neue Tabelle erzeugen

• Zuerst wird das <tbody>-Element mit Hilfe seines eindeutigen id-Attributs ("tab") in der Variablen n adressiert. An dieses Element werden alle anderen erzeugten Elemente angehängt.

• Die for-Schleife wird für jedes Element des Daten-Arrays ma 1mal durchlaufen. Allerdings werden die Elemente nicht fortlaufend (mit Index i ) verwendet, sondern es wird der sortierte Index j aus dem Hilfs-Array sn verwendet.

• Für jedes Element von ma wird eine Zeile erzeugt, d.h. je ein <tr>-Element. Daran wird für jede Spalte ein <td>-Element angehängt.

• An jedes <td>-Element wird ein Text-Knoten angehängt - In der ersten Spalte der Name, in der zweiten Spalte die Punkte-Zahl.

• Nach Fertigstellung wird jeder DOM-Knoten an sein parent-Element angehängt. Das ergibt insgesamt die fertige Tabelle.
Voraussetzungen:
• (unsortierte) Daten im mehrdimensionalen Array ma
• Sort-Index im Hilfs-Array sn
(so wie im Kapitel ↑ Sortieren mehrdimensionaler Arrays auf dieser Seite demonstriert):
var n = document.getElementById("tab");
var ntr=null; var ntd=null; var ntxt=null;
var j=0;
for(i=0;i<ma.length;i++) {
// Zeile:
j=sn[i];
ntr=document.createElement("tr");
// Spalte 1
ntd=document.createElement("td");
ntxt=document.createTextNode(ma[j][0]);
ntd.appendChild(ntxt);
ntr.appendChild(ntd);
// Spalte 2
ntd=document.createElement("td");
ntxt=document.createTextNode(ma[j][1]);
ntd.appendChild(ntxt);
ntr.appendChild(ntd);
n.appendChild(ntr);
}
Die Methode ist ideal für alle Fälle, bei denen die AnwenderInnen eine begrenzte Daten-Menge genauer untersuchen (Suchen, Sortieren).
• Sie ist in diesem Fall wesentlich schneller als die meist verwendeten Server-Programme.
• Der Server wird merkbar entlastet und kann daher für alle AnwenderInnen schneller regieren.
• Die Methode ist nicht auf Tabellen beschränkt: Man kann die Daten alternativ oder zusätzlich als → SVG-Grafik anzeigen. 		Alle modernen Browser können Tabellen innerhalb eines <table>-Elements aufbauen. M$IE Browser können Tabellen nur innerhalb eines vorgegebenen <tbody>-Elements aufbauen. Dieses Detail ist leider - wenn überhaupt - nur schlecht dokumentiert.

Alternativen:

Es ist kompliziert und aufwändig, ähnliche Wirkungen mit veralteten Browsern und Javascript zu erzielen.
Hier wird kurz eine der Möglichkeiten skizziert:
• Die HTML-Tabelle wird mit der Javascript Methode document.write aufgebaut. Diese Methode ist allerdings veraltet und funktioniert in → XHTML nicht mehr.
• Jedes (!) einzelne <td>-Element der Tabelle wird mit einem eindeutigen id-Attribut versehen.
• Nach jeder Sortierung wird der Inhalt aller (!) Tabellen-Elemente ausgetauscht. Dazu kann man zwar DOM-Methoden verwenden, allerdings ist dieses Verfahren wesentlich langsamer.
♦ Ein Beispiel finden sie unter → Standard-Codes für Staaten, wenn sie diese Seite mit einem veralteten M$IE Browser öffnen.
► Die meist verwendete Alternative ist die Sortierung auf Server-Seite.
Mit Programmen in → Perl oder → PHP lassen sich problemlos HTML-Tabellen jeder gewünschten Sortierung erzeugen.
• Ein schwerwiegender Nachteil ist allerdings die Belastung des Webservers:
Für jeden einzelnen Sortier-Wunsch wird die gesamte Webseite (bei kluger Programmierung nur die Tabelle) am Server neu programmiert (in HTML-Code umgesetzt) und zum Client übertragen.
• Ein Server arbeitet (bei geringer Last) zwar schnell, dafür muss man die Übertragungs-Zeiten in Kauf nehmen. - Insgesamt ist die oben beschriebene Methode in der Praxis 10..100mal schneller als bei Verwendung von Server-Programmen.

Array als dynamischer Speicher für Objekte
Ein Array ist ein idealer Zwischenspeicher für zeitweilig verwendete Daten aller Art. Vor allem bei Verwendung von → Objekten kommt es vor, dass man eine unbekannte Anzahl solcher Objekte mit begrenzter Lebensdauer verwalten muss.

Ein Array ist die beste Lösung zur Verwaltung von einander ähnlichen Objekten.
Der Speicher darf allerdings auch bei häufiger Verwendung nicht unbegrenzt wachsen, d.h. er sollte immer nur so viel Platz besetzen, wie gerade Elemente enthalten sind.

Das Beispiel demonstriert einen Speicher variabler Länge:
• Neue Elemente werden am Ende angefügt.
• Ein Element wird gelöscht, indem sein Wert null gesetzt wird. Danach wird der Speicher sortiert. Dabei gelangt das null-Element an das Ende und das Array kann wieder verkürzt werden. 		Dynamischer Speicher:
var sa = new Array();
Neue Elemente speichern:
sa[sa.length] = 123;
sa[sa.length] = 234;
sa[sa.length] = 345;
Objekt löschen:
sa[1] = null;
cleanup(sa);
Speicher bereinigen:
function cleanup(ar) {
ar.sort();
while(!ar[ar.length-1]) {
ar.length--;
}
}

Speicher für Objekte

Das Beispiel ist stark verkürzt, weil hier lediglich die Anwendung der Sortierung demonstriert wird. Einige Punkte müssen in der Praxis erweitert werden:
● Beim Löschen müssen sie je nach Anwendung zwischen null, der Zahl 0 und leeren Strings "" unterscheiden.
● In der Praxis ist es meistens erforderlich, die Daten mit einem eindeutigen Index zu bezeichnen. Der fortlaufende Index des Speichers kann dafür nicht verwendet werden, weil er während der Anwendung sortiert und teilweise wieder gelöscht wird.
● In diesem Fall speichert man keine einfachen (skalaren) Daten sondern Arrays, z.B. in der Form
element = new Array(idx++,obj);
sa[sa.length] = element;
Der Objekt-Index idx wird automatisch hochgezählt und kann sehr große Werte annehmen, ohne dass der eigentliche Speicher wächst.
Zur Verwendung eines gespeichertes Objekts sucht man nach seinem Objekt-Index
if(sa[n][0]==gesuchter_index) {...}
und verwendet das zutreffende Objekt obj=sa[n][1]

Zum Inhaltsverzeichnis Homepage von PS-Trainer   >   Entwicklung   >   Javascript   >   Arrays