Community discussions

MikroTik App
 
User avatar
TealFrog
just joined
Topic Author
Posts: 23
Joined: Sun Oct 02, 2011 11:56 am

Another (Faster) Sort Based on QuickSort Algorithm

Sat Oct 29, 2011 8:44 am

Being that I was unhappy with the performance of the previous script based on a bubble sort algorithm, I rewrote the script using a QuickSort algorithm. The script is meant to sort numeric data. The first script in this post is the raw script to do plain numeric sorting demonstrating the QuickSort. It is meant for illustration purposes only. The second script is a working example used to sort an IP address list. The second script benefits from the fact that it sorts based on the IP address, but manipulates the array by the internally represented numeric ROS identifiers.

The sorting scripts were originally written to sort IP address lists allowing quicker and easier removal of duplicate IP addresses from the IP address list. Since the initial development I have switched to a different method, but I am sharing the scripts here in the hopes that someone may have a use for them.

Warning: Please note if the second script is used and the "saveList" Boolean variable is set to "true", the script is destructive in that the IP addresses contained in the specified input list are removed and then re-added in sorted order. The script also does not preserve the comment field. The script could easily be modified to keep comments with a couple of additional lines of code. Since entries are removed and re-added this is especially important with regards to dynamically created IP address entries as the entries lose their associated expiration time/date values.
# QuickSort
# v1.0
# Script developed and tested on ROS v5.7
# Assign numeric values to sort to array a
:local a ( 84, 99, 3, 56, 49, 6, 54, 11, 13, 93, 46, 48, 2, 62, 62, 22, 87, 88, 65, 54, 63, 23, 15, 20, 35, 85, 85, 30, 54, 38, 80, 80, 19, 18, 44, 61, 50, 41, 34, 95, 53, 30, 100, 83, 34, 14, 60, 48, 81, 65, 93, 78, 100, 81, 99, 85, 96, 84, 48, 72, 49, 64, 51, 56, 98, 83, 41, 91, 82, 41, 100, 39, 100, 52, 87, 64, 35, 33, 64, 82, 6, 39, 99, 16, 98, 51, 54, 60, 25, 61, 72, 24, 12, 36, 87, 35, 47, 7, 28, 98 );
:local c 0;
:local i 0;
:local l 0;
:local items [ :len $a ];
:local r ( $items - 1 );
:local s ( $l, $r );
:local j;
:local k;
:local v1;
:local v2;
:local pivot;
:local doit1 true;
:local doit2 true;
:put "Before sorting..."
:put $a;
:put "Sorting $items items.";
:local lcv 0;
:while ( ( [ :len $s ] ) > 0 ) do={
    :set lcv ( $lcv + 1 );
    :put ("Pass # " . $lcv );
# pop stack x2        
    :set r [ :pick $s [ :tonum ( [ :len $s ] - 1) ] ];
    :set l [ :pick $s [ :tonum ( [ :len $s ] - 2) ] ];
    :set s [ :pick $s 0 ( [ :len $s ] - 2 ) ];
# done popping stack        
    :if ( $r <= $l ) do={
# NOP
    } else={        
        :set i ( [ :tonum $l ] - 1 ); 
        :set j [ :tonum $r ]; 
        :set pivot [ :pick $a $r ];
        :set doit1 true;
        :while ($doit1 = true) do={
            :set i ( [ :tonum $i ] + 1 );
            :while ( ( [ :pick $a $i ] ) < $pivot) do={
                :set i ( [ :tonum $i ] + 1 );
            }
            :set doit2 true;
            :set j ( [ :tonum $j ] - 1 );
            :while ((  $doit2 = true ) and ($pivot < ( [ :pick $a $j ] ) ) ) do={
                :if ( $j = $l ) do={
                    :set doit2 false;
                } else={
                    :set j ( [ :tonum $j ] - 1 );
                }                
            }            
            :if ($i >= $j) do={
               :set doit1 false;
            }  else={
# Start swapping array elements 
                :set v1 [ :pick $a [ :tonum $i ] ];
                :set v2 [ :pick $a [ :tonum $j ] ];
                :if ( $i = 0 ) do={
                    :set a ($v2, [ :pick $a (([ :tonum $i ])+1) $items ]); 
                } else={
                    :set a ([ :pick $a 0 [ :tonum $i ] ], $v2, [ :pick $a (([ :tonum $i ])+1) $items ]); 
                }
                :if ( $j = 0 ) do={
                    :set a ($v1, [ :pick $a (([ :tonum $j ])+1) $items ]); 
                } else={
                    :set a ([ :pick $a 0 [ :tonum $j ] ], $v1, [ :pick $a (([ :tonum $j ])+1) $items ]); 
                }
# Done swapping array elements
            }
        }            
# Start swapping array elements 
                :set v1 [ :pick $a [ :tonum $i ] ];
                :set v2 [ :pick $a [ :tonum $r ] ];
                :if ( $i = 0 ) do={
                    :set a ($v2, [ :pick $a (([ :tonum $i ])+1) $items ]);
                } else={
                    :set a ([ :pick $a 0 [ :tonum $i ] ], $v2, [ :pick $a (([ :tonum $i ])+1) $items ]);
                } 
                :if ( $r = 0) do={
                    :set a ($v1, [ :pick $a (([ :tonum $r ])+1) $items ]);                 
                } else={
                    :set a ([ :pick $a 0 [ :tonum $r ] ], $v1, [ :pick $a (([ :tonum $r ])+1) $items ]); 
                }
# Done swapping array elements
        :if (($i-$l) > ($r-$i)) do={
            :set s ($s, $l, (( [ :tonum $i] )-1));             
        }
        :set s ($s, (([ :tonum $i ])+1), [ :tonum $r ]);             

        :if (($r-$i) >= ($i-$l)) do={
            :set s ($s, [ :tonum $l ], (([ :tonum $i ])-1));
        }
    }    
}
:put "Finished sorting $[ :len $a ] items.";
:put "After sorting...";
:put $a;
:put "Done.";
# QuickSort IP Address List (Example)
# v1.0
# Script developed and tested on ROS v5.7
# Script shows QuickSort usage by sorting IP address list
#
# Replace the "some_list" below with the name of IP list to sort
:local addrList "some_list";
# Set saveList to true or false, if set to true the list will be overwritten with sorted IPs.
# If saveList is set to false, then sort IPs are displayed on console (:put).
:local saveList false;
:local a {};
:foreach id in=[ /ip firewall address-list find where list=$addrList ] do={
    :set a ($a, $id);
}
:local c 0;
:local i 0;
:local l 0;
:local items [ :len $a ];
:local r ( $items - 1 );
:local s ( $l, $r );
:local j;
:local k;
:local v1;
:local v2;
:local pivot;
:local doit1 true;
:local doit2 true;
:put "Before sorting..."
:put $a;
:put "Sorting $items items.";
:local lcv 0;
:while ( ( [ :len $s ] ) > 0 ) do={
    :set lcv ( $lcv + 1 );
    :put ("Pass # " . $lcv );
# pop stack x2        
    :set r [ :pick $s [ :tonum ( [ :len $s ] - 1) ] ];
    :set l [ :pick $s [ :tonum ( [ :len $s ] - 2) ] ];
    :set s [ :pick $s 0 ( [ :len $s ] - 2 ) ];
# done popping stack        
    :if ( $r <= $l ) do={
# NOP
    } else={        
        :set i ( [ :tonum $l ] - 1 ); 
        :set j [ :tonum $r ]; 
        :set pivot [ :toip [/ip firewall address-list get [ :pick $a $r ] address ] ];
        :set doit1 true;
        :while ($doit1 = true) do={
            :set i ( [ :tonum $i ] + 1 );
            :local ip1 [ :toip [/ip firewall address-list get [ :pick $a $i ] address ] ];
            :while ( $ip1 < $pivot) do={
                :set i ( [ :tonum $i ] + 1 );
                :set ip1 [ :toip [/ip firewall address-list get [ :pick $a $i ] address ] ];
            }
            :set doit2 true;
            :set j ( [ :tonum $j ] - 1 );
            :set ip1 [ :toip [/ip firewall address-list get [ :pick $a $j ] address ] ];
            :while ((  $doit2 = true ) and ($pivot < $ip1 ) ) do={
                :if ( $j = $l ) do={
                    :set doit2 false;
                } else={
                    :set j ( [ :tonum $j ] - 1 );
                    :set ip1 [ :toip [/ip firewall address-list get [ :pick $a $j ] address ] ];
                }                
            }            
            :if ($i >= $j) do={
               :set doit1 false;
            }  else={
# Start swapping array elements 
                :set v1 [ :pick $a [ :tonum $i ] ];
                :set v2 [ :pick $a [ :tonum $j ] ];
                :if ( $i = 0 ) do={
                    :set a ($v2, [ :pick $a (([ :tonum $i ])+1) $items ]); 
                } else={
                    :set a ([ :pick $a 0 [ :tonum $i ] ], $v2, [ :pick $a (([ :tonum $i ])+1) $items ]); 
                }
                :if ( $j = 0 ) do={
                    :set a ($v1, [ :pick $a (([ :tonum $j ])+1) $items ]); 
                } else={
                    :set a ([ :pick $a 0 [ :tonum $j ] ], $v1, [ :pick $a (([ :tonum $j ])+1) $items ]); 
                }
# Done swapping array elements
            }
        }            
# Start swapping array elements 
                :set v1 [ :pick $a [ :tonum $i ] ];
                :set v2 [ :pick $a [ :tonum $r ] ];
                :if ( $i = 0 ) do={
                    :set a ($v2, [ :pick $a (([ :tonum $i ])+1) $items ]);
                } else={
                    :set a ([ :pick $a 0 [ :tonum $i ] ], $v2, [ :pick $a (([ :tonum $i ])+1) $items ]);
                } 
                :if ( $r = 0) do={
                    :set a ($v1, [ :pick $a (([ :tonum $r ])+1) $items ]);                 
                } else={
                    :set a ([ :pick $a 0 [ :tonum $r ] ], $v1, [ :pick $a (([ :tonum $r ])+1) $items ]); 
                }
# Done swapping array elements
        :if (($i-$l) > ($r-$i)) do={
            :set s ($s, $l, (( [ :tonum $i] )-1));             
        }
        :set s ($s, (([ :tonum $i ])+1), [ :tonum $r ]);             

        :if (($r-$i) >= ($i-$l)) do={
            :set s ($s, [ :tonum $l ], (([ :tonum $i ])-1));
        }
    }    
}
:put "Finished sorting $[ :len $a ] items.";
:put "After sorting...";
:put $a;
:foreach id in $a do={
    :local ip1 [ /ip firewall address-list get $id address ];
    :if ($saveList) do={
        :put "Removing ID: $id with IP address $ip1 from $addrList";
        /ip firewall address-list remove $id
        :put "Adding ordered IP address $ip1 to $addrList";
        /ip firewall address-list add list=$addrList address=$ip1
    } else={
        :put "IP Address: $ip1";
    }
}
:put "Done.";

Who is online

Users browsing this forum: No registered users and 16 guests