Seite 1 von 1

LinkedList nach zwei Kriterien sortieren

Verfasst: 26.02.2007 14:38
von zoidberg
Hi !

Ich hatte schonmal danach gesucht, und auch Lösungsansätze dazu gefunden, nur nicht verstanden.

Kann mir jemand erklären wie ich eine Linked List nach zwei Listeninhalten sortieren kann? Also Tabellenmäßig erst nach Spalte A und anschließend nach Spalte B?

Danke!

Gruß, Steffen

Nur am Rande (weiß nicht ob das bei Linkedlists einen Unterschied macht) ich nutze PB Linux Version 4 Beta 3.

Verfasst: 26.02.2007 14:40
von Kaeru Gaman
musst mal ausprobieren...

normalerweise macht man das mit zwei sortiervorgängen,
zuerst nach dem unterkriterium, danach nach dem hauptkriterium.
bei dem sortieren nach dem hauptkriterium sollte die vorherige sub-sortierung erhalten bleiben,
oder höchstens umgekehrt werden.
wenn letzteres der fall ist, halt die sortierrichtung beim ersten vorgang umkehren.

Verfasst: 09.03.2007 23:48
von zoidberg
Hallo Kaeru!

Ich hab es leider erst heute ausprobieren können, aber das scheint so nicht zu funktionieren.
Hier mein Hin und Her sortier Testprogramm:

Code: Alles auswählen

Structure test
  spieler.b       
  position.b              
  farbe.b
EndStructure
Global NewList karten.test()  
For q = 1 To 4 
  For w = 1 To 10
      AddElement(karten())
        karten()\spieler = q
        karten()\position = w
        karten()\farbe = Random (4)+1
  Next w
  Next q
  SortStructuredList(karten(),0,OffsetOf(test\farbe), #PB_Sort_Byte)
  OpenWindow(0, 10, 10, 500, 400, "Testfenster")
  CreateGadgetList(WindowID(0))
  ListViewGadget(0, 10, 10, 400, 300)
  SortStructuredList(karten(),0,OffsetOf(test\position), #PB_Sort_Byte)
  SortStructuredList(karten(),0,OffsetOf(test\spieler), #PB_Sort_Byte)
   ForEach karten()
    AddGadgetItem(0, x, "Spieler: "+Str(karten()\spieler)+"  Position: "+Str(karten()\position)+"   Farbe: "+Str(karten()\farbe))
    x=x+1
   Next
     Repeat
     Event = WaitWindowEvent()
     Until Event = #PB_Event_CloseWindow
Sollte somit nicht die Sortierung der Positionen eines Spielers stimmen?

Wäre nett wenn es noch einen Tip gäbe.

Danke!

Gruß, Steffen

Verfasst: 10.03.2007 02:28
von PureLust
Hallo zoidberg,

es hängt von dem verwendetem Sortieralgorithmus (z.B. QuickSort, BubbleSort, etc.) ab, in wieweit eine bereits existierende Sortierung bei einer erneuten Sortierung durcheinander gewürfelt wird.

Bei dem von "SortStructuredList" verwendeten Algorithmus handelt es sich vermutlich um den rekursiv arbeitenden QuickSort.
Bei dem QuickSort-Algorithmus handelt es sich um ein sogenanntes instabiles Sortierverfahren welches keinerlei Rücksicht auf eine bereits bestehende Sortierung nimmt und sich im Grunde ausschließlich um eine möglichst schnelle Sortierung des aktuell relevanten Bereiches kümmert. Dabei wird eine evtl. zuvor bereits bestehende Sortierung vollkommen ausser Acht gelassen und zum Teil sehr stark durcheinandergewürfelt.

Im Grunde müsstest Du ein spezielles "Sortierfeld" anlegen, welches die beiden Felder, nach denen Du sortieren möchtest, hintereinander enthält und dann nach diesem zusätzlichen Feld sortieren - dann klappt's auch mit dem QuickSort.

Auf Deinen speziellen Fall bezogen, erreichst Du dies aber auch ganz einfach dadurch, dass Du die Reihenfolge Deiner beiden Byte-Werte in Deiner Struktur etwas änderst und dann "SortStructuredList" nach einem Word (also nach den beiden aufeinander folgenden Bytes) sortieren lässt (siehe abgeändertes Beispiel):

Code: Alles auswählen

Structure TEST 
  position.b        ;<<<<<<<<<<< Änderung
  spieler.b         ;<<<<<<<<<<< Änderung
  farbe.b 
EndStructure 
Global NewList karten.test()  
For q = 1 To 4 
  For w = 1 To 10 
      AddElement(karten()) 
        karten()\spieler = q 
        karten()\position = w 
        karten()\farbe = Random (4)+1 
  Next w 
  Next q 
  SortStructuredList(karten(),0,OffsetOf(TEST\farbe), #PB_Sort_Byte) 
  OpenWindow(0, 10, 10, 500, 400, "Testfenster") 
  CreateGadgetList(WindowID(0)) 
  ListViewGadget(0, 10, 10, 400, 300) 
  SortStructuredList(karten(),0,OffsetOf(TEST\position), #PB_Sort_Word)        ;<<<<<<<<<<< Änderung
   ForEach karten() 
    AddGadgetItem(0, x, "Spieler: "+Str(karten()\spieler)+"  Position: "+Str(karten()\position)+"   Farbe: "+Str(karten()\farbe)) 
    x=x+1 
   Next 
     Repeat 
     Event = WaitWindowEvent() 
     Until Event = #PB_Event_CloseWindow
Als Resultat erhältst Du dann die gewünschte Sortierreihenfolge.

Gruß, PureLust.

Re: LinkedList nach zwei Kriterien sortieren

Verfasst: 10.03.2007 12:34
von horst
Auf meiner Website gibts ein QLsort mit benutzerdefinierten Vergleichsoperationen unter Berücksichtigung mehrerer Felder.
http://home.mnet-online.de/horst.muc/pb.htm