Quick Sort Verfahren

Beiträge
2
Reaktionspunkte
0
Zuviel Werbung?
-> Hier kostenlos registrieren
Hallo,

habe folgendes Problem. Ich soll folgende FB anstatt Bubble Sort Verfahren mit Quick Sort Verfahren sortieren lassen. Kennt sich damit jemand aus?! Danke!



FUNCTION_BLOCK AUSWERTEN
CONST
GRENZE := 7;
END_CONST

VAR_IN_OUT
sortierpuffer : ARRAY[0..GRENZE] OF INT;
END_VAR

VAR_OUTPUT
rechenpuffer : ARRAY[0..GRENZE] OF
STRUCT
wurzel : INT;
quadrat : INT;
END_STRUCT;
END_VAR

VAR_TEMP
tauschen : BOOL;
index, hilf : INT;
wertr, ergebnr: REAL;
END_VAR

BEGIN
(********************************************************
Teil 1 Sortierung : nach dem "Bubble Sort" Verfahren: Werte
solange paarweise tauschen, bis Messwertpuffer sortiert ist.
**********************************************************)
REPEAT
tauschen := FALSE;
FOR index := GRENZE TO 1 BY -1 DO
IF sortierpuffer[index-1] > sortierpuffer[index]
THEN hilf := sortierpuffer[index];
sortierpuffer[index] := sortierpuffer[index-1];
sortierpuffer[index-1] := hilf;
tauschen := TRUE;
END_IF;
END_FOR;
UNTIL NOT tauschen
END_REPEAT;
(**********************************************************
Teil 2 Berechnung : Wurzelberechnung mit Standardfunktion
SQRT und Quadrierung mit Funktion QUADRAT durchführen.
************************************************************)
FOR index := 0 TO GRENZE BY 1 DO
rechenpuffer[index].wurzel := WURZEL(sortierpuffer[index]);
rechenpuffer[index].quadrat := QUADRAT(sortierpuffer[index]);
QUADRAT(sortierpuffer[index]);
END_FOR;
END_FUNCTION_BLOCK
 
Vorgehensweise bei Quicksort:
- von einer gegebenen Elementefolge wird das erste als Trennelement genommen. Alle anderen Elemente werden davor (wenn sie kleiner oder gleich sind) oder dahinter (wenn sie größer sind) angeordnet. Das Trennelement steht danach an der richtigen Stelle.
- mit den beiden so entstandenen Teilfolgen, welche durch das Trennelement getrennt sind, wird ebenso verfahren.
- eine Teilfolge aus nur einem Element ist natürlich sofort fertig sortiert.
- eine Teilfolge aus nur zwei Elementen benötigt zum Sortieren nur noch einen Vergleich.
Es handelt sich um ein rekursives Sortierverfahren, braucht also Speicherplatz.
Weitere Informationen findest du auch bei Wikipedia.
(oder wolltest du hier deine Aufgabe fertig gelöst bekommen :?:)
MfG
eNDe
 
Hi,

z.B.
Code:
FUNCTION_BLOCK _ARRAY_SORT
TITLE = '_ARRAY_SORT'
//
//this function will sort a given array.
//the function needs to be called:  _array_sort(adr("array"),sizeof("array"));
//this function will manipulate a given array.
//the function will not return anything except true, it will instead manipulate the original array.
//because this function works with pointers its very time efficient and it needs no extra memory.
//
VERSION : '2.0'
AUTHOR  : Alex
NAME    : AR_SORT
FAMILY  : ARFUNCT

VAR_INPUT
  PT : POINTER;       (* POINTER TO REAL *)
    _PT AT PT: STRUCT
      DBNr: WORD;
      Adr: DWORD;
    END_STRUCT;    
  SIZE : INT;
END_VAR
VAR_OUTPUT
  SORT: BOOL;
END_VAR
VAR
  stack: ARRAY[1..32] OF INT;  (* Stackgröße~ 1,6*Log(n)/log(2) *)
                    (* Stackgröße 32 => ~1 Mio Elemente *)
END_VAR  
VAR_TEMP
  stack_count: INT;        (* Laufvariable Stack*)
  links: INT;            (* Anfangselement des Arrays *)
  rechts: INT;           (* Endelement des Arrays *)
  pivot: REAL;            (* temporärer Schwellwert für Tauschbedingung *)
  i: INT;              (* Laufvariable1 *)
  j: INT;              (* Laufvariable2 *)
  ende_innen: BOOL;       (* Ende innere Schleife *)
  ende_aussen: BOOL;        (* Ende äußere Schleife *)
  tmp: REAL;            (* Hilfsvariable zum Tauschen von Werten *)
  Adr: INT;
  DB_LENGTH: WORD;
  WRITE_PROT: BOOL;
  rTEST_DB: INT;
END_VAR

BEGIN

SORT := FALSE;
 
(* Datenbaustein Testen *)
rTEST_DB := TEST_DB(DB_NUMBER := _pt.DBNr // IN: WORD
                   ,DB_LENGTH := DB_LENGTH // OUT: WORD
                   ,WRITE_PROT := WRITE_PROT // OUT: BOOL
                   ); // INT
(* Ende wenn Test-DB <> 0 = Fehler *)
IF rTEST_DB <> 0 THEN RETURN; END_IF;
(* Ende wenn DB zu klein *) 
IF WORD_TO_INT(DB_LENGTH)/4 < size THEN RETURN; END_IF;

Adr := DWORD_TO_INT(SHR(IN:=SHL(IN:=_pt.Adr,N:=8),N:=11))-4;

(* Startwerte zur Arraygröße *)
links := 1;         (* Anfangselement des Arrays *)
rechts := WORD_TO_INT(SHR(IN:=INT_TO_WORD(size),N:=2));    (* Endelement des Arrays *)
stack_count := 1;     (* Laufvariable Stack *)

WHILE NOT ende_aussen DO            (* äußere Schleife *)
  IF links < rechts THEN
    pivot := DWORD_TO_REAL(WORD_TO_BLOCK_DB(_pt.DBNr).DD[(Adr+WORD_TO_INT(SHR(IN:=INT_TO_WORD(rechts+links),N:=1)))*4]);      (* Wert des mittleren Elements als Pivot-Wert *)
    i := links -1;
    j := rechts +1;

    (* innere Schleife, teile Feld *)
    ende_innen := FALSE;
    REPEAT

      (* steigende Reihenfolge *)
      REPEAT  i := i+1; UNTIL (DWORD_TO_REAL(WORD_TO_BLOCK_DB(_pt.DBNr).DD[(Adr+i)*4]) >= pivot) OR NOT (i < rechts) END_REPEAT;
      REPEAT  j := j-1; UNTIL (DWORD_TO_REAL(WORD_TO_BLOCK_DB(_pt.DBNr).DD[(Adr+j)*4]) <= pivot) OR NOT (j > links)  END_REPEAT;


      (*sinkende Reihenfolge *)
(*      REPEAT  i := i+1; UNTIL (PT^[i] <= pivot) OR NOT (i < rechts) END_REPEAT  *)
(*      REPEAT  j := j-1; UNTIL (PT^[j] >= pivot) OR NOT (j > links)  END_REPEAT  *)

      IF i >= j THEN
        ende_innen := TRUE;
      ELSE
           tmp := DWORD_TO_REAL(WORD_TO_BLOCK_DB(_pt.DBNr).DD[(Adr+j)*4]);
        WORD_TO_BLOCK_DB(_pt.DBNr).DD[(Adr+j)*4] := WORD_TO_BLOCK_DB(_pt.DBNr).DD[(Adr+i)*4];
        WORD_TO_BLOCK_DB(_pt.DBNr).DD[(Adr+i)*4] := REAL_TO_DWORD(tmp);
      END_IF;

    UNTIL ende_innen END_REPEAT;

    (* Push stack *)
    stack[stack_count] := rechts;   (* rechten Teil später sortieren *)
    IF Stack_count < 32 THEN
      stack_count := stack_count +1;
    ELSE
      ende_aussen := TRUE;
      SORT := FALSE;         (* Fehler: Stack zu klein *)
    END_IF;

    (* linken Teil sortiern *)
    rechts := MAX(IN1:=links,IN2:=i-1);

  ELSE

    IF stack_count = 1 THEN
      ende_aussen := TRUE;
    ELSE

      links := rechts+1;

      (* pop stack *)
      stack_count := stack_count -1;    (* jetzt rechten Teil sortierne *)
      rechts:= stack[stack_count];
    END_IF;

  END_IF;

END_WHILE;

SORT := TRUE;        (* Sortierung beendet *)

END_FUNCTION_BLOCK

Beispiel _ARRAY_SORT aus der OSCAT_S7_basic_332 Lib. Download unter http://www.oscat.de/

Gruss Daniel
 
Ist das so driekt auch auf neuen Steuerungen (1500) und neuem TIA-Portal sinnvoll nutzbar? Man arbeit dort ja nicht mehr so richtig mit indirekter Adressierung auf Datenbausteinen, oder irre ich mich da?
 
Zuviel Werbung?
-> Hier kostenlos registrieren
Das Adressieren von ArrayElementen über einen Index ist letztlich auch nichts anderes als ein "indirektes Adressieren".
Vorsicht aber bei "QuickSort": QuickSort ist ein rekursives Verfahren und die erforderliche StackTiefe hängt davon ab, wie "unsortiert" die Daten vor dem Sortieren sind!
 
ich hab den aus der OSCAT mal etwas angepasst für TIA und 1500er.
Code:
FUNCTION_BLOCK "Quicksort"
TITLE = Quicksort
{ S7_Optimized_Access := 'TRUE' }
AUTHOR : VoR
FAMILY : Filter
VERSION : 1.4
//Quicksort. Sortierung aufgebaut nach dem Prinzip Teile und herrsche.
   VAR_OUTPUT 
      sort : Bool;   // Meldung für fertig Sortiert.
   END_VAR


   VAR_IN_OUT 
      Arraytosort : Array
[*] of LReal;   // Array das sortiert werden soll. Muss vom Typ LReal sein. Länge ist Dynamisch.
   END_VAR


   VAR 
      stack : Array[1..32] of DInt;   // Beispiel aus OSCAT Bibliothek
   END_VAR


   VAR_TEMP 
      stack_count : Int;   // Stack index
      links : DInt;   // zähler links
      rechts : DInt;   // zähler rechts
      pivot : LReal;   // mittlerer Wert
      i : DInt;   // index für Rechte Gruppe
      j : DInt;   // index für Linke gruppe
      ende_innen : Bool;   // Innere Schleife beendet
      ende_aussen : Bool;   // äussere Schleife beendet
      tmp : LReal;   // wert zwischenspeichern für Tausch
      Arraygroesse : DInt;
      status : Int;
   END_VAR




BEGIN
	#Arraygroesse := UPPER_BOUND(ARR:=#Arraytosort, DIM:=1) - LOWER_BOUND(ARR:=#Arraytosort, DIM:=1);
	
	
	#sort := false;
	#links := LOWER_BOUND(ARR:=#Arraytosort, DIM:=1); // Arrayanfang
	#rechts := UPPER_BOUND(ARR:=#Arraytosort, DIM:=1); // Arrayende
	#stack_count := 1; // init Stackindex
	
	WHILE NOT #ende_aussen DO
	    IF #links < #rechts THEN
	        #pivot := #Arraytosort[(#rechts + #links) / 2];
	        #i := #links - 1;
	        #j := #rechts + 1;
	        
	        // Teile und herrsche       
	        #ende_innen := false;
	        REPEAT
	            REPEAT // In rechte gruppe ordnen
	                #i := #i + 1;
	            UNTIL #Arraytosort[#i] >= #pivot OR NOT (#i < #rechts) END_REPEAT;
	            
	            REPEAT // in linke gruppe ordnen
	                #j := #j - 1;
	            UNTIL #Arraytosort[#j] <= #pivot OR NOT (#j > #links) END_REPEAT;
	            
	            IF #i >= #j THEN
	                #ende_innen := TRUE;
	            ELSE
	                #tmp := #Arraytosort[#j];
	                #Arraytosort[#j] := #Arraytosort[#i];
	                #Arraytosort[#i] := #tmp;
	            END_IF;
	            
	        UNTIL #ende_innen END_REPEAT;
	        
	        // Stack bearbeiten
	        #stack[#stack_count] := #rechts;
	        IF #stack_count < 32 THEN
	            #stack_count := #stack_count + 1;
	        ELSE
	            #ende_aussen := TRUE;
	            #sort := FALSE;
	        END_IF;
	        
	        #rechts := MAX(IN1 := #links, IN2 := #i - 1);
	        
	    ELSE
	        
	        IF #stack_count = 1 THEN
	            #ende_aussen := TRUE;
	        ELSE
	            
	            #links := #rechts + 1;
	            
	            #stack_count := #stack_count - 1;
	            #rechts := #stack[#stack_count];
	        END_IF;
	        
	    END_IF;
	    
	END_WHILE;
	
	#sort := TRUE;
	
	
	
	
END_FUNCTION_BLOCK
 
Hallo zusammen :)

Die Anpassung für TIA/1500 funktioniert super und das Sortieren klappt auch ohne Probleme. Mein Problem ist nur, dass ich zu sortierende Betriebsstunden in den Array (arraytosort) move und dadurch, dass der Baustein dann in den Array zurückschreibt geht meine Zuordnung der Motoren verloren. Kann man das iwie anders lösen oder kann ich den Baustein für sowas einfach nicht nehmen?

Vielen Dank im Voraus!

Gruß Dennis
 
Zuviel Werbung?
-> Hier kostenlos registrieren
Hallo zusammen :)

Die Anpassung für TIA/1500 funktioniert super und das Sortieren klappt auch ohne Probleme. Mein Problem ist nur, dass ich zu sortierende Betriebsstunden in den Array (arraytosort) move und dadurch, dass der Baustein dann in den Array zurückschreibt geht meine Zuordnung der Motoren verloren. Kann man das iwie anders lösen oder kann ich den Baustein für sowas einfach nicht nehmen?
Ich löse das so dass ich Array mit den kompletten UDT eines Motors sortiere. Das heisst in dem UDT ist auch der Name/Nummer/AKS des Motors abgelegt, damit habe ich die Zuordnung wieder.
 
Könntest du mir dazu eventuell ein Beispiel aufzeigen, wie du da vorgehst? Das sind quasi meine ersten Schritte mit Arrays und UDT hab ich noch gar nichts mit gemacht.
 
Du definierst dein Array als ARRAY[*] OF UDT_Betriebsstunden.
In dem UDT hast du dann mindestens die Elemente "Name" und "Betriebsstunden". Die zu sortierenden Werte sind dann "UDT_Betriebsstunden".Betriebsstunden; aber zum verschieben wird dann der ganze UDT genommen.
 
Zuviel Werbung?
-> Hier kostenlos registrieren
Hab ich alles so gemacht. Wenn ich jetzt aber das ARRAY UDT_Betriebsstunden vorne am Quicksort anhängen will, meckert er, weil der Aktualparameter sich vom Formalparameter (ARRAY [*] of Dint) unterscheidet? Wenn ich den Parameter im Baustein anpasse, dann meckert er auch, weil die Variable nicht passt.
 
Code:
TYPE "Motor"
VERSION : 0.1
   STRUCT
      Betriebsstunden : Real;
      Starts : DInt;
      Motornummer : Int;
      Serienummer : String[16];
   END_STRUCT;

Dann deklarierst du in der Schnittstelle des Bausteins der den Typen bearbeiten soll entsprechend die Teile.
Beim Quicksort wären dies.
Arraytosort : Array[*] of "Motor"; Weil das ist ja das zu sortierende Array mit den Inhalten des Typen.
pivot : "Motor"; // mittlerer Wert den du zum Vergleich brauchst
tmp : "Motor"; // wert zwischenspeichern für Tausch der ebenfalls alle Motorwerte braucht damit du diese mit tauschen kannst.

In TIA wird dir dann im Code ja angemosert wo du den Code noch anpassen musst. Das überlasse ich dir jetzt mal.
So funktioniert das eigentlich immer. wenn du einen Baustein der für einen Basisdatentypen gemacht wurde, auf einen Anwenderdatentypen anwenden willst.
 
@vollmi: Habs versucht so umzusetzen. Hin und her probiert, aber der Baustein ist immer weiter am meckern. Habe mal ein Bild angehangen. Vielleicht sieht man ja auf Anhieb, was das Problem ist bzw. kennt die Lösung. Er meckert an, dass nur Arrays mit variablen Grenzen zulässig sind.

Quicksort.png
 
Welche Fehlermeldung wird dir denn angezeigt, wenn du den Baustein oder die ganze CPU einmal komplett übersetzen lässt? Ich habe gerade testweise einen FB mit einem InOut-Array und einer temp-Variable für die Größe angelegt und erhalte keine Ferhlermeldungen.
1707817683648.png

Edit: Und einfach weil es bisher noch nicht gefragt wurde: Welche CPU hast du projektiert? Welche Firmware? Und mit welcher TIA-Version arbeitest du?
 
@vollmi: Habs versucht so umzusetzen. Hin und her probiert, aber der Baustein ist immer weiter am meckern. Habe mal ein Bild angehangen. Vielleicht sieht man ja auf Anhieb, was das Problem ist bzw. kennt die Lösung. Er meckert an, dass nur Arrays mit variablen Grenzen zulässig sind.
Ist das dieselbe CPU in der du mit dem LREAL den Baustein übersetzen konntest? Also du hast nur auf UDT gewechselt aber Hard und Software belassen?
 
Zurück
Oben