(PHP) Gleichmäßige Sortierung

[Sebastian Salzgeber]

Hallo

Kann mir jemand helfen, Daten gleichmäßig zu Sortieren?

Schaut euch bitte einmal diese Seite beim schweizer Fehrsehen an.

Wie man sieht, sind die Sendungen dort alphabetisch nach Namen sortiert in Gruppen gepackt (A-Z) und in Spalten gegliedert. Ähnlich wie bei der anderen Ansicht auf der Seite (der thematischen) sind beide Ansichten grob gesagt, platzsparend gesetzt. Will heissen: Sie haben in etwa so viele Einträge pro Spalte, dass die unteren Enden annährend ausgeglichen sind in Ihrer Höhe.

Ich frage mich wie man so eine Ausgleichung erreicht.

Nehmen wir ein Beispiel:
Ich habe 26 Buchstaben im Alphabet (in BEispiel benutzen wir nur die ersten 8 davon) und eine ganze Anzahl an Städtenamen in einer Datenbank. Ich könnte zum einen natürlich 26 GRuppen aufmachen und jeweils die Stadt mit dem Anfangsbuchstaben eintragen. Dies ergäbe dann eber ggf. soetwas:

A B C D E F G H ...
* * * * *   * *
* * * * *   * *
* * *   *   * *
  * *   *   * *
  * *   *     *
  *     *     *
  *           *
  *

Man hat eben mehr Namen mit B als z.B. mit D.

Würde man nun hingehen und sagen: Statt der 8 Gruppen (von A-H) möchte ich nun nur 4 Gruppen haben; wie bekäme ich dann eine ausgeglichene Sortieurng zustande?

Man könnte sie einfach zusammenfassen, doch wären sie dann noch nciht ausgeglichen:

A-B  C-D  E-F  G-H
 *    *    *    *
 *    *    *    *
 *    *    *    *
 *    *    *    *
 *    *    *    *
 *    *    *    *
 *    *         *
 *              *
 *              *
 *              *
 *
12    7    6   11

Bei den Insgesamt 36 Einträgen wäre da der Durschnschnitt bei 4 Kategorien ja 9 Einträge pro Gruppe (36/4). Dies könnte man ggf. durch durchlaufen und mitzählen hinbekommen (kennt man ja von einer Routine, Texte nach zu vielen Zeichen abzukürzen, aber dabei zu beachten, dies nach einem Wort zu mache anstatt mittem in einem Wort) aber dann auch noch das aufsplitten in eine dynamsiche Anzahl an Spalten... dabei bekomme ich dann doch einen Knoten im Kopf. Deswegen: Gibt es Lösungen für sowas ohne, dass ich das Rad neu erfinden muss? Wonach muss ich suchen um so eine classe/function zu finden?
Ich suchte nach div. Sort-Classes aber dort fand ich nur Sortier-Alghorithmen in PHP (was aber auhc spannend nachzuvollziehen war, was dort geschieht).

Liebe Grüße
S. Salzgeber

[Der-Dennis]

Hallo Sebastian,

Wie man sieht, sind die Sendungen dort alphabetisch nach Namen sortiert in Gruppen gepackt (A-Z) und in Spalten gegliedert. Ähnlich wie bei der anderen Ansicht auf der Seite (der thematischen) sind beide Ansichten grob gesagt, platzsparend gesetzt. Will heissen: Sie haben in etwa so viele Einträge pro Spalte, dass die unteren Enden annährend ausgeglichen sind in Ihrer Höhe.

Ich frage mich wie man so eine Ausgleichung erreicht.

Bei diesen Beispielen vermute ich, dass das per Hand gemacht wird, da es keine großen Datenmengen sind.

Ansonsten kenn ich mich mit sowas auch nicht aus und hab im Netz nichts gefunden. Ich hab mir aber grad mal kurz Gedanken dazu gemacht, weil ich das echt interessant finde. Vielleicht können wir ja zusammen was erarbeiten.

Also, gehen wir mal von dem Beispiel mit den Buchstaben aus:

Wir können einfach berechnen, wie viele Elemente wir insgesamt haben und wie viele Elemente jeweils mit einem bestimmten Buchstaben anfangen. Die Buchstaben mit Anzahl schreiben wir in ein Array.

Außerdem wissen wir die Anzahl der gewünschten Spalten, sodass wir, wie Du bereits beschrieben hast, mit AnzahlEinträgeGesamt geteilt durch AnzahlderSpalten den optimalen Wert pro Spalte errechnen können.

Versuchen wir's mit ein bisschen Pseudo-Code:

• Wir setzen eine Variable Summe
• Durchlaufe das Buchstaben Array
• Wenn Summe + aktuelleAnzahldesBuchstaben < BesterWert:
      Summe = Summe + aktuelleAnzahldesBuchstaben
• Sonst wenn Summe + aktuelleAnzahldesBuchstaben > BesterWert:
      wenn BesterWert - Summe > Summe + aktuelleAnzahldesBuchstaben - BesterWert:
        Die beste Lösung ist die MIT dem aktuellen Buchstaben
      sonst:
        Die beste Lösung ist die OHNE den aktuellen Buchstaben
• Sonst:
      Wir haben sogar die optimale Länge erreicht, können die Schleife abbrechen.
• Ende der Schleife
• Lösche die nun verwendeten Buchstaben aus dem Array, durchlaufe das Buchstaben-Array erneut und berechne für die nächste Spalte.

Ich weiß, das hört sich alles etwas kryptisch an. Aber vielleicht finden wir eine Lösung. Diese hier könnte schon ganz gut funktionieren, allerdings weiß ich nicht genau, wie es sich dann mit der letzten Spalte verhält. Die könnte, so wie ich das sehe, um einiges größer oder kleiner sein als die anderen.

Gruß, Dennis

[Tom]

Hello,

Außerdem wissen wir die Anzahl der gewünschten Spalten, sodass wir, wie Du bereits beschrieben hast, mit AnzahlEinträgeGesamt geteilt durch AnzahlderSpalten den optimalen Wert pro Spalte errechnen können.

Versuchen wir's mit ein bisschen Pseudo-Code:

• Wir setzen eine Variable Summe
• Durchlaufe das Buchstaben Array
• Wenn Summe + aktuelleAnzahldesBuchstaben < BesterWert:
      Summe = Summe + aktuelleAnzahldesBuchstaben
• Sonst wenn Summe + aktuelleAnzahldesBuchstaben > BesterWert:
      wenn BesterWert - Summe > Summe + aktuelleAnzahldesBuchstaben - BesterWert:
        Die beste Lösung ist die MIT dem aktuellen Buchstaben
      sonst:
        Die beste Lösung ist die OHNE den aktuellen Buchstaben
• Sonst:
      Wir haben sogar die optimale Länge erreicht, können die Schleife abbrechen.
• Ende der Schleife
• Lösche die nun verwendeten Buchstaben aus dem Array, durchlaufe das Buchstaben-Array erneut und berechne für die nächste Spalte.

Ich weiß, das hört sich alles etwas kryptisch an. Aber vielleicht finden wir eine Lösung. Diese hier könnte schon ganz gut funktionieren, allerdings weiß ich nicht genau, wie es sich dann mit der letzten Spalte verhält. Die könnte, so wie ich das sehe, um einiges größer oder kleiner sein als die anderen.

Die Reihenfolge der Buschstaben liegt ja fest. Also ist es kein Sortier-, sondern ein Verteilproblem.

Die Anzahl der Einträge Gesamt ist bekannt.
Die Anzahl der gewünschten Spalten ist bekannt.

Bei optimaler Verteilung wären dann alle Spalten gelich lang, was aber in der Realität nicht zu erwarten ist.

Legen wir als Randbedingung fest, dass innerhalb einer Gruppe (erstmal) kein Umbruch stattfinden soll. Ist diese Bedingung erfüllbar? Wenn nein: Sonderregel festlegen!
Wenn ja, nächste Gruppe aufrücken lassen und feststellen, ob die Gesmatlänge der Spalte innerhalb der optimalen (+ Toleranz) liegt.

Das Verfahren mit dem Aufrücken dann solange wiederholen, bis die maximale Abweichung von der optimalen Länge ihr Minimum erreicht.

Ggf. noch Sonderregel für letzte Spalte (Schusterjungen, etc.) beachten.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Beat]

Wie man sieht, sind die Sendungen dort alphabetisch nach Namen sortiert in Gruppen gepackt (A-Z) und in Spalten gegliedert. Ähnlich wie bei der anderen Ansicht auf der Seite (der thematischen) sind beide Ansichten grob gesagt, platzsparend gesetzt. Will heissen: Sie haben in etwa so viele Einträge pro Spalte, dass die unteren Enden annährend ausgeglichen sind in Ihrer Höhe.

Das ist händisch betreut.

Die Frage ist, was ist zielführender.
Du hast ein rein gestalterisches Problem.

Eine mehrspaltige Alphabetische Liste könnte nämlich entgegen deinen Beispiele so aussehen

----Spalte------------------
4
   404 error
B
   Bots
   Broadcast
C
   Charges
   Clients
N
   Navigation
----Spalte-------------------
N-Fortsetzung
   Navigation
   Network
   News
   Newsletter
   Nodes
   Noodels
   Notes
S
   Server

Die Listenlänge ist definiert durch die Anzahl Einträge Plus Lables.

Da sind ein paar Einschränkungen.
Eine sortierte mehrspaltige Liste macht erst Sinn, wenn mehr als zwei
Labels vorhanden sind (Ich muss ja als Leser erkennen können um was es sich da handeln könnte)

Hinweis: In der alphabetischen Sortierung herrscht ein Krieg der Kulturen.
Du kannst es nicht allen recht machen.

Alphabetische Anordnung ist nicht unbedingt besser als eine thematische Gliederung, wenn ein Ding einen ungewohnten Titel hat und der Leser nach diesem Ding sucht.
Scannt er ein Angebot, interessiert ihn die alphabetische Sortierung auch nicht, sondern das, was die Titel sagen.

Aber egal, dein Problem lässt sich auch auf thematische Gruppen anwenden, und da gilt mein Vorschlag ebenso.

mfg Beat