Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Zahlen sortieren ohne if?
DarkCell - So 26.03.06 13:37
Titel: Zahlen sortieren ohne if?
Ich habe sechs Int-Variablen: Z1, Z2, Z3, Z4, Z5, Z6 wahlweise auch ein array[1..6]
Jede dieser Variable hat eine zufällige Zahl.
Jetzt möchte ich in der ersten Variable(/Spalte des arrays) die höchste Zahl, in der zweiten die zweithöchste, und so weiter ...
Gibt es eine "schönere" bzw bequemere Möglichkeit, dass Problem zu lösen ohne ewige if-Entscheidungen?
Danke schonmal im voraus
DarkCell
Moderiert von
Christian S.: Topic aus Sonstiges (Delphi) verschoben am So 26.03.2006 um 15:20
Gausi - So 26.03.06 13:56
Ganz ohne Ifs wirds nicht gehen ;-)
Aber such mal nach
BUBBLESORT. Das dürfte für deine Zwecke am geeignetsten sein.
zemy - Di 28.03.06 21:48
Bubblesort, Quicksort, Shellsort, Bogosort.... Wiki unter Sortieralgorythmen. Da gibtsschon was. Ist schon was zu finden. Aber ohne If? Natülich!
Delphi-Quelltext
1: 2:
| if (a[i]>a[j]) tausche(a[i],a[j]); |
wird zu
Delphi-Quelltext
1: 2:
| while (a[i]>a[j]) tausche(a[i],a[j]); |
Obn das elegant ist, wage ich zu bezweifeln :P
MfG
Noodles - Di 28.03.06 22:22
Geht es Dir darum einen Algorithmus selbst zu entwickeln, oder eine vorhandenen Lösung zu finden?
Wenn es das Letztere ist, dann sollte Dir folgendes helfen.
C#-Quelltext
1: 2: 3:
| int[] values = { 5, 2, 8, 3, 22, 1, 7 }; Array.Sort<int>(values); Array.Reverse(values); |
MightyPit - Mi 12.04.06 09:12
Hmm das Funktioniert in Delphi so aber nicht. Ein Array ist in Delphi kein Objekt sondern ein eigenes Sprachmittel. Wenn man eine Liste verwendet kann man sortieren lassen. aber die Vergleichsfunktion muss man selber machen, und darin sind auch wieder mindestens 2 if enthalten
TLIST SORTIERPROBLEM
alzaimar - Mi 12.04.06 09:47
Ohne einen Vergleich wird und kann es nicht gehen. Aber ohne 'ständige' Vergleiche schon. In Bubble/Insertionsort etc. ist sogar nur jeweils ein 'IF' zu finden, insofern kommen diese Algorithmen schon ohne ständige If's aus :wink:
Robert_G - Mi 12.04.06 10:30
Ohne bedingte Sprünge wird man wohl nicht sortieren können. :mrgreen:
Man kann es höchstens so deichseln, dass man sie nicht im selbst geschriebenen Code enthält sondern an TList delegiert. :lol:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42:
| uses Classes;
function CompareInts(left, right : PInteger) : Integer; begin Result := left^ - right^; end;
procedure Print(list : TList); var i : Integer; begin for i := 0 to list.Count - 1 do begin Writeln(PInteger(list[i])^); end; end;
var list : TList;
procedure Add(const items : array of Integer); var i : Integer; begin for i := Low(items) to High(items) do begin list.Add(@items[i]); end; end; begin list := TList.Create(); try Add([5, 2, 8, 3, 22, 1, 7]);
list.Sort(@CompareInts);
Print(list); finally list.Free(); end; end. |
Spaceguide - Mi 12.04.06 10:34
Geht schon ohne IF's:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8:
| procedure Sortiere(var a,b : integer); var temp : integer; begin temp := a;
a := (-abs(a-b)+(a+b)) div 2; b := (abs(temp-b)+(temp+b)) div 2; end; |
*hoffentlich merkt keiner den Beschiss* ;-)
zemy - Mi 12.04.06 17:18
wie währe es da mit...
Delphi-Quelltext
1: 2: 3: 4:
| procedure Sortiere(int x):int begin result:=x; end; |
Spaceguide - Mi 12.04.06 17:24
1) Das sortiert nix
2) Procedures geben keine Werte zurück
3) Den Datentyp int gibt es in Delphi nicht
4) Bei der Deklaration einer Variablen wird der Datentyp nachgestellt und durch einen Doppelpkt. vom Variablennamen getrennt
5) Nach der Angabe des Rückgabewerts einer Funktion muss ein Strichpkt. folgen
Aristoteles - Do 13.04.06 14:24
Titel: Re: Zahlen sortieren ohne if?
DarkCell hat folgendes geschrieben: |
Gibt es eine "schönere" bzw bequemere Möglichkeit, dass Problem zu lösen ohne ewige if-Entscheidungen?
|
Nein. Ohne zwei Zahlen miteinander zu vergleichen kann man nicht feststellen, welche die größere ist.
Auch fremde Routinen wie z.B. Bubblesort müssen auf den If-Befehl zurückgreifen.
Spaceguide - Do 13.04.06 14:53
Man KANN entscheiden, welches die größere/kleinere Zahl von zwei Zahlen ist, ohne eine Fallunterscheidung zu verwenden, und zwar mit der obigen Routine von mir. Abs ist zwar oft als Fallunterscheidung implementiert, aber das lässt sich ja umgehen:
Größere Zahl von a und b: (Sqrt(Sqr(a-b))+(a+b))/2
jasocul - Do 13.04.06 14:59
Damit kannst du den Wert der größeren Zahl bestimmen (Formel habe ich nicht geprüft), aber du weißt immer noch nicht welche die größere ist.
Spaceguide - Do 13.04.06 15:11
Eine Zahl wird ja auch nur über ihren Wert definiert.
Horschdware - Do 13.04.06 15:22
ja gut. dann weisst du wie groß die beiden sind. aber du weisst nicht welche größer ist.
das ist wie bei kuchen: vom ansehen und der beschreibung her weiss du dass zwei kuchen lecker sind. du könntest dir sogar beschreiben lassen WIE lecker sie sind. aber ohne probiert zu haben kannst du trotzdem keinen vergleich ziehen.
btw: ...die größere zahl herausfinden ist ja ein vergleich.
und wie mache ich einen vergleich ohne einen vergleich zu machen? eigentlich nicht...
Spaceguide - Do 13.04.06 15:38
Von was redet ihr hier eigentlich? Kuchen?!?!
Hier der Beweis:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25:
| procedure Sortiere(var aNumbers : array of double); var temp : double; i,j : integer; begin for i:=Low(aNumbers) to High(aNumbers)-1 do for j:=i+1 to High(aNumbers) do begin temp := aNumbers[i]; aNumbers[i] := (-Sqrt(Sqr(aNumbers[i]-aNumbers[j]))+ (aNumbers[i]+aNumbers[j]))*0.5; aNumbers[j] := (Sqrt(Sqr(temp-aNumbers[j]))+ (temp+aNumbers[j]))*0.5; end; end;
procedure TForm1.Button1Click(Sender: TObject); var zahlen : array of double; i : integer; begin setlength(zahlen,100); for i:=Low(zahlen) to High(zahlen) do zahlen[i]:=Random*100; Sortiere(zahlen); for i:=Low(zahlen) to High(zahlen) do memo1.lines.add(floattostr(zahlen[i])); end; |
DaRkFiRe - Do 13.04.06 16:13
Ich vermute mal, dass er das Array / die Zahlen und dessen Sortierung fest im Source verankert hatte, anstatt über Schleifen zu iterieren oder über Funktionen zu rekursieren.
jasocul - Do 13.04.06 16:45
@Spaceguide:
Das Verfahren kann ich nachvollziehen. Über den Sinn lässt sich streiten. :wink:
Robert_G - Fr 14.04.06 12:46
Benutzt ebenfalls bedingte Sprpünge. ;)
Horst_H - Fr 14.04.06 13:36
Hallo,
dem Wahnsinn eine Chance, eine kleine Optimierung ;-).
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
| procedure Sortiere(var aNumbers : array of double); var AbsDiff,Summ : double; pAi,pAj : ^double; pInt32 :^Cardinal; i,j : integer; begin pInt32 := @AbsDiff; inc(pInt32); pAi := @aNumbers[High(aNumbers)-1]; for i:= High(aNumbers)-1 downto 0 do begin pAj := @aNumbers[High(aNumbers)]; for j:=High(aNumbers) downto 1 do begin AbsDiff := pAi^-pAj^; pInt32^:=pInt32^ AND $7FFFFFFF; Summ :=pAi^+pAj^; pAi^ := (Summ-AbsDiff)*0.5; pAj^ := (Summ+AbsDiff)*0.5; dec(pAj); end; dec(pAi); end; end; |
Gruss Horst
zemy - Fr 14.04.06 14:07
Spaceguide hat folgendes geschrieben: |
1) Das sortiert ni
2) Procedures geben keine Werte zurück
3) Den Datentyp int gibt es in Delphi nicht
4) Bei der Deklaration einer Variablen wird der Datentyp nachgestellt und durch einen Doppelpkt. vom Variablennamen getrennt
5) Nach der Angabe des Rückgabewerts einer Funktion muss ein Strichpkt. folgen |
Schon ein Problem, wenn man Stundenlang C/C++ schreibt und dann sich Delphi-Code ausm Ärmel Schütteln soll... Aber es sortiert trotzdem;) Ein einzelner Wert ist sortiert ^^
delfiphan - Fr 14.04.06 15:11
Bucketsort macht keine Vergleiche. Bucketsort funktioniert vereinfacht ungefähr so:
Sortiere die Buchstaben im Wort "elephant". Dabei wird einfach gezählt welcher Buchstabe wie häufig vorkommt. Das heisst:
1x"a", 2x"e", 1x"h", 1x"l", 1x"n", 1x"p", 1x"t"
Das kannst du ungefähr so machen:
Delphi-Quelltext
1: 2:
| for I := 1 to length(S) do inc(Haeuffigkeit[S[I]]); |
Danach gibst du einfach das Resultat aus...
Das ganze Spielchen kann man dann auch in mehrere Schritte unterteilen. Verglichen hast du die Zahlen bzw. Buchstaben untereinander jedoch nie.
Bei Wikipedia gibt's ein Codeschnipsel in Pascal. Im Code kommt nirgends ein "if", ein "=", "<" oder ">" vor. Auch keine while oder repeat Schleifen. Nur fest vorgegebene for-Schleifen.
nullplan001 - Fr 14.04.06 15:39
Es war ja nur gefragt, ob man denn "if" rauslassen könne. Klar, das geht:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
| procedure sortarray(var a:array of word); assembler; label loop1, endloop; asm lea cx,a loop1: mov ax,[cx] add cx,2 mov bx,[cx] cmp ax,bx jz endloop jns endloop sub cx,2 mov bx,[cx] add cx,2 mov ax,[cx] endloop: push offset a call sizeof cmp cx,ax jnz loop1 end; |
Spaceguide - Fr 14.04.06 15:48
Das "IF" ist nicht wörtlich gemeint. Das Problem ist eine Sortierung ohne Verzweigungen.
Horst_H - Fr 14.04.06 15:59
Hallo,
bei Bucketsort muss aber noch etwas hinzukommen, das Du naemlich einen sehr eingeschraenkten Wertebereich.
Siehe
[url=http://www.linux-related.de/index.html?/coding/sort/sort_radix.htm]Hier[/url] bei linstraightradix.
Dies gilt fuer Fliesskommazahln nun meist garnicht.
Aber auch da kann man erst nach Mantissenbytes und dann nach Exponent sortieren.
Dazu muss aber die Anordnung im Speicher genau kennen und es erschliesst sich nicht so leicht.
Hast Du soetwas schon umgesetzt.
Gruss Horst
F34r0fTh3D4rk - Fr 14.04.06 16:31
Spaceguide hat folgendes geschrieben: |
Von was redet ihr hier eigentlich? Kuchen?!?!
Hier der Beweis:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25:
| procedure Sortiere(var aNumbers : array of double); var temp : double; i,j : integer; begin for i:=Low(aNumbers) to High(aNumbers)-1 do for j:=i+1 to High(aNumbers) do begin temp := aNumbers[i]; aNumbers[i] := (-Sqrt(Sqr(aNumbers[i]-aNumbers[j]))+ (aNumbers[i]+aNumbers[j]))*0.5; aNumbers[j] := (Sqrt(Sqr(temp-aNumbers[j]))+ (temp+aNumbers[j]))*0.5; end; end;
procedure TForm1.Button1Click(Sender: TObject); var zahlen : array of double; i : integer; begin setlength(zahlen,100); for i:=Low(zahlen) to High(zahlen) do zahlen[i]:=Random*100; Sortiere(zahlen); for i:=Low(zahlen) to High(zahlen) do memo1.lines.add(floattostr(zahlen[i])); end; | |
wo er recht hat... ;) ihm geht es auch wohl nur darum nicht jede zahl mit jeder vergleichen zu müssen, ihm wurden genug wege genannt, es wurden genug wege genannt, dann sollte auch irgendwann mal gut sein ;)
delfiphan - Fr 14.04.06 21:34
Spaceguide hat folgendes geschrieben: |
Das Problem ist eine Sortierung ohne Verzweigungen. |
Das Problem ist nicht eine Sortierung ohne Verzweigungen. Er hat ein Array und möchte die möglichst ohne eine komplizierte Sortierroutine sortieren. Dabei geht es nicht darum, ob man ein min(a,b) mathematisch zu einem Audruck mit abs() bzw sqrt(sqr()) umformulieren kann.
Es ist nicht meine Aufgabe, die Threads sauber zu halten. Aber: Er hat lediglich gefragt, ob man 6 Integer-Zahlen möglichst ohne grosse IF-Entscheidungen sortieren kann. Alles andere ist dazugedichtet. DarkCell hat seit dem ersten Post nie mehr was von sich gegeben. Die vielen Hacks hier beantworten imho weder seine Frage noch sind die meisten Codeschnipsel ihm in irgend einer Weise dienlich.
Meine Antwort auf seine Frage: Ja, es ist unter Umständen möglich, aber nicht so, wie du es dir wohl vorstellst. Wenn du ein Array sortieren willst hast du zwingend eine For-Schleife und bei allen klassischen Sortieralgorithmen musst du Zahlen vergleichen (eine Ausnahme ist Bucketsort). Bucketsort hat zwar eine lineare Sortierzeit, ist aber bei einer so kleinen Datenmenge (6 Integers) überhaupt nicht zu empfehlen.
Jan11 - Mo 17.04.06 17:20
Man kann sie auch einfach in eine Tstringlist schreiben, und da gibt es den befehl Mystringlist.sort; ... dann kannst du sie einfach wieder einlesen
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| procedure ordnen var(i : integer, mystringlist : Tstringlist, werte : array[1..6] of integer);
begin mystringlist:=Tstringlist.create;
for i := 1 to 6 do begin Mystringlist.add(inttostr(werte[i])); end;
mystringlist.sort;
for i := 1 to 6 do begin werte[i]:=strtoint(mystringlist.strings[i-1]); end;
Mystringlist.free;
end; |
und kann mir mal jemand sagen, wie ich das in sonen coolen delphi-quelltext schreiben kann?
F34r0fTh3D4rk - Mo 17.04.06 17:31
Benutzen auch du die Delphi Tags du sollst junger Padawan.
[delphi][/delphi]
Spaceguide - Mi 19.04.06 08:19
Jan11, da hast du aber überhaupt nicht nachgedacht. Zahlen als Werte zu sortieren ist gänzlich anders als Zahlen als Strings:
1
2
3
100
200
300
wird bei dir zu
1
100
2
200
3
300
sortiert.
TSittly - Di 25.04.06 16:38
Ich versteh euch nicht...als Assemblercode wird immer ein Compare verwendet... aber wen es dennoch interessiert: Hier ein Beispiel mit und eines ohne if.
In Delphi gibt es anscheinend keinen Bedingungsoperator wie in C:
#define Min(x,y) (x<y) ? x:y
Deshalb habe ich es so gemacht, hier mit if (einfaches BubbleSort)
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| procedure TForm1.Sort(var a:array of integer); var t:integer; i,j:integer; begin t:=0; for i:=0 to 8 do begin for j:=0 to 7 do begin if (a[j]>a[j+1]) then begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; end; end; end; |
Und hier das gleiche ohne if
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| procedure TForm1.Sort2(var a:array of integer); var t:integer; i,j:integer; begin t:=0; for i:=0 to 8 do begin for j:=0 to 7 do begin case (a[j]>a[j+1]) of True: begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t; end; end; end; end; end; |
Wer kommt auf die Idee, so rechenintensive Sqrt dem if vorzuziehen?
Die Wahl des Algorithmus hängt mit von der Datenmenge ab, Bubblesort kann man gut für relativ kurze Listen verwenden, Quicksort ist zwar im schlechtesten Fall genauso lahm, aber im besten Fall dafür schneller ;-)
alzaimar - Di 25.04.06 17:32
Dreht es, wie ihr wollt: Spaceguide hat gewonnen (zu recht)!
Spaceguide - Fr 28.04.06 15:59
Hehe, thx. Die ganzen anderen "Lösungen" sind wie einfach das Fremdwort beim Spiel Tabu zu sagen.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!