Sortieren [PASCAL]

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
Sortieren [PASCAL]
Nächstes Problem. In matlab könnte man mit sortrows die Zeilen einer Matrix sortieren.

Zitat:

SORTROWS Sort rows in ascending order.
SORTROWS(X) sorts the rows of the matrix X in ascending order as a
group. For ASCII strings, this is the familiar dictionary sort.
When X is complex, the elements are sorted by ABS(X). Complex
matches are further sorted by ANGLE(X).

SORTROWS(X,COL) sorts the matrix based on the columns specified in
the vector COL. For example, SORTROWS(X,[2 3]) sorts the rows of X
by the second and third columns of X.

[Y,I] = SORTROWS(X) also returns an index matrix I such that Y = X(I,smile .

See also SORT.


Ich möchte also die Zeilen einer Matrix nach ihrem ersten Eintrag aufsteigend sortieren. Wie mache ich das in Pascal?

Danke vom tiger Wink
Mazze Auf diesen Beitrag antworten »

Entweder irgendwelche Bibliotheken benutzen wovon ich keine kenne oder aber Du musst die Sortierfunktion selber schreiben.

Dazu brauchst Du dann folgendes:

Eine Ordnung für die Matrixelemente (ich weiss ja nicht was Deine Matrixeinträge sind Augenzwinkern ).

Einen Sortieralgorithmus der dann das Sortieren gemäß der Ordnung übernimmt.

Einfacher Algorithmus: Bubble Sort
Schneller Algorithmus aber recht hohe Varianz was die Zeit angeht: Quick Sort
Schneller Stabiler Algorthmus: Merge Sort

Nach diesen Begriffen kannst Du sehr leicht googlen. Falls Du noch nie einen Sortieralgorithmus implementiert hast würde ich Bubblesort vorschlagen. Sortieren einer Matrix ist im übrigen dann nur n maliges Sortieren eines Arrays, und die meisten Beispiele werden Arrays sortieren.
tigerbine Auf diesen Beitrag antworten »

Selber schreiben... Na dann Schläfer Ich habe es lediglich geschafft einen Algo zu schreiben, der einen Zeilenvektor [1x3] sortiert. Aber die 3 ist da auch fix. Big Laugh

Ich habe aber n² Zeilen, wobei n > 1.000 seien sollte.

Ich google dann mal....
tigerbine Auf diesen Beitrag antworten »

Also ich bin mit den Vokabeln noch nicht so vertraut. Was sind denn diese Bibliotheken?

Was kann denn Pascal "alleine". Hinter sqr, sqrt muss ich ja auch ein Algorithmus verbergen, oder? verwirrt
Mazze Auf diesen Beitrag antworten »

Also ich glaub weniger das Pascal intern schon einen Sortieralgorithmus auf arrays geschweige denn auf Matrizen implementiert hat. Wenn ich Dein Problem richtig deute willst Du die Zeilen der Matrix getrennt sortieren, also Zeile 1 sortieren, Zeile 2 usw. also n mal n Zeilen sortieren, oder anders gesprochen n arrays.

In wie weit kannst Du schon Zählschleifen in Pascal verwenden? Bzw. kannst Du überhaupt schon eine Schleife verwenden? (Zählschleifen kann man mit while Schleifen nachbauen)

Zitat:
Was sind denn diese Bibliotheken?


Das sind prinzipiell Sammlungen von Funktionen und Prozeduren die andere schon geschrieben haben und die man benutzen kann. Je nach Programmiersprache kann man diese unterschiedlich einbinden. Manche sind Kostenlos andere sind Kostenpflichtig. Man muss sie halt nur Kennen bzw. irgendwo runterladen sofern es geht.

Zitat:
Hinter sqr, sqrt muss ich ja auch ein Algorithmus verbergen, oder?


Bei solchen Funktionen in der Regel ein Näherungsverfahren.
AD Auf diesen Beitrag antworten »

Zitat:
Original von Mazze
Zitat:
Hinter sqr, sqrt muss ich ja auch ein Algorithmus verbergen, oder?


Bei solchen Funktionen in der Regel ein Näherungsverfahren.

Bei sqr eher nicht, denn das ist ja pure Multiplikation. Augenzwinkern

Und auch sqrt ist als Coprozessorbefehl direkt in der FPU-Einheit moderner PC-Prozessoren implementiert. Wobei ich mir nicht sicher bin, ob die Wurzelberechnung heutzutage mit dem ganzen SSE/SSE2/SSE3/... nicht doch wieder in Routinen verlagert wird. Augenzwinkern
 
 
Mazze Auf diesen Beitrag antworten »

Uah sqr genau Hammer

Mich würd mal in dem Zusammenhang interessieren wie man Schaltungstechnisch ne Wurzelberechnung macht. Die kann ja trotzdem nur approximativ laufen, es sei denn man spendiert uns nen unendlichen Speicher Big Laugh
AD Auf diesen Beitrag antworten »

Die sehr komplexen PC-Prozessoren haben ja die komplizierteren Befehle wie etwa sqrt auch nicht fest verdrahtet, sondern internen Microcode, der in gewissen Grenzen ja auch änderbar ist, zumindest vom PC-BIOS. Kostet dann allerdings ein paar Takte mehr als die "unmittelbaren" Befehle.
tigerbine Auf diesen Beitrag antworten »

Zitat:
Mazze
In wie weit kannst Du schon Zählschleifen in Pascal verwenden? Bzw. kannst Du überhaupt schon eine Schleife verwenden? (Zählschleifen kann man mit while Schleifen nachbauen)


Ich hab Freitag mit Pascal angefangen. Das dürfte die Frage beantworten. Big Laugh



Zitat:
Mazze

Also ich glaub weniger das Pascal intern schon einen Sortieralgorithmus auf arrays geschweige denn auf Matrizen implementiert hat. Wenn ich Dein Problem richtig deute willst Du die Zeilen der Matrix getrennt sortieren, also Zeile 1 sortieren, Zeile 2 usw. also n mal n Zeilen sortieren, oder anders gesprochen n arrays.


Ja und nein. Ich muss 2mal sortieren.

1. Innerhalb einer Zeile. Beispiel: 1 2 1 muss zu 1 1 2 werden.

Kriterien:

Kleinstes Element auf 1
Nachbarschaft muss erhalten bleiben
und wie im Beispeil oben muss im Fall 121 zu 112 sortiert werden.

Das habe ich. In MAtlab hatte ich das als Funktion "sorty" gespeichert.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
%Sortierfunktion für 1x3 Matrix
function [z]=sorty(v)

%Minimales Element unter Erhaltung der Reihenfolge nach vorne sortieren
if v(1,1)>v(1,2)
   w=[v(1,2), v(1,3), v(1,1)];
   if w(1,1)>w(1,2)
      z=[w(1,2),w(1,3),w(1,1)];
   end
   if w(1,1)<=w(1,2)
       z=w;
   end
end

if v(1,1)<=v(1,2)
   if v(1,1)>= v(1,3)
   z=[v(1,3),v(1,1),v(1,2)];
   else
   z=v;
   end
end


In Pascal sieht es jetzt so aus. Dabei wird es eben direkt eine eine Matrix fester Dimension angewendet, ist also nun keine Funktion mehr wie vorher...

code:
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:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
{Programm Teil 8: Matrix Sortieren}



for i:=1 to sqr(n) do
begin

  IF R4[i,1] > R4[i,2] THEN
  BEGIN

  S1[i,1]:=R4[i,2];
  S1[i,2]:=R4[i,3];
  S1[i,3]:=R4[i,1];


       IF S1[i,1] > S1[i,2] THEN
            BEGIN
            S2[i,1]:=S1[i,2];
            S2[i,2]:=S1[i,3];
            S2[i,3]:=S1[i,1];
            END

       ELSE
            BEGIN
            S2[i,1]:=S1[i,1];
            S2[i,2]:=S1[i,2];
            S2[i,3]:=S1[i,3];
            END;
   END

   ELSE
   BEGIN

   S1[i,1]:=R4[i,1];
   S1[i,2]:=R4[i,2];
   S1[i,3]:=R4[i,3];


       IF S1[i,1] < S1[i,3] THEN

            BEGIN
            S2[i,1]:=S1[i,1];
            S2[i,2]:=S1[i,2];
            S2[i,3]:=S1[i,3];
            END

       ELSE
            BEGIN
            S2[i,1]:=S1[i,3];
            S2[i,2]:=S1[i,1];
            S2[i,3]:=S1[i,2];
            END
   END;

end;


2. Nun müssen die Zeilen noch sortiert werden. Nach der Größe des ersten Eintrags.

3. Bildung der Differenz von je 2 Zeilen 1-2, 2-3 , etc.

Ziel ist es die Anzahl der unterschiedlichen Zeilen zu ermitteln.

Beispiel:

123 = 231 = 312 ungleich 132 = 321 = 213
Mazze Auf diesen Beitrag antworten »

Also erstmal vorne weg, ohne Schleifen wirst Du das Problem nicht für allgemein große Matrizen lösen können. Das Problem selber wäre mit diesen jedoch sehr schnell erledigt. Ich würde Dir vorschlagen das Du Dir mal schleifen in Pascal anschaust, speziell hier die Zählschleife. Das ist ne Sache von 30 min, die Syntax kapierste in 10 sec smile . Das einzige was Du am Anfang damit machen soltlest ist etwas rumspielen das Du ein Gefühl dafür entwickelst.
tigerbine Auf diesen Beitrag antworten »

Wie geeignet ist hier Quicksort?

Wie brutal Schlecht ist mein "sorty"?

Link zu einer guten Seite um die Begriffe zu lernen?

Danke Wink
Mazze Auf diesen Beitrag antworten »

Zitat:
Wie geeignet ist hier Quicksort?


Das kommt drauf an wie die Zahlen in der Matrix auftreten, ich würde Dir aber eher Bubblesort anraten.

Zitat:
Wie brutal Schlecht ist mein "sorty"?


Ich seh da jetzt nicht sofort durch, aber n simpler Sortieralgorithmus ist meistens nicht länger als 10 Zeilen Augenzwinkern . Was sind hier deine R4 und S1 ,S2 ?

Hier mal der Code für einen Bubblesort der eine n-stelliges Array sortiert:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
float tmp = 0;
for i:= 0 to array.length-1 do
 begin
   for j:= 0 to array.length-2 do
     begin
       if(array[j] < array[j+1]) then
        begin
          tmp = array[j];
          array[j] = array[j+1];
          array[j] = tmp;
        end
     end
end


Ich bin nicht mehr sicher ob arraylängen in Pascal auch mit name.length angesprochen wurden.

Man kann den Bubblesort noch etwas optimieren, da in jedem Schritt ja das n-j größte Element bereits sortiert ist aber das lassen wir hier mal.

Die Idee von Bubblesort ist folgende:

Wir nehmen das erste Element und schauen nach ob es kleiner als das Nachbarelement ist, das ganze machen wir einmal das ganze array durch.
Danach steht das kleinste Element ganz hinten. Wenn wir den Vorgang n mal wiederholen (i Schleife) wird im i = n-1 durchgang das array sortiert sein. Aufwand für Bubblesort: n²

Zitat:
Link zu einer guten Seite um die Begriffe zu lernen?


Ich würd glaub ich mal nach Tutorial und Pascal googlen oder sowas ähnliches.

edit:

Für Deine Matrix müsstest Du den ganzen Kram noch mal durch eine 0 bis k Schleife laufen lassen, dann wäre jede Zeile sortiert. Und dann machst Du den kram noch mal für die erste Spalte, dabei musst Du beim tauschen dann aber eine andere Operation (Zeilen tauschen) implementieren.
tigerbine Auf diesen Beitrag antworten »

Wie die Zahlen auftreten weiß ich nicht. Bei Bubblesort stand (im Netz), dass der nur bis n=50 ok wäre. Mein n ist aber 10^6 und größer. Wie lange würden die Algos denn da brauchen (grob)

Problemhintergrund ist, dass ich in matlab alles fertig hatte, nur das Ding dann einen Tag gebraucht hat um mir das Ergebnis zu liefern. Deswegen sollte ich auf, z.B. Pascal umstellen.

Nun zum Sorty. R4 ist eine nx3 Matrix, deren Zeilenvektoren nach oben beschriebenem Kriterien sortiert werden sollen. Wichtig ist, dass benachbarte Zahlen benachbart bleiben müssen.

S1 und S2 sind dann die Matrizen mit den sortieren Zeilen. Denn ich kann ja nicht überschreiben. Ich muss im worst case Fall eine Zeile 2x bearbeiten.

Beispiel:

321 -> 213 -> 132

Vielleicht ist es mit der matlab Darstellung einfacher zu verstehen. Bei Pascal kann ich ja den Zeilenvektor nur einzeln füllen.
MrMilk Auf diesen Beitrag antworten »

Hallo tigerbine,

ich zwar nur asymptotische Laufzeiten von einigen Programmen, aber vielleicht helfen sie dir:

BlubbleSort:
Quicksort: (Worst-Case) - Best case
MergeSort:

Bei der asymtotischen Laufzeit werden die Konsten Zeiten weggelassen. Zum Beispiel das zuweisen einer Varialbe etc. - Man möchte nur wie viel Zeit für schleifendurchläufe etc. verwendet wird.


Du hast bestimmt schon gelesen, dass Quicksort als der beste Sortierer beschreiben wird.

Er ist in dem Sinne besser als MergeSort, die Konstanten deutlich niederiger sind ;-9 Dieses kannst du dir so vorstellen, also ob in einer Schleife 10 oder 1000 Anweisungen sind. Asymtotisch kein Unterschied, aber in der Praxis doch.


Ich hoffe ich konnte dir ein wenig helfen.


Viele Grüße
-- MrMilk
Mazze Auf diesen Beitrag antworten »

Schneller als n*logn kannst Du mit Sortierungen die auf Vergleichen beruhen nicht mehr werden. Es gibt Sortierverfahren die linear mit der größe sind allerdings benötigen diese Vorwissen über die Daten.


Zitat:
Wichtig ist, dass benachbarte Zahlen benachbart bleiben müssen.


Dann ist doch eine Sortierung komplett unmöglich, schau Dir mal das hier an:



Damit die zweite Zeile aufsteigend sortiert ist müssen 3 und 1 getauscht werden. Dann ist aber 1 nicht mehr in Nachbarschaft zur 3 und umgekehrt.
Was heisst Nachbarschaft also in dieses Sinn?

Zu Quicksort: Wenn die Zahlen in der Matrix einigermaßen zufällig verteilt sind, und wenn keine sortierten Teilzeilen dabei sind, kannst Du Quicksort ohne Probleme verwenden. Die Sache ist halt Quicksort im worst-case asymptotisch genauso schlecht wie Bubblesort ist.

Dein Sorty so wie es da steht hat zumindest auch quadratischen Aufwand , d.h ist asymptotisch genauso schnell wie Bubblesort.

Zitat:
Ziel ist es die Anzahl der unterschiedlichen Zeilen zu ermitteln.


D.h alle Zeilen die nur eine Permutation von 3 Elementen sind, sind nicht unerschiedlich? Ich überleg grade ob man das wirklich über Sortieren lösen muss smile
tigerbine Auf diesen Beitrag antworten »

Hallo Mazze,

ganz lieben Dank für die Mühe mit mir. Schau mal in hier (modlink) dann verstehst Du das Problem was der ganzen Sache zu Grunde liegt. (Parkettierung von Kugeloberflächen - Ansatz geodätische Kuppel)

In der Matrix stehen die Seitenlängen von Dreiecken. Ich muss raus bekommen, wie viele kongruente Dreiecke in der Matrix stehen. Deswegen dürfen die Nachbarschaften nicht verändert werden. Eine Sortierung (vielleicht nicht im Sinne der Informatik?) der Zeilen ist dennoch möglich.



1. Das kleinste Element muss auf Platz 1



Hier wären wir dann schon fertig. Probleme macht folgender Fall



Würde man nur nach Minimum auf Pos 1 gehen, käme raus.



Dann sind die Differenzen der Zeilen aber nicht 0, obwohl die Dreiecke kongruent sind. Deswegen hab ich den Sorty geschrieben. Rauskommen soll:



Sorty sollte keinen gängigen Sortieralgo ersetzten, bewahre optimieren, wir haben nur in matlab keine Funktion gefunden, die eine Sortierung wie von mir gewünscht macht. Deswegen hab ich nur einen geschrieben, der nach meinen Wünschen sortiert. Problem war dann, dass matab ab längen >100 einfach schlapp macht. man kann in der Zeit tagsüber ruhig weggehen bis man die Anzahl der kongruenten Dreiecke hat. Das kann es ja nicht sein.

Wenn Du einen anderen Vorschlag zur Berechnung hast, bin ich immer offen dafür. Bislang war der Plan:

1. Seitenlängen der Dreiecke bestimmen
2. Zeilensoertieren
3. Spaltenweise nach der ersten Zeile sortieren
4. Differenz der benachbarter Zeilen bilden
5. Nicht-Nullzeilen zählen
Mazze Auf diesen Beitrag antworten »

Ich hätte sogar einen recht effektiven Algorithmus dafür wenn mein Problem aus diesem Thread lösbar wäre. In Deinem Fall müsste man die Abbildung auf



erweitern.

Wenn man eine solche Abbildung wirklich hätte, so könnte man einen Algorithmus der Ordnung



entwickeln. In der Tat ist die Klassifizierung 3 Elementiger Teilmengen der reellen Zahlen verwand mit Deinem Problem die kongruenten Dreiecke zu zählen.

Die Funktion f könnte man auch ganz trivial als Vergleichsoperator implementieren, also nach dem Verfahren:

Wähle nächstes Zahlentripel aus
suche in den bereits verarbeiteten Tripeln ein gleiches:
wenn gleiches exisitert:
addiere eine 1 zu der zu diesem tripel assoziierten Zählvariablen
wenn nicht
lege für dieses Tripel eine Zählvariable an.

Ein Zahlentripel zu Vergleichen hat konstanten Aufwand c.
Das Zahlentripel zu suchen einen Aufwand von k*c.

im worst case würde diese Algorithmus :

n*n*c

brauchen.
tigerbine Auf diesen Beitrag antworten »

Geschickt den Ball zurückgespielt Augenzwinkern Frage wie lange dauert denn wohl ein durchlauf, wenn ich bubblesort oder quicksort nehmen würde, sagen wir für 10^6, 10^7 Zeilen. Wieder einen Tag? traurig Oder ist das wirklich nur ein Problem von matlab (@ sqrt2: nicht böse gemeint).

Meine Lage kannst Du dir wie folgt vorstellen. Ich habe eine Excel Tabelle und wollte nur mal eben schnell sortieren. Gibt ja einen Button. Nun soll plötzlich ich selbst aufschreiben wie man sortiert. Big Laugh Hammer

Im Moment ist für mich nur wichtig, dass ich das in akzeptierbarer Zeit in Pascal realisiert bekomme. D.h. ein Durchlauf darf nicht wieder einen Tag dauern. Da könnte ich ja auf wieder matlab laufen lassen.

Könntest Du mir dann ganz konkret bei der Anpassung von BS oder QS helfen. Ich gehe langsam echt auf dem Zahnfleisch.

EDIT:

Dein Problem ist doch von meinem verschieden. Bei dir sind alle Permutationen erlaubt, Du forderst ja nur, dass die Menge gleich bleibt. Ich will mehr Big Laugh
Mazze Auf diesen Beitrag antworten »

Zitat:
Dein Problem ist doch von meinem verschieden. Bei dir sind alle Permutationen erlaubt, Du forderst ja nur, dass die Menge gleich bleibt. Ich will mehr


Hm, nach SSS sind doch zwei Dreiecke kongruent wenn alle 3 Seiten gleich lang sind. Demnach kann man doch mit Rotation jedes dreieck auf einander abbilden, weshalb alle Permutationen erlaubt sein sollten doer irre ich mich da?
tigerbine Auf diesen Beitrag antworten »

Ich war mathematisch ungenau. Sorry,

Zitat:
Kongruent sind Formen, wenn man sie durch Spiegelung, Verschiebung oder Drehung auf einander abbilden kann (gleiche Seitenlängen, gleiche Winkel, gleicher Flächeninhalt).


Spiegeln würde man bei SSS brauchen, ich darf aber nur Drehen. Augenzwinkern
Mazze Auf diesen Beitrag antworten »

Ok, das beudetet Du darfst die Zeilen nur zyklisch ändern oder?
tigerbine Auf diesen Beitrag antworten »

Aber ohne Fixpunkt.
Mazze Auf diesen Beitrag antworten »

Das ist ja so gesehen keine reine Sortierung, ich muss da glaub ich erstmal drüber schlafen. Das impelmentieren ist denke ich weniger das Problem als zu verstehen was da genau passiert. In diesem Sinne gute Nacht Augenzwinkern
tigerbine Auf diesen Beitrag antworten »

Schläfer

Wie steht es mit meiner Frage nach der Dauer in Minuten des Algorithmus? O(n²)? Wieder ein Tag?
Mazze Auf diesen Beitrag antworten »

Bubblesort müsste man etwas an Deine Nachbarschaftsbedingungen anpassen, und da die "Breite" deiner Matrix nur 3 ist kannst Du wie bei Deinem Sorty eine feste sortierung angeben (unabhängig von n).

Aufwand eine Zeile zu sortieren: irgendwas Konstantes mit 3
Aufwand alle Zeilen zu sortieren: n*irgendwas mit 3
+ n² für die Sortierung nach der ersten Spalte

Ich glaube nicht das ein solches "Bubblesort" bei 10^6 Einträgen einen ganzen Tag braucht. Ich seh das ganze jetzt so

wähle ein Zahlen Tripel aus {
sortiere zyklisch ohne Fixpunkt
(d.h insbesondere musst Du nicht mal tauschen sondern nur im array shiften)
}
sortiere nach Spalten

Ich hoffe ich hab das Problem jetzt so einigermaßen verstanden Augenzwinkern .
tigerbine Auf diesen Beitrag antworten »

Hi Mazze:

Hatte gestern Nacht noch einen Quicksort im Internet gefunden. An dem habe ich jetzt so lange rumgebastelt, bis er mir Zeilenvektoren nach der ersten Spalte (Primaräschlüssel) sortiert. Ob ich das richtig gemacht habe ( Prost ) weiß ich noch nicht, bei kleinen Matrizen sieht es genauso aus wie ich es haben will.

Beim Sorty bin ich mir sicher, dass er das macht, was ich von der Umsortierung in der Zeile erwarte.

Ich teste jetzt mal, da matlab bis Spaltenlängen von 120 in vertretbarer Zeit läuft, ob die Ergebnisse stimmen mit dem "manipulierten" quicksort passen. Dann melde ich mich wieder.

Einschub:

Bei dem Mengen-Problem. Du sucht eine Eigenschaft, die es möglich macht einer natürlichen Zahl eindeutig ein Zahlentrippel zuzuordnen. Die 3 Zahlen sind dabei paarweise verschieden?

Ob das geht weiß ich nicht, da ich bei der Bestimmung von "Gleichen" viel zu sehr in meinem Algorithmus gedanklich gefangen bin. Nur, vielleicht solltest Du hinschrieben, wie lange O(?) man maximal brauchen darf, um diese Indexzahl zu berechnen. Denn sollte diese Abbildung existieren, sollte sie ja auch schneller zu berechnen sein, als die Sortierung der Matrix, oder?
tigerbine Auf diesen Beitrag antworten »

Ok, der Quicksort funktioniert, aber ich habe etwas übersehen. Ich muss ja 3mal sortieren. Also mit Priorität nach 1.Spalte, dann 2.Spalte und dann 3. Spalte.

Wie stellt man das denn an?

EDIT: Beispiel in Excel:
g0ju Auf diesen Beitrag antworten »

ich habe hier mal einen interessanten link (insofern der noch nicht gepostet wurde). die beispiele sind allesamt in pascal geschrieben:klick
Mazze Auf diesen Beitrag antworten »

Zitat:
Ok, der Quicksort funktioniert, aber ich habe etwas übersehen. Ich muss ja 3mal sortieren. Also mit Priorität nach 1.Spalte, dann 2.Spalte und dann 3. Spalte.


Meinst Du damit Du musst Spalte 1 2 und 3 separat oder in abhängigkeit sortieren?

Übergib doch die Spalten nacheinander dem Quicksortalgorithmus, zumindest wenn Du den Quciksort in eine extra Funktion ausgelagert hast.
tigerbine Auf diesen Beitrag antworten »

Aber dann verlier' ich doch die Sortierung der ersten Spalte wieder. traurig Klick auf die Excel Bilder, dann siehst Du wie es gemeint ist.
AD Auf diesen Beitrag antworten »

Quicksort und auch die anderen gängigen Sortieralgorithmen kannst du auf alle Datenstrukturen anwenden, die einer totalen Ordnung unterliegen. Du musst nur den Vergleichsoperator für zwei Daten, den die Algoritmen verwenden, entsprechend anpassen (in meinen dir zugeschickten Quellen sind das Le und Leq).

In deinem Fall liegt offenbar die Lexikographische Ordnung vor.
tigerbine Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
In deinem Fall liegt offenbar die Lexikographische Ordnung vor.


Das ist richtig. Nun habe ich auch den Begriff. Danke.

In deinem File stehen doch mehrere programme /proceduren oder ist das ein großes aus vielen kleinen. Laufen tut es auf freepascal nämlich nicht.

Zitat:
Arthur Dent
Quicksort und auch die anderen gängigen Sortieralgorithmen kannst du auf alle Datenstrukturen anwenden, die einer totalen Ordnung unterliegen. Du musst nur den Vergleichsoperator für zwei Daten, den die Algoritmen verwenden, entsprechend anpassen (in meinen dir zugeschickten Quellen sind das Le und Leq).


Mmh, wirklich verstehen tue ich es noch nicht. Also beie Dir sieht der Quicksort doch so aus:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
{ Sortiert a[l]...a[r-1] }
procedure QuickSort(l,r: Word);
var k: Word;
begin
  if l+1>=r then Exit;
  k:=l+Random(r-l);  SwapS(k,l);  s:=a[l];
  k1:=l+1;  k:=r-1;
  while k1<k do begin
    while (k1<r) AND Le(k1,l) do Inc(k1);
    while (l<k)  AND Leq(l,k) do Dec(k);
    if k1<k then SwapS(k1,k);
  end;
  if Le(k,l) then SwapS(l,k);
  QuickSort(l,k);  QuickSort(k+1,r);
end;


Welche "Begriffe" die darin auftauschen, müssen denn vorher noch definiert werden? Am der Datei habe ich gefunden:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
function Le(k1,k2: Word): Boolean;
begin
  Inc(v);  Le:=a[k1]<a[k2];
end;

function Leq(k1,k2: Word): Boolean;
begin
  Inc(v);  Leq:=a[k1]<=a[k2];
end;

procedure SwapS(k1,k2: Word);
var t: TSortElement;
begin
  t:=a[k1];  a[k1]:=a[k2];  a[k2]:=t;
end;


Könnten wir die Begriffe im mal durchgehen, also wie der Algorithmus arbeitet? Bislang ist der Array - bezeichnet mit a? - doch 1-dimensional, oder?.

Gruß,
tigerbine
AD Auf diesen Beitrag antworten »

Hmm, die Unterhaltung wird schwierig, da ich die Pascal-Syntax wegen 10jährigem Nichtgebrauch fast vergessen habe ... ich versuchs:

Ich setze oben an:

code:
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:
type
  PSortElement= ^TSortElement;
  TSortElement = record
    x: double;
    y: double;
    z: double;
  end;
  PSortArray= ^TSortArray;
  TSortArray= array[0..Max-1] of TSortElement;

{...}

var
  a: TSortArray;

{...}

function Le(k1,k2: Word): Boolean;
begin
  if (a[k1].x < a[k2].x) then Le := True
  else if (a[k1].x > a[k2].x) then Le := False
  else if (a[k1].y < a[k2].y) then Le := True
  else if (a[k1].y > a[k2].y) then Le := False
  else Le := (a[k1].z < a[k2].z);
end;

function Leq(k1,k2: Word): Boolean;
begin
  if (a[k1].x < a[k2].x) then Leq := True
  else if (a[k1].x > a[k2].x) then Leq := False
  else if (a[k1].y < a[k2].y) then Leq := True
  else if (a[k1].y > a[k2].y) then Leq := False
  else Leq := (a[k1].z <= a[k2].z);
end;


Das ist die Realisierung der lexikografischen Ordnung für dreidimensionale Vektoren mit den Komponenten x,y,z.

Dass mit den Le, Leq ist umständlich, ich weiß - heute würde ich angelehnt an qsort aus C das eher mit einer einzigen Vergleichsprozedur machen:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
{-1 für kleiner, 0 für gleich, 1 für größer }
function Cmp(k1,k2: Word): Integer;
begin
  if (a[k1].x < a[k2].x) then Cmp := -1
  else if (a[k1].x > a[k2].x) then Cmp := 1
  else if (a[k1].y < a[k2].y) then Cmp := -1
  else if (a[k1].y > a[k2].y) then Cmp := 1
  else if (a[k1].z < a[k2].z) then Cmp := -1
  else if (a[k1].z > a[k2].z) then Cmp := 1
  else Cmp := 0;
end;


Dann müsste der eigentliche Code der Sortierprozeduren noch etwas umgestrickt werden. Augenzwinkern
tigerbine Auf diesen Beitrag antworten »

So, ich hab das mal versucht für mich anzupassen. Da ich mit den ARRAYS ohne Längenangabe zunächst so meine Schwierigkeiten hatte, habe ich im Hauptprogramm alles in der Form[1...n] wobei man n oben bei den Variablen manuell anpassen muss. Damit muss ich im Moment leben.

Dann würde der Quicksort für Lexi so aussehen... verwirrt

code:
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:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
program testsort;
uses crt;

type
   PSortElement= ^TSortElement;
   TSortElement= ARRAY [1..3] OF DOUBLE;
   PSortArray= ^TSortArray;
   TSortArray= array[1..4] of TSortElement;

var
   a: TSortArray;
   s: double;
   k1,k2: Longint;
   i,j,v: Longint;

function Le(k1,k2: word): Boolean;
begin
  if (a[k1,1] < a[k2,1]) then Le:= True
  else if (a[k1,1] > a[k2,1]) then Le:= False
  else if (a[k1,2] < a[k2,2]) then Le:= True
  else if (a[k1,2] > a[k2,2]) then Le:= False
  else Le:= (a[k1,3] < a[k2,3]);
end;


function Leq(k1,k2: word): Boolean;
begin
  if (a[k1,1] < a[k2,1]) then Leq:= True
  else if (a[k1,1] > a[k2,1]) then Leq:= False
  else if (a[k1,2] < a[k2,2]) then Leq:= True
  else if (a[k1,2] > a[k2,2]) then Leq:= False
  else Leq:= (a[k1,3] <= a[k2,3]);
end;


procedure SwapS(k1,k2: Word);
var t: TSortElement;
begin
   t[1]:=a[k1,1];  t[2]:=a[k1,2];  t[3]:=a[k1,3];
a[k1,1]:=a[k2,1]; a[k1,2]:=a[k2,2]; a[k1,3]:=a[k2,3];
a[k2,1]:= t[1]; a[k2,2]:= t[2]; a[k2,3]:= t[3];
end;


procedure QuickSort(l,r: word);
var k: word;
begin
   if l+1>=r then Exit;
   k:=1+Random(r-1); Swaps(k,l);
   s:=a[l,1];
   k1:=l+1; k:=r-1;
   while k1<k do begin
      while (k1<r) AND Le(k1,l) do Inc(k1);
      while (l<k)  AND Leq(l,k) do Dec(k);
      if k1<k then SwapS(k1,k);
   end;
   if Le(k,l) then SwapS(l,k);
   Quicksort(l,k); Quicksort(k+1,r);
end;

{Matrix zum Ausprobieren}
begin

a[1,1]:=2; a[1,2]:=3; a[1,3]:=1;
a[2,1]:=1; a[2,2]:=2; a[2,3]:=3;
a[3,1]:=2; a[3,2]:=1; a[3,3]:=3;
a[4,1]:=1; a[4,2]:=2; a[4,3]:=2;

for i:=1 to 4 do
begin
writeln(a[i,1],' ', a[i,2],' ',a[i,3]);
end;
writeln;

quicksort(1,5);

for i:=1 to 4 do
begin
writeln(a[i,1],' ', a[i,2],' ',a[i,3]);
end;
writeln;

end.
AD Auf diesen Beitrag antworten »

Dann bin ich mal gespannt, ob irgendwann das Problem auftaucht, das du damals nicht so ganz ernst genommen hast - wir werden sehen. Augenzwinkern
tigerbine Auf diesen Beitrag antworten »

So ganz verstehe ich dich da immer noch nicht, wo ich mein "blaues Wunder" erleben soll. Ich möchte mit dem Programm ja nicht ausrechnen, ob die Dreiecke theoretisch gleich sind, sondern im Rahmen der Produktionsgenauigkeits von 0.5mm.

  1. Ich berechne erst alle n² Dreiecke (: double) bezogen auf einen Ikosaeder der Kantenlänge a=1.

  2. Dann berechne ich die Länge bezogen auf den Radius der gewünschten Kugel R=20m = 20.000 mm, indem ich die Werte von 1 mit 20*10^4 (noch geteilt durch Radius der Umkugel für a=1) multipliziere

  3. Dann benutze ich round. Die Werte sind zwar noch im Format (double), müßten nun aber auf 0.5mm genau sein.


Das wären doch die Angaben, die man dem Konstrukteur geben müßte, oder? Und diese Angaben vergleiche ich auf Gleichheit. Was ist daran falsch?

Ich dachte ach das es im anderen Thread hiermit geklärt wurde.

BTW, war denn meine Fließkomma Hausaufgabe richtig? Augenzwinkern
AD Auf diesen Beitrag antworten »

Drücke ich mich denn so unverständlich aus? unglücklich

Bezogen auf das Beispiel sind die Dreiecke 1-2 also auch die Dreiecke 2-3 im Rahmen der Produktionsgenauigkeit eben nicht gleich - wohl aber die Dreiecke 1-3. Was bringt also der Sortieralgorithmus in diesem Fall bei der Identifizierung gleicher Dreiecke? Nichts.
tigerbine Auf diesen Beitrag antworten »

Bei mir will es einfach nicht klick machen...Aber ich glaube ich weiß, wo wir aneinander vorbeireden. Das Problem ist zunächst nicht das sortieren, sondern das Runden. Ich hol die Matrix mal her:

( 3.000001 , 4.000000 , 5.000000 )
( 2.999999 , 4.000000 , 5.000000 )
( 3.000000 , 4.000000 , 6.000000 )

Ich habe sie so gelesen. In der Matrix stehen die Angaben, die der Hersteller in sein Prodktionsprogramm eingibt. Also Werte auf 0.5mm gerundet. Daher stehen dort für mich 3 verschiedene Dreiecke.

Du hingegen sagst:

Zitat:

Ok, in Kurzform: Zwei solche "numerisch" ermittelten Floatingpoint-Vektoren und sollte man dann als gleich ansehen, wenn

mit k=0 oder k=1


Nun, dann sind 1 und 2 (hier wurde noch nicht sortiert) gleich. Doch was soll der Mann nun als Produktionsmaße eingeben?
AD Auf diesen Beitrag antworten »

Ok, du rundest also vor dem Sortieren, sortierst quasi (abgesehen von Skalierungsfaktoren) nur Integer-Vektoren. Dann besteht das beschriebene Problem allerdings nicht.
tigerbine Auf diesen Beitrag antworten »

Schön, da fällt mir jetzt aber was vom Herzen. Das Lexi Sortieren klappt doch noch nicht so ganz. Wo der Fehler nun liegt weiß ich noch nicht. Hoffe ihn heute noch zu finden...Vielleicht sieht auch hier jemand, wo ich den Übersetzungsfehler von deinem Code für [0...Max-1] zu [1..4] gemacht habe.

So long und einen schönen Feiertag Wink
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »