Verschiedene Sortiermethoden im Vergleich

[vollmi]

Zuviel Werbung?
-> Hier kostenlos registrieren

Hab grad ein nettes Video gesehen das die verschiedenen Sortiermethoden vergleicht.
Nett!

Vielleicht hilfts dem einen oder anderen in der Entscheidungsfindung.

 

[DeltaMikeAir]

Da hat sich aber einer Mühe gegeben.

Danke fürs einstellen.

 

[vollmi]

Zuviel Werbung?
-> Hier kostenlos registrieren

Jo ich finds ziemlich gut. Das Gif kann man auch gut speichern. Ich hab noch das Youtube Video beigefügt das ich immer zum Zeigen genommen habe.

 

[vollmi]

Ich hab da den Quicksort Algorythmus aus der Oscat Library für mich schon öfter verwendet in abgewandelter Form. Der Funktioniert ja auch tadellos.
Dabei verstehe ich aber nicht wirklich, warum der STACK im statischen Bereich liegen muss. Der wird ja nur innerhalb der Schleife verwendet und beim nächsten Zyklus eh ab erster Stelle neu beschrieben.

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 *)

 

[Thomas_v2.1]

Vielleicht um den L-Stack etwas zu entlasten?
Die meisten Oscat Funktionen wurden für Codesys geschrieben und dann auf Siemens portiert. Und bei Codesys gibt es überhaupt kein VAR_TEMP, bzw. wird das gleich VAR behandelt. Ohne nachzudenken begeht man mit VAR zumindest keinen Fehler, wenn man nicht versteht was da abläuft.