Sortieralgorithmus für Zahlen

[Jan K.]

Hallo zusammen,

eines meiner Scripte enthät eine riesengroße Tabelle, momentan 1860 Spalten und steigend, inder ich gerne Zahlenwerte spaltenweise mit Javascript sortieren möchte.

Nach einigen Stunden rumprobieren habe ich eine Lösung fabriziert die funktioniert.

Solange ich die Funktion mit einem kleinen Array füttere funktioniert das ganze einwandfrei, aber wenn ich die gewünschte Arraylänge mit 1860 Feldern nehme schmiert der Browser ab, mit der Meldung daß das Javascript zulange läuft.

  
function sortNumbers(field){  
  //Erwartet Array als Input, gibt sortierten Array zurück  
  
  
  //nur Zahlen zugelassen, rest wird gelöscht  
  for(var b=0;b<field.length;b++){  
      field[b]=field[b]*1;  
      if(isNaN(field[b])){field.splice(b,1);}  
  }  
  
  //die Sortierfunktion  
  var groesste_zahl = new Array(0,0);  
  var field_sorted = new Array();  
  var y=0;  
  do{  
    groesste_zahl[0] = 0;  
    groesste_zahl[1] = 0;  
    for(var b=0;b<field.length;b++){  
      var wert_a = field[b];  
      for(var c=0;c<field.length;c++){  
        var wert_b = field[c];  
        if(wert_a > wert_b && wert_a > groesste_zahl[0]){  
        groesste_zahl[0] = wert_a;  
        groesste_zahl[1] = b;  
        }  
      }  
    }  
    field_sorted.push(groesste_zahl[0]);  
    field.splice(groesste_zahl[1],1);  
    y++;  
  }  
  while(field.length>0);  
  return field_sorted;  
}  

Hat den Anschein als wäre diese Lösung zu uneffizient. Nach ein wenig googeln bin ich auf den bubble-algorithmus gestoßen, vondem wikipedia sagt das er völlig ineffizient ist und nur zu schulungs und anschauungszwecken gut ist...

Da mir der nötige Background fehlt frage ich euch ob ihr eine Javascriptlösung für einen Zahlensortieralgorithmus für mehrere Tausend Werte kennt.

Was mich am Rande auch noch interessieren würde ist:
-Wielange kann ein Javascript durchnittlich(oder exakt wenn es da Richtwerte gibt) rechnen bis der Browser sich meldet das es zulange läuft
-Wie genau errechnet sich die Rechendauer für meinen (oder im allgemeinen) Sortieralgorithmus? Mir magelt es schon an dem mathematischen Grundverstänniß dafür. In meinem Algorithmus ist es beispielsweise eine 3 fach geschachtelte Schleife. Bei 1860 angenommenen Feldern und 3 facher Schachtelung, bedeuted das 1860^3 Durchläufe?

Grüße aus Berlin,

Jan

[LX]

Nur interessehalber: warum verwendest Du nicht http://de.selfhtml.org/javascript/objekte/array.htm#sort@title=Array.sort?

Gruß, LX

[Jan K.]

Danke für die interessanten und hilfreichen Informationen.

Ich habe sort() vorher schon probiert, mit dem Ergebnis das es keine Zahlen sortieren kann (111 kommt z.b vor 2), daher hattte ich an meiner eigenen Sortierfunktion gebastelt.

Letztendlich funktioniert das Konstrukt aus dem Selfhtml manual bestens.

  
function Numsort (a, b) {  
  return a - b;  
}  
array.sort(Numsort);  

Mir ist zwar schleierhaft wie genau die Parameter übergeben werden, aber es funktioniert.

Gruß,

Jan

[Sven Rautenberg]

Moin!

function Numsort (a, b) {
  return a - b;
}
array.sort(Numsort);

>   
> Mir ist zwar schleierhaft wie genau die Parameter übergeben werden, aber es funktioniert.  
  
Die Methode sort() erwartet eine Referenz auf eine Funktion.  
  
Diese Funktion wiederum muss zwei Werte als Parameter entgegennehmen (im Beispiel a und b genannt - die Namen sind frei wählbar), und als Rückgabewert muss ein Wert geliefert werden, der  
- kleiner 0 ist, wenn der erste Parameter kleiner als der zweite Parameter ist  
- gleich 0 ist, wenn die beiden Parameter identisch sind  
- größer 0 ist, wenn der erste Parameter größer als der zweite Parameter ist.  
  
"Größer" bezieht sich hierbei auf die vorzunehmende Sortierung, wobei das Sortierergebnis alle Werte von "klein" nach "groß" fortlaufend ins Array einsortiert.  
  
Das Sortieren nach Zahlenwert ist dabei relativ simpel, man kann die Vergleichsfunktion auch komplizierter machen, wenn die im Array gespeicherten Datenstrukturen komplexer sind.  
  
 - Sven Rautenberg

[Gunnar Bittersmann]

@@Jan K.:

Ich habe sort() vorher schon probiert, mit dem Ergebnis das es keine Zahlen sortieren kann (111 kommt z.b vor 2)

Steht doch auch in SELFHTML bei der <http://de.selfhtml.org/javascript/objekte/array.htm#sort@title=Beschreibung der sort()-Funktion> drin: „Im Beispiel wird ein Array Namen definiert, dessen Elemente Zeichenketten darstellen. Um einen solchen Array zu sortieren, genügt es, die Methode sort() einfach auf den Array anzuwenden. Die Elemente des Arrays werden dann neu angeordnet, nämlich lexikalisch aufsteigend sortiert.“

sort() ohne Parameter sortiert also Zeichenketten. Selbstverständlich kommt 111 vor 2 bei lexikalischer Ordnung.

Weiter im Text: „Um Zahlen zu sortieren brauchen Sie eine einfache Vergleichsfunktion.“

Live long and prosper,
Gunnar

[Struppi]

eines meiner Scripte enthät eine riesengroße Tabelle, momentan 1860 Spalten und steigend, inder ich gerne Zahlenwerte spaltenweise mit Javascript sortieren möchte.

Ohne mir den Sortieralgorithmus genauer angesehen zu haben, würde ich zuerst auch den Einwand von LX zustimmen und die Frage ist auch, ob das sortieren solange dauert oder das umbauen der Tabelle?

Ich hab relativ lange gebraucht um meinen Tabellensortierer halbwegs schnell zu machen.
http://javascript.jstruebig.de/js/sort_table_test.html mit 2000 Zeilen in unter 2 Sekunden.

Struppi.

[Cheatah]

Hi,

Hat den Anschein als wäre diese Lösung zu uneffizient. Nach ein wenig googeln bin ich auf den bubble-algorithmus gestoßen, vondem wikipedia sagt das er völlig ineffizient ist und nur zu schulungs und anschauungszwecken gut ist...

ja, Bubblesort ist, wie soll ich sagen ... niedlich. Wenn Dir LX' Vorschlag nicht zusagen sollte (warum auch immer), suche nach Quicksort.

-Wielange kann ein Javascript durchnittlich(oder exakt wenn es da Richtwerte gibt) rechnen bis der Browser sich meldet das es zulange läuft

Keine Ahnung, aber eine Uhr mit Sekundenanzeige sollte Aufschluss geben.

-Wie genau errechnet sich die Rechendauer für meinen (oder im allgemeinen) Sortieralgorithmus?

Meistens ungenau. Grund: Es hängt von der Leistung und aktuellen Auslastung des Rechners ab.

Mir magelt es schon an dem mathematischen Grundverstänniß dafür. In meinem Algorithmus ist es beispielsweise eine 3 fach geschachtelte Schleife. Bei 1860 angenommenen Feldern und 3 facher Schachtelung, bedeuted das 1860^3 Durchläufe?

Du hast nur eine zweifache Schachtelung, die dritte Schleife liegt davor, nicht darüber. Man spricht von einem Aufwand von O(n^2), da das zusätzliche O(n) vergleichsweise irrelevant ist.

Cheatah

[Bademeister]

Hi Jan,

Nach einigen Stunden rumprobieren habe ich eine Lösung fabriziert die funktioniert.

Tut sie leider nicht. Jedenfalls nicht fuer beliebige Arrays.

Da mir der nötige Background fehlt frage ich euch ob ihr eine Javascriptlösung für einen Zahlensortieralgorithmus für mehrere Tausend Werte kennt.

Wenn Du eine fertige Loesung willst, dann ist wohl das von LX vorgeschlagene sort() die Antwort (ich kenne den sort()-Algorithmus nicht, aber ich bin ziemlich sicher, dass Du keine bessere Loesung selber schreiben wirst).

Wenn Du hingegen (zu Uebungszwecken) einen eigenen Algorithmus schreiben willst, dann ist Dein Ansatz doch ganz gut: suche, etwa bei Wikipedia, nach dem Algorithmus Deines Vertrauens und implementiere ihn.

Zu Deinem obigen Algorithmus rege ich an: Schreibe mal ausfuehrliche(!) Kommentare daran. Schreibe zu jeder Zeile in einem deutschen Satz, was die Zeile bewirken soll. Wenn Du Dir das dann hinterher durchliest, dann wirst Du auch ohne mathematischen Background ein Gefuehl dafuer haben, ob es vernuenftig ist, was Du da tust.

In meinem Algorithmus ist es beispielsweise eine 3 fach geschachtelte Schleife. Bei 1860 angenommenen Feldern und 3 facher Schachtelung, bedeuted das 1860^3 Durchläufe?

Durchlaeufe von was? Du meinst Anzahl der Ausfuehrungen des Anweisungsblockes in der innersten Schleife?
Nicht wirklich 1860^3, weil ja die Laenge des Arrays, das durchlaufen wird, kleiner wird, aber von der Groessenordnung her stimmt es schon.

@Cheatah: do, for, for sind ineinander, alle laufen ueber die Laenge des Arrays. Also: kubische Laufzeit.

Grüße aus Berlin,

Gruesse nach Berlin,

der Bademeister

[Cheatah]

Hi,

@Cheatah: do, for, for sind ineinander, alle laufen ueber die Laenge des Arrays. Also: kubische Laufzeit.

stimmt, ich habe das while hinter dem do übersehen. Macht also, weil field in jedem Durchlauf um 1 verkleinert wird, O(n^3).

Cheatah