QuickSort for PLC's

[Codeblue]

Hi all,


I was looking all over the internet for a QuickSort function implemented on a PLC but could not find one anywhere so here is one I have written using some C code as a template. See https://en.wikipedia.org/wiki/Quicksort AND https://www.toptal.com/developers/sorting-algorithms


Quicksort2: Implements iterative quick sort without the use of a stack.
Returns a sorted array and an array containing the index order of the original array.


This was written in ST using Schneider Control Expert V14; I will include the TXT below for all without CE V14.

(*
Quicksort2: Implements iterative quick sort without the use of stack.
Returns a sorted array and an array containing the index order of the original array.

WARNING: All Array sizes must be matched.*)

(*INITALISE VALUES*)
(*elements := UDINT_TO_INT(SIZEOF(IN:=INPUT_ARRAY) / SIZEOF(IN := INPUT_ARRAY[0]));*)
MAX_DEPTH := 300;
pivot := 0;
i := 0;
L := 0;
R := 0;
swap := 0;
LeftArr[0] := 0; 
RightArr[0] := elements;
ARR := INPUT_ARRAY;
FOR n := 0 TO (elements-1) BY 1 DO
    INDEX[n] := n;
END_FOR;
(*SORT*)
WHILE (i>=0) DO
    L := LeftArr[i]; 
    R := RightArr[i]-1;
    IF (L<R) THEN 
            pivot := arr[L];
        pivotPos := INDEX[L];
            WHILE (L<R) DO
                WHILE ((arr[R]>=pivot) AND (L<R)) DO 
                DEC(R);
            END_WHILE;
            IF (L<R) THEN
                arr[L] := arr[R];
                INDEX[L] := INDEX[R];
                INC(L);
            END_IF;
                WHILE ((arr[L]<=pivot) AND (L<R)) DO
                INC(L);
            END_WHILE;
            IF (L<R) THEN 
                arr[R] := arr[L];
                INDEX[R] := INDEX[L];
                DEC(R);                    
            END_IF;
        END_WHILE;
        INDEX[L] := pivotPos;
        arr[L] := pivot; 
        LeftArr[i+1] := L+1; 
        RightArr[i+1] := RightArr[i];  
        RightArr[i] := L;
        INC(i);
        IF ((RightArr[i]-LeftArr[i])>(RightArr[i-1]-LeftArr[i-1])) THEN
                swap := LeftArr[i]; 
            LeftArr[i] := LeftArr[i-1];
            LeftArr[i-1] := swap;
                swap := RightArr[i]; 
            RightArr[i] := RightArr[i-1]; 
            RightArr[i-1] := swap; 
        END_IF;
    ELSE
              DEC(i);
    END_IF;
END_WHILE;

 

[Codeblue]

If your PLC can do PUSH and POP to arrays then you can create a much smaller version of this function but CE V14 does not have any dynamic array capabilities.

 

[drbitboy]

Being that the number of values to be sorted will be small in a PLC (or else the scan watchdog will fault), I wonder what the O(NlogN) performance of Quicksort will be compared to a simpler O(N**2) algorithm (e.g. bubble sort). Also, the performance of Quicksort is dependent on the initial ordering, reaching O(N**2) in the worst case, so most Quicksort algorithm randomize the ordering first to make that problem vanishingly rare.

 

[chud]

If your PLC can do PUSH and POP to arrays then you can create a much smaller version of this function but CE V14 does not have any dynamic array capabilities.

It does have dynamic array capabilities. It must just be activated in the project settings.