| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
 Verfasst am: 25.08.2013, 17:00 Titel: Type Rang sortieren. |
 |
|
Hi ich bräuchte einen kleinen Denkanstoss.
Und zwar habe ich mehrere Objekte mit einer bestimmten Punktezahl.
Ich bräuchte eine schnelle funktion die alle Objekte durchgeht die Punkte vergleicht und somit jedem Objekt einen Rang von eins...bis.... zuweist. |
|
| Nach oben |
|
 |
Sebastian
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 5969
Wohnort: Deutschland
|
| Verfasst am: 25.08.2013, 17:46 Titel: UDT-Array sortieren, z. B. mit BubbleSort |
|
|
Hallo,
| Zitat: | | mehrere Objekte mit einer bestimmten Punktezahl |
du könntest ein Array der Objekte anlegen und auf das Array dann einen Sortieralgorithmus anwenden. Wenn es sich um wenige Elemente handelt bzw. das Sortieren nicht zeitkritisch ist, reicht dafür schon der ganz einfache BubbleSort-Algorithmus. Nach dem Durchlauf des Algorithmus stehen die Elemente dann entsprechend ihrer Rangfolge im Array. Dabei kann man natürlich wahlweise aufsteigend oder absteigend nach dem Schlüssel sortieren.
Viele Grüße!
Sebastian
_________________
Die gefährlichsten Familienclans | Opas Leistung muss sich wieder lohnen - für 6 bis 10 Generationen! |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4699
Wohnort: ~/
|
| Verfasst am: 25.08.2013, 18:03 Titel: |
|
|
Ich habe schon diverse Anpassungen des QuickSort-Algorithmus für verschiedene UDTs vorgenommen. Eine findet sich z. B. in der patfinder.bas (http://www.freebasic-portal.de/projekte/patfinder-41.html) zum alphabeitschen Sortieren der Einträge.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
St_W
Anmeldungsdatum: 22.07.2007
Beiträge: 956
Wohnort: Austria
|
| Verfasst am: 25.08.2013, 20:45 Titel: |
|
|
Wenn sich die Einträge sortieren lassen, muss man das nicht selbst implementieren, sondern kann die qsort Funktion aus der C-Standard-Library verwenden, die ohnehin in jedem FB Programm vorhanden ist. Dazu muss man nur eine Funktion schreiben, die zwei Elemente vergleicht.
Damit kann man beliebige Arrays, die zusammenhängend im Speicher liegen, sortieren. Neben Standard-Datentypen, wie Integer, Strings, ... natürlich auch komplexe, wie UDTs.
_________________
Aktuelle FreeBasic Builds, Projekte, Code-Snippets unter http://users.freebasic-portal.de/stw/
http://www.mv-lacken.at Musikverein Lacken (MV Lacken) |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 26.08.2013, 13:55 Titel: |
|
|
das ist eigentlich ganz easy:
| Code: | Type Blatype
wert as integer
end type
dim foocount as integer = 100
dim foo(foocount) as blatype
for x as integer = 1 to foocount
foo(x).wert = int(rnd * 1000)
next
'hier wird sortiert!!!
dim tpos as integer
do
if tpos = foocount then Exit Do
if foo(tpos).wert > foo(tpos + 1).wert Then
swap foo(tpos), foo(tpos + 1)
if tpos > 1 Then tpos -= 1
Else: tpos += 1
End If
loop
'fertig
for x as integer = 1 to foocount
Print foo(x).wert; " ";
next
print
end 0
|
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 27.08.2013, 08:13 Titel: |
|
|
So ich hab mal nach dem Beispiel von ThePuppetMaster gearbeitet,,,
| Code: |
Dim counter As Integer = 6
Dim obj(counter) As Tobj
For i As Integer = 0 To counter
obj(i).zahl = Rnd * 9
Next
For i As Integer = 0 To counter - 1
if obj(i).zahl > obj(i + 1).zahl Then
Swap obj(i).zahl, obj(i + 1).zahl
EndIf
Next
|
Aber irgentwie vertauscht er die zahlen nicht richtig, oder überhaupt nicht.... |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 27.08.2013, 08:43 Titel: |
|
|
das liegt daran, weil du da nicht ganz richtig umgesetzt hast 
Du darfst die sortierung nicht mit einer for schleife machen, sondern mit einer do und musst die position von hand setzen. Je nachdem ob ein tausch statfidnet oder nicht, wird der index für die nächste prüfung unterschiedlich gesetzt.
hab mal etwas beschreibung hinzugefügt.
| Code: |
'hier wird sortiert!!!
dim tpos as integer 'ist der index für das nächste element
do
if tpos = foocount then Exit Do 'solange durchlaufen, bis wir am ende sind
if foo(tpos).wert > foo(tpos + 1).wert Then 'wenn wert gröser als der nächste ...
swap foo(tpos), foo(tpos + 1) '... dann wert tauschen ...
if tpos > 1 Then tpos -= 1 'und um einen index (falls wir nicht am anfang sind) zurück gehen
Else: tpos += 1 'ansonsten können wir einen index weiter vor gehen
End If
loop
'fertig
|
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 27.08.2013, 11:28 Titel: |
|
|
| Code: | Randomize Timer
Type Tobj
zahl As Integer
End Type
Dim counter As Integer = 6
Dim obj(counter) As Tobj
For i As Integer = 0 To counter
obj(i).zahl = Int(Rnd * 9)
Next
For i As Integer = 0 To counter
? "obj " & i & " | zahl: " & obj(i).zahl & " | rang: " & obj(i).rang
Next
Print
Print "----------------------------------"
Dim tpos As Integer
Do
If tpos = counter Then Exit Do
If obj(tpos).zahl > obj(tpos + 1).zahl Then
Swap obj(tpos).zahl, obj(tpos + 1).zahl
If tpos > 1 Then tpos -= 1
Else
tpos += 1
EndIf
Loop
For i As Integer = 0 To counter
? "obj " & i & " | zahl: " & obj(i).zahl
Next
Sleep
End
|
Dies ist jetzt mein code er funktioniert auch... das merkwürdige ist noch das wenn ich es mehr mals auch starte komische sortierungen dabei herauskommen...
Unsortiert
obj 0 | zahl: 5
obj 1 | zahl: 6
obj 2 | zahl: 3
obj 3 | zahl: 7
obj 4 | zahl: 6
obj 5 | zahl: 0
obj 6 | zahl: 3
----------------------------------
Sortiert
obj 0 | zahl: 5
obj 1 | zahl: 0
obj 2 | zahl: 3
obj 3 | zahl: 3
obj 4 | zahl: 6
obj 5 | zahl: 6
obj 6 | zahl: 7
|
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 27.08.2013, 12:41 Titel: |
|
|
1. Es fehlt ne var im type
| Code: | test5.bas(18) error 18: Element not defined, rang in '? "obj " & i & " | zahl: " & obj(i).zahl & " | rang: " & obj(i).rang'
|
->
| Code: | '...
Type Tobj
zahl As Integer
rang as integer '<===
End Type
'...
|
2. Wertebereich sollte man definieren, wenn man bei 0 anfängt. Je nach boundary kann es nämlich auch erst bei 1 anfangen. Da man das vorab nicht einschätzen kann, ist es nicht schlecht, wenn man es anderen auch vor Augen führt.
| Code: | | Dim obj(counter) As Tobj |
->
| Code: | | Dim obj(0 to counter) As Tobj |
3. Da du eben einen idnexbereich von 0 bis ... hast, und nicht von 1 bis ... muss hier auch der sort algo angepasst werden.
| Code: | | If tpos > 1 Then tpos -= 1 |
->
| Code: | | If tpos > 0 Then tpos -= 1 |
wir im post zuvor erwähnt, ist es wichtig das do loop zu nutzen, um darin im index hin und her springen zu können, was von hand erledigt wird.
da wir bei einem SWAP auch prüfen müssen, ob der vorherige wert nicht eventuell mit dem neuen in ebenfalls getauscht werden muss, wird hier ein rückschritt gemach (-=1) ... vorher muss natürlich geprüft werden, ob wir nicht schon am anfang der liste sind. denn dann würden wir aus unserem array bereich herauslaufen. Daher folgt das If tpos > .... hier könnte man alternativ auch ein LBound(array) einfügen, um die grenze von unten zu erfassen. Alternativ auch für die obergrenze mit UBound.
Das ist auch der Grund, warum er in deiner auflistung auch die erste zahl im array nicht mit sortiert.
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 27.08.2013, 20:08 Titel: |
|
|
Alles klar.
Wenn ich jetzt es so machen will das nur der rang gesetzt werden soll aber nicht die zahl variablen des types müsste ich diese doch in einem Temp Array vorsortiert werden und dann mit den zahl variablen verglichen werden um so den Rang zu bestimmen?
Oder denk ich wieder zu kompliziert? |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 27.08.2013, 20:10 Titel: |
|
|
naja.. das kommt drauf an, was du vor hast.
wenn du die objekte als ganzes sortieren wilst, um so einen rang von 1 bis n zu haben, kannste meinen source nutzen. der sortiert die array-elemente um.
bei deiner variante hast du nur die zahlen IM objekt vetauscht (bei dem ich nicht ganz kapiere, wofür das gut sein soll)
erklär doch mal, was du genau vor hast, bzw. was das ziel sein soll.
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007
Beiträge: 4699
Wohnort: ~/
|
| Verfasst am: 27.08.2013, 21:33 Titel: |
|
|
Sollte es sich bei "rang" um die Positionierung in der Hiscore-Liste handeln, dann ist das unnötig. Diese hast du nämlich schon in der Array-Folge: obj(0) ist Platz 1 usw.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 29.08.2013, 06:42 Titel: |
|
|
Servus...
Ich bräuchte die ganze sache als render Index Nummer für meine engine..
Hab mir jetzt was zusammen gebastelt aber denke das es noch einen schnelleren algo geben muss. |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 29.08.2013, 08:55 Titel: |
|
|
du meinst eine Z-Liste?
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 29.08.2013, 19:47 Titel: |
|
|
Ja genau TPM.
Habe das so gelöst das ich einen type mit z var ,z_temp,r_Index habe.
Ich übergebe die aktuellen z werte an z_temp dann sortieren ich z_temp und vergleiche am Ende die werte der z und z_temp um so den render_Index zu bestimmen. |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 29.08.2013, 19:51 Titel: |
|
|
für Z wäre es sinvoller eine Z->LISTE< zu erzeugen ... eine autonome liste.
sieh es mal so ...
du hast n array, das in einem typ eine var besitzt, welche du so sortierst, das du die reihenfolge hast (Z) ... jetzt musst du einen gigantischen aufwand treiben, um diese auflistung in der richtigen reihenfolge zu sortieren.
deutlichst schneller wäre es hier, wenn du eine 2. liste erzeugst, und in dieser liste jetzt die sortierten elemente ablegst, um so schneller, udn vorallem direkter darauf zugreifen zu können. alternativ sortierst du einfach die gesammte liste mit meinem beispiel um.
oder du erzeugst eine liste in der du die pointer und werte auf deine liste speicherst. dann sortierst du diese liste, und kannst dann durch 1 to n die reihenfolge entsprechend auflisten.
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 29.08.2013, 22:34 Titel: |
|
|
Ich denke mal mein Algo ist zu rechenintensive 
| Code: |
Randomize Timer
Type Tobj
zahl As Integer
zahl_temp As Integer
rang As Integer
End Type
Dim counter As Integer = 30
Dim obj(counter) As Tobj
Dim _timer As Single
_timer = Timer
Dim counts As Integer
Do
counts += 1
Loop Until (Timer > _timer + 1)
Print counts
counts = 0
_timer = Timer
Do
For i As Integer = 0 To counter
obj(i).zahl = Int(Rnd * 100)
Next
For i As Integer = 0 To counter
obj(i).zahl_temp = obj(i).zahl
Next
Dim tpos As Integer
Do
If tpos = counter Then Exit Do
If obj(tpos).zahl_temp > obj(tpos + 1).zahl_temp Then
Swap obj(tpos).zahl_temp, obj(tpos + 1).zahl_temp
If tpos > 0 Then tpos -= 1
Else
tpos += 1
EndIf
Loop
For i As Integer = 0 To counter
For ii As Integer = 0 To counter
If obj(i).zahl = obj(ii).zahl_temp Then
obj(i).rang = ii
EndIf
Next
Next
counts += 1
Loop Until (Timer > _timer + 1)
Print counts
Sleep
End
|
|
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 29.08.2013, 23:20 Titel: |
|
|
| Oder hat jemand ne idee womit ich nach dem sortieren die render reihenfolge berechnen kann? |
|
| Nach oben |
|
|
ThePuppetMaster
Anmeldungsdatum: 18.02.2007
Beiträge: 1839
Wohnort: [JN58JR]
|
| Verfasst am: 30.08.2013, 00:07 Titel: |
|
|
warum sortierst du nicht das array direkt (wie ich das im obrigem beispiel schon demonstriert habe), sondern willst es über ne 2. liste machen?
MfG
TPM
_________________
[ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
| Nach oben |
|
|
0oFreako0
Anmeldungsdatum: 17.12.2011
Beiträge: 114
|
| Verfasst am: 30.08.2013, 09:05 Titel: |
|
|
| Frage die mich beschäftigt ist wie die ich nun Abfrage weches Objekt als erstes gerendert wird und das bis zum letzen durch. Ich kann ja nicht die real_z daten... überschreiben... |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
