Javascript Sortierfunktion

[Linuchs]

Moin,

ich habe eine ganz einfache Sortierfunktion geschrieben für <li> Elemente, die ein <a> Element (Seitenzahl) enthalten.

Doch irgendwas stimmt nicht, wenn ich erst nach Titel und dann nach Seite sortiere, sind die Seitenzahlen erst nach dem zweiten Sortierlauf aufsteigend.

Ausschnitt aus einem Liederbuch:

  <button onclick="sortiereListeNachSeite('dieses');">sortiere nach Seite</button>
  <ul id=dieses>
    <li>Uhren-Kanon ♫ <a href="#lied_02">02</a></li>
    <li>Ich geh mit meiner Laterne ♫ <a href="#lied_03" target="_parent">03</a></li>
    <li>Shantymen sind very good ♫ <a href="#lied_04" target="_parent">04</a></li>
  </ul>

In Datei sortiere_liste.js:

function sortiereListeNachSeite ( id ) {
  var zahl1, zahl2, html;
  obj = document.getElementById( id ).getElementsByTagName( "LI" );
  for ( i=0; i<obj.length; i++ ) {
    zahl1 = "x" + obj[i].getElementsByTagName( "A" )[0].innerHTML;  // Seitenzahl als string
    for ( j=i+1; j<obj.length; j++ ) {
      zahl2 = "x" + obj[j].getElementsByTagName( "A" )[0].innerHTML;  // Seitenzahl als string
      if ( zahl2 < zahl1 ) {
        html = obj[i].innerHTML;          // unteren sichern
        obj[i].innerHTML = obj[j].innerHTML;  // oberen nach unten
        obj[j].innerHTML = html;              // gesicherten nach oben
        i++;
      }
    }
  }
}

Wo ist der Fehler?

Gruß, Linuchs

[dedlfix]

Tach!

Doch irgendwas stimmt nicht, wenn ich erst nach Titel und dann nach Seite sortiere, sind die Seitenzahlen erst nach dem zweiten Sortierlauf aufsteigend.

Vermutlich ist dein Sortieralgorithmus nicht optimal und macht nicht vollständig was er soll. Nimm lieber die sort()-Funktion eines Arrays und übergib eine benutzerdefinierte Vergleichsfunktion.

dedlfix.

[Matthias Apsel]

Hallo Linuchs,

Wo ist der Fehler?

Kann ich dir nicht sagen, aber soviel:

• Es tritt auch beim Sortieren nacht Titeln auf
• Sortieren ist ein gelöstes Problem, du solltest vielleicht auf einen erprobten Algorithmus zurückgreifen

Bis demnächst
Matthias

[JürgenB]

Hallo Linuchs,

im Wiki wird beschrieben, wie eine Tabelle sortiert werden kann. Das Script auf Liste umzuschreiben (table/tbody →ul, tr/td → li) sollte kein Problem sein.

zu deinem Sortierer: du vergleichst und vertauscht die Elemente i und j, ich glaube, du musst das mit den Elementen j und j+1 machen.

Gruß
Jürgen

[Rolf B]

Hallo Linuchs,

schmeiß das i++ in der inneren Schleife raus, das gehört da nicht hin. Du musst obj[i] mit jedem obj[j] vergleichen.

Ein Selection-Sort geht übrigens anders: Man merkt sich in der inneren Schleife die Position mit dem kleinsten Wert und nur dann, wenn da einer dabei ist der kleiner ist als obj[i] wird getauscht.

Rolf

[Rolf B]

Wenn man bei deinem Vorgehen bleiben will, solltest Du es wie folgt machen, das ist ein echter Selection Sort.

Weitere Korrektur: Die äußere Schleife muss nur bis i<length-1 laufen, weil für i=length-1 die innere Schleife null Durchläufe macht.

Weiterer Vorschlag: querySelector statt getElementsByTagName, der liefert kein Array sondern einfach den ersten Match. Der Lesbarkeit halber sollte man das in eine Funktion auslagern.

function sortiereListeNachSeite ( id ) {
  var zahl1, zahl2, jMin, html;
  obj = document.getElementById( id ).getElementsByTagName( "LI" );
  for ( i=0; i<obj.length-1; i++ ) {
    zahl1 = getLiedNummer(obj[i]);       // Seitenzahl als string
    jMin = i;                            // Nimm an dass Minimum an Pos. i steht.
    // Durchsuche Rest der Liste nach kleineren Liednummern, merke Pos. der kleinsten in jMin
    for ( j=i+1; j<obj.length; j++ ) {
      zahl2 = getLiedNummer(obj[j]);  // Seitenzahl als string

      if ( zahl2 < zahl1 ) {          // An Pos. j eine kleinere Nummer als bisheriges Minimum
        zahl1 = zahl2;                // -> als neues Minimum setzen und Pos. speichern
        jMin = j;
      }
    }
    // Wurde oberhalb von i ein kleinerer Wert gefunden -> Pos. i, jMin tauschen
    if (jMin > i) {
        html = obj[i].innerHTML;
        obj[i].innerHTML = obj[jMin].innerHTML;
        obj[jMin].innerHTML = html;
    }
  }
}

// Liefert Liednummer aus dem Link-Text
function getLiedNummer(entry) {
   return "x" + entry.querySelector("a").innerHTML;
}

Rolf

[Linuchs]

Es hat wirklich gedauert, aber ich hab's gefunden.

Wenn ich die innerHTML vertausche, muss ich auch die Werte vertauschen, die mir zum Vergleich dienen, also

function sortiereListeNachSeite ( id ) {
  var zahl1, zahl2, html;
  // alert ("id ist id der <ul>");
  obj = document.getElementById( id ).getElementsByTagName( "LI" );
  for ( i=0; i<obj.length; i++ ) {
    zahl_i = "x" + obj[i].getElementsByTagName( "A" )[0].innerHTML;   // Seitenzahl als string
    for ( j=i+1; j<obj.length; j++ ) {
      zahl_j = "x" + obj[j].getElementsByTagName( "A" )[0].innerHTML; // Seitenzahl als string
      if ( zahl_i > zahl_j ) {
        html              = obj[i].innerHTML;   // unteren sichern
        obj[i].innerHTML  = obj[j].innerHTML;   // oberen nach unten
        obj[j].innerHTML  = html;               // gesicherten nach oben
        zahl_i            = zahl_j;             // zahl_i wurde geaendert
      }
    }
  }
}

Linuchs

[Rolf B]

Hallo Linuchs,

stimmt, das war auch falsch. Und das i++ hast Du ja ebenfalls entfernt.

Guck Dir trotzdem mal meinen Vorschlag an, der tauscht weniger.

Rolf

[Rolf B]

Hallo Linuchs,

ohne eigene Sort-Akrobatik könnte man es so machen:

function sortiereListeNachSeite ( id ) {
  var i, liedNr, entries={};
  var liste = document.getElementById( id ).getElementsByTagName( "LI" );
  for ( i=0; i<liste.length; i++ ) {
      liedNr = "x" + liste[i].querySelector("a").innerHTML;
      entries[liedNr] = liste[i].innerHTML;
  }
  var keys = Object.getOwnPropertyNames(entries).sort();
  for (i=0; i<keys.length; i++)
  {
     liste[i].innerHTML = entries[keys[i]];
  }
}

Rolf

[Linuchs]

Hallo Rolf,

ohne eigene Sort-Akrobatik könnte man es so machen:

danke dir, deine Funktion habe ich zusätzlich hier eingebaut

Etwas ist komisch. Zwischenüberschriften wie F G H I J verschwinden, dafür sind einige Titel doppelt. Nach Seite 68 kommen noch fünf.

Gruß, Linuchs

[Rolf B]

Hallo Linuchs,

Zwischenüberschriften wie F G H I J verschwinden

natürlich verschwinden die. Sie haben keine Seitenangabe, führen also alle zum gleichen Key "x" und überschreiben sich damit in der entries-Tabelle. Nur die letzte bleibt übrig. Von Zwischenüberschriften war in der Aufgabenstellung keine Rede.

Durch das Wegfallen von 4 Zwischenüberschriften ist die entries-Liste dann zu klein und die Liste wird nicht komplett überschrieben.

Du könntest etwas hexen und im Fall einer leeren Zwischenüberschrift einen Schlüssel "yn" setzen, mit einem fortlaufenden n. Damit bleiben die Einträge für Zwischenüberschriften eindeutig und gehen nicht verloren. Für die ANZEIGE musst Du dann noch erreichen, dass bei einer Sortierung nach Seite die <li>, die einen y-Schlüssel bekommen, versteckt werden. Bei einer Sortierung nach Titel blendest Du alle wieder ein.

Alternatives Vorgehen: Du könntest Du vom Server aus eine Javascript-Tabelle schicken, die die Inhaltsverzeichnis-Einträge enthält, und die Sortierung basierend auf dieser Tabelle ausführen. Die initiale Darstellung setzt Du entweder im ready-Handler der Seite (Sortieren nach Titel im DOMContentLoaded Event) oder schickst sie vom Server gleich mit. Je nach dem, ob nach Titel oder Seitenzahl sortiert wird, kommen Zwischenüberschriften hinein oder nicht. Und statt die <li> zu überschreiben, müsstest Du dann die <li> komplett aus der Liste löschen und neu einfügen. Dann sollte es passen.

Rolf