Community discussions

MUM Europe 2020
 
User avatar
TealFrog
just joined
Topic Author
Posts: 23
Joined: Sun Oct 02, 2011 11:56 am

Script to perform numeric sorting using a bubble sort

Thu Oct 13, 2011 8:55 am

I'm providing this script in the hopes others may find it useful. I suspect it might be able to be simplified a bit further. The script performs a numeric sort using a bubble sort. Ideally other sorts are faster and better, but given the scripting language and simplicity of the bubble sort it seems to be a good trade off. The script is fairly straight forward. In the first example it takes a numeric array, sorts it, and then prints out the sorted array. The first example is a basic template script that can be used and customized as needed.
# Mikrotik bubble sort implementation
# v1.1
:local A 5,4,3,2,1;
:local B;
:local n [ :len $A ];
:local swapped;
:put "Before unsorted $A";
do {
    :set swapped false;
    :for i from=1 to=($n - 1) do={
        :if ([ :pick $A ($i - 1) ]  > [ :pick $A $i ]) do={
            :set B [ :pick $A ($i - 1) ];
            :set A ([ :pick $A 0 ($i - 1) ], [ :pick $A $i ], $B, [ :pick $A ($i + 1) [ :len $A ] ]);
            :set swapped true;
        }
    }
    :set n ($n - 1);
} while=($swapped);
:put "After sorted $A";
The second example is a demonstration of the sort being used to sort an "/ip firewall address-list" containing a list of IP addresses. I use the script to sort IP addresses to make an ordered list to programmatically search for duplicate IP addresses.
:local ipAddrListName "some_list";
:local arrIpAddrList;
:local arrCommentList;
:local tempIpValue;
:local tempComment;
:local swapped false;
:local arrIdAddrList [ :toarray [ /ip firewall address-list find where list=$ipAddrListName ] ];
:if ([ :len $arrIdAddrList ] > 0) do={
    :foreach i in $arrIdAddrList do={
      :set arrIpAddrList ($arrIpAddrList, [ :toip [ /ip firewall address-list get $i address ] ]);
      :set arrCommentList ($arrCommentList, [ /ip firewall address-list get $i comment ]);
    }
    :local n [ :len $arrIpAddrList ];
    do {
        :set swapped false;
        :for i from=1 to=($n - 1) do={
            :if ([ :pick $arrIpAddrList ($i - 1) ]  > [ :pick $arrIpAddrList $i ]) do={
                :set tempIpValue [ :pick $arrIpAddrList ($i - 1) ];
                :set tempComment [ :pick $arrCommentList ($i - 1) ];
                :set arrIpAddrList ([ :pick $arrIpAddrList 0 ($i - 1) ], [ :pick $arrIpAddrList $i ], $tempIpValue, [ :pick $arrIpAddrList ($i + 1) [ :len $arrIpAddrList ] ]);
                :set arrCommentList ([ :pick $arrCommentList 0 ($i - 1) ], [ :pick $arrCommentList $i ], $tempComment, [ :pick $arrCommentList ($i + 1) [ :len $arrIpAddrList ] ]);
                :set swapped true;
            }
        }
        :set n ($n - 1);
    } while=($swapped);
    :if ($swapped = true) do={
# Remove the old entries
        :foreach i in $arrIdAddrList do={
            /ip firewall address-list remove $i;
        }
# Save the sorted entries
        :for i from=0 to=([ :len $arrIpAddrList ] - 1) do={
            /ip firewall address-list add list=$ipAddrListName \
            address=[ :pick $arrIpAddrList $i] comment="$[ :pick $arrCommentList $i ]";
        }
    }
}
Last edited by TealFrog on Fri Oct 14, 2011 10:39 am, edited 1 time in total.
TealFrog
 
User avatar
sadeghrafie
Long time Member
Long time Member
Posts: 515
Joined: Sat Nov 14, 2009 11:28 am
Location: Bushehr, IRAN

Re: Script to perform numeric sorting using a bubble sort

Thu Oct 13, 2011 9:41 pm

Hi
Thank you for this post, But this code has some problem like:
you can not use such code in MK for i from=1 to=($n - 1) to= must be an integer. Instead, :while (i<=n) do={:<Every task you want> :set i (i+1); }
Mikrotik Route My Life

Someone Says: Don't forget to give karma
 
User avatar
TealFrog
just joined
Topic Author
Posts: 23
Joined: Sun Oct 02, 2011 11:56 am

Re: Script to perform numeric sorting using a bubble sort

Fri Oct 14, 2011 8:12 am

Thank you for your feedback. The code is directly posted from working code. That is not to say that the code will work with every version of ROS and on every system. The code was developed and verified to run on a ROS v5.7 system. I have noticed MT scripting does have, to put it nicely, many subtleties in its syntax, and it may be more correct to do it the way that you have outlined. I did some testing and the "for loop" works as expected. There were some variations that I found that were interesting. Anyway, this type of code appears elsewhere including in the MT documentation, for example:

See "Traffic limiting per amount downloaded" section:

http://www.mikrotik.com/testdocs/ros/2. ... pting1.php

If the code does not work because of a backwards compatibilty issue or other issues, I'll be glad to change it

Regards.
TealFrog
 
User avatar
astounding
Member Candidate
Member Candidate
Posts: 121
Joined: Tue Dec 16, 2008 12:17 am

Re: Script to perform numeric sorting using a bubble sort

Fri Nov 21, 2014 10:24 pm

Here's my simple implementation of a recursive merge sort (works as of RouterOS 6.22 where it was implemented and used):
## Merge-sort a simple (non-associative) array:
##   NOTE: This only works if each array item can
##         be compared using the '<' operator.
/system script environment remove [ find where name="SortList" ];
:global SortList do={
  :global SortList;

  :local out [:toarray $1];
  :local l [:len $out];
  :if ($l>1) do={
    ## Split the list in two, recursively sort, then merge results

    ## Pick split point index:
    :local s ($l/2);

    ## Recursively sort each half-list:
    :local a [$SortList [:pick $out 0 $s]];
    :local b [$SortList [:pick $out $s $l]];

    ## Merge results:
    :set out [:toarray ""];
    :set l [:len $b];
    :local s 0;       ## Use $s as index into array $b
    :foreach i in=$a do={
      :local j [:pick $b $s];
      :while ($s<$l && $j<$i) do={
        :set out ($out,$j);
        :set s ($s+1);
        :set j [:pick $b $s];
      };
      :set out ($out,$i);
    };
    :while ($s<$l) do={
      :set out ($out,[:pick $b $s]);
      :set s ($s+1);
    };
  };
  :return $out;
};
Watch out for the global definition and the /system script environment bit (remove it or adapt it as needed). I use this in a global library script on some of my systems.

Example use from the CLI (after the above was defined/executed):
[admin@MikroTik] > :put [$SortList (55,-1,29,44,381,1,1,16,0,-234,44)]
-234;-1;0;1;1;16;29;44;44;55;381

Who is online

Users browsing this forum: MSN [Bot] and 26 guests