3. Sortieralgorithmus

Sortieralgorithmus

  • D

    Hi Leute,

    ich habe hier in einer Liste mehrere Assoziationen stehen. Das sind im Grunde Rename-Befehle:
    a=>b
    c=>d

    usw.
    Um jetzt doppeltes Umbenennen zu vermeiden, muss ich das ganze ja sortieren.
    Doppeltes Umbenennen würde hier passieren:
    a=>b
    b=>c

    Das wäre ja im Grunde dieses:
    a=>c
    b=>c
    Man müsste also die Ausführungsreihenfolge ändern:
    b=>c
    a=>b

    Ich hätte es jetzt so sortiert, dass ich mir die Positionen merke, wo a, b, c, ... im hinteren Teil stehen. Und dann jedesmal, wenn a, b, c, ... im vorderen Teil stehen, diesen Eintrag vor den ersten Eintrag verschiebe, in dem a, b, c, ... im hinteren Teil steht. Und dann würde ich das Teil so oft aufrufen, bis nichts mehr verschoben wurde.
    Es ist noch anzumerken, dass es eine 0..1 => n Assoziation ist, d.h. jeder Buchstabe kann maximal einmal auf der linken Seite stehen.

    Was meint ihr dazu? Kann man das schneller machen?

    0
  • S

    ich will nur zu bedenken geben:

    a=>b
    c=>a
    b=>c

    einfach umstrukturieren geht nicht...

    a=>c
    c=>a

    waere wohl etwas doof 😉

    eine loesung habe ich nicht, wollte dich nur auf dieses problem hinweisen.

    0
  • D

    Hm, dann muss beim Hinzufügen zur Liste noch ne Überprüfung auf so einen Ring hinzukommen. Urgs.

    0
  • F

    Vielleicht solltest du dein Problem noch ein wenig konkretisieren.
    Was genau ist das bei der doppelten Umbenennung?
    Kann man die "Assoziationen" nachträglich verändern?

    0
  • D

    Es ist ganz einfach:
    Man hat zwei identische Listen + eine dritte Liste:

    Liste1 => Liste2

    Add

    Liste3

    In Liste1 und Liste2 stehen die gleichen Werte drin. Man wählt einen Wert in Liste1 und einen in Liste2 aus, klickt auf Add und die Assoziation wird in Liste3 übernommen. Wenn man alle Assoziationen drin hat, klickt man auf Rename und alle Elemente werden der Liste3 entsprechend umbenannt.
    Es ist eine PHP-Seite, die es dem Benutzer ermöglicht Zeiten eines Mitarbeiters von einem Projekt auf ein anderes zu buchen.

    0
  • F

    Warum nimmst du nicht ein assoziatives Array? Dann kannst du Liste2 (oder beide?) genau einmal durchgehen und brauchst keine Angst vor doppelten Umbennenungen zu haben.
    Ginge eigentlich auch so wenn du statt die "Assoziationsliste" abzuarbeiten bei jedem Element der Ursprungsliste die richtige Assoziation raussuchst, sollte aber fixer sein. Und auch die Prüfung auf irgendwelche zirkulären Assoziationen sollte etwas eleganter ausfallen.

    Wobei sich das alles so trivial anhört dass ich fast vermute dein Problem immer noch nicht so richtig verstanden zu haben 😉

    edit:
    Ich hab's wohl tatsächlich falsch verstanden, würde aber trotzdem für ein Array plädieren.
    Kannst ja beim Klick auf Rename die Indirektionen auflösen um so aus
    a=>b
    b=>c
    tatsächlich
    a=>c
    b=>c
    statt
    b=>c
    a=>b
    zu machen.
    Einfach die Keys linear durchgehen, schauen ob der Wert selber Key ist und ggf durch dessen Wert ersetzen, bis der Wert kein Alias mehr ist.
    So ähnlich kannst du auch gleich auf zirkuläre Referenzen prüfen.

    0
  • D

    Naja... Gibt es in JavaScript denn assoziative Arrays? Ich will das ganze ja nciht erst sortieren usw, nachdem die Seite abgeschickt wurde, sondern immer direkt, wenn der User eine Assoziation hinzufügt...

    Vielleicht ist es wirklich trivial und ich mach mir grad nur so nen Kopf, weil ich das in JavaScript implementieren muss 😉

    0
  • F

    Hab mir schon ewig kein JavaScript mehr angeschaut aber ich denke selbst wenn's von Haus aus keine assoziativen Container gibt wird's sicher zahllose Open Source Implementierungen geben.

    0
  • D

    Jo, möglich. Werd's mir morgen mal anschauen.

    0
Anmelden zum Antworten