In order to exercise in the new NAV Modern Development Environment I thought to implement a comparison of two sorting algorithms directly in Visual Studio Code AL Language: Insertion Sort and Merge Sort.
Most of the sorting examples over the internet are using arrays, but the issue with arrays is they have fixed length that needs to be declared upfront. Of course I didn’t like this even if it is just an example with educational purpose. Or someone maybe will use it also for a real situation, we’ll see.
As I said also in a previous post, the AL Language has now a built in List wrapper. The problem is that this List does not have a Sort method:
Before I started to write this post I implemented the Insertion Sort using temporary tables because I was sure that the List has it’s own Sort method so it wouldn’t be fun to create something that already exists and performs much better. But it seems it’s not the case. How did Microsoft miss this one ?
So I created a new AL extension:
For this project, first I created a Setup Page:
Here, there are 2 options of running the sorting algorithms:
1) CreateInMemory: The Random numbers that will be sorted are created at run time, in memory: this is fine for small tests, but in case of more than 10000 numbers, it takes too long time to populate the List/Temp Table with random numbers.
2) CopyFromDatabase: The Random Numbers are first Created in the database in a table called “Random Numbers” which looks like this in SQL Server:
Then, when we run the sorting algorithms we just copy the random numbers from the database instead of generating them at runtime. This way, we can test the sorting algorithms on much larger sets of numbers. It will take some time just once (when we populate the table). For example for 1.000.000 random numbers it took about 4-5 minutes for this system:
It takes so long because my method of creating these random numbers creates unique random numbers. For example if you want the numbers from 1 to 1000 but mixed up. Or you can have 1000 unique mixed up numbers picked up from numbers between 1 to 3000. For everything up to 1.000.000 it’s ok, but for more it is pretty slow. If you have a faster way of doing this please write a comment 🙂
In this setup page you can see also other fields:
– No of Random Numbers in Memory: specifies the number of random numbers created in memory in an AL List or Nav Temporary table.
– Random Selection Max Number Memory: ex: if you want to generate in memory 5 random numbers selected from numbers between 1 to 10 you will specify here 10; if you want 5 number from 1 to 5 you specify here 5 etc.
– No Of Random Nos Real Table: specifies the number of random numbers created and inserted into database by function “Populate Random Numbers Table”
– Random Selection Max Number Table: similar to “Random Selection Max Number Memory” but for the numbers inserted into the database.
– Maximum Values Displayed in Message: after you sort numbers, the program displays the initial numbers (unsorted) and resulted numbers (sorted) in a message. In case you have a lot of numbers the message cannot display because the text is too long. By filling this field the program will display only the numbers until the value specified in it. Ex: if you sorted 100.000 numbers and this value is 300 the program displays first 300 numbers and text: “and 99.700 more”.
If you want to use the option RunMode = CopyFromDatabase you first have to populate the Random Numbers Table. When you select this option I implemented a check: in case the Random Numbers table is empty, it will ask if you want to populate it. If you select Yes, it will run the same script as action “Populate Random Number”.
field(9;RunMode; Option) { OptionMembers = CopyFromDatabase,CreateInMemory; trigger OnValidate(); var RandomNos : Record RandomNumbers; RandomNosMgt : Codeunit RandomNosMgt; RandomTabEmptylbl : label '%1 is empty. Do you want to run job to populate it ?'; begin If RunMode = RunMode::CopyFromDatabase then If RandomNos.IsEmpty then If Confirm(StrSubstNo(RandomTabEmptylbl,RandomNos.TableCaption)) and (NoOfRandomNosRealTable > 0) then RandomNosMgt.FillRealRecWithRandomNumbers(NoOfRandomNosRealTable,RandomSelectionMaxNumberTable); end; }
If you use action “Populate Random Numbers” and you already have data in the Random Numbers table, it will delete all existing data and create a new set of numbers.
–> The logic of generating the Random numbers is the same for the table/temp table and list. The code that populates the table is this one:
procedure FillRealRecWithRandomNumbers(NumberOfValuesWanted : Integer; RandomSelectionMaxNumber : Integer) var i : integer; ListOfInt : List Of [Integer]; RandomNumbers : Record RandomNumbers; intprimarykey : Integer; randomposition : integer; RemainedRandomNumbers : Integer; ProgressWindow : Dialog; begin If NOT RandomNumbers.IsEmpty then Exit; //values already were added at a previous run //add values to List for i := 1 to RandomSelectionMaxNumber do ListOfInt.Add(i); ProgressWindow.Open('Creating Random Nos @1@@@@@@@@@'); RemainedRandomNumbers := RandomSelectionMaxNumber; //select random values from List and add to RandomNumbers. Then delete the added number from ListOfInt for i := 1 to NumberOfValuesWanted do begin ProgressWindow.UPDATE(1,ROUND(i / NumberOfValuesWanted * 10000,1)); randomposition := random(RemainedRandomNumbers); //get a random position //add value to RandomNumbers RandomNumbers.PrimaryKey := intprimarykey; RandomNumbers.RandomNumber := ListOfInt.Get(randomposition); RandomNumbers.Insert; intprimarykey += 1; //detele value from ListOfInt to have only unique random numbers ListOfInt.RemoveAt(randomposition); RemainedRandomNumbers -= 1; If RemainedRandomNumbers = 0 THEN //in case someone inputs more wanted values than the RandomNumbers break; end; ProgressWindow.Close; end;
So, I hope I explained clear enough how I designed this small app. Now, I will explain how I implemented the Insertion Sort using the AL List, then Nav temporary tables and I will leave for the end the Merge Sort. (start with an easy thing and finish with a more complicated one).
The logic of the Insertion Sort algorithm is very simple and nice to my opinion. I created the bellow example to explain it:
Now let’s see the implementations in AL
1) Insertion Sort Using AL List:
codeunit 50101 InsertionSortList { trigger OnRun(); var RandomNumbersList : List of [Integer]; InitialRandomValuesString : Text; ResultedSortedValuesString : Text; MessageText : TextConst ENU = 'Initial Numbers:\\%1\\Sorted Numbers:\\%2'; StartTime : DateTime; EndTime : DateTime; ExecutionTime : DateTime; RandomNosMgt : Codeunit RandomNosMgt; RandomNosSetup : Record RandomNosSetup; begin RandomNosSetup.Get; If RandomNosSetup.RunMode = RandomNosSetup.RunMode::CreateInMemory Then RandomNosMgt.FillRandomNumbersList(RandomNumbersList, RandomNosSetup.NoOfRandomNosInMemory,RandomNosSetup.RandomSelectionMaxNumberMemory) Else RandomNosMgt.FillRandomNumbersListFromRealTable(RandomNumbersList); RandomNosMgt.CreateStringWihValuesList(RandomNumbersList,InitialRandomValuesString); //generate string for message StartTime := CurrentDateTime; InsertionSort(RandomNumbersList); EndTime := CurrentDateTime; RandomNosMgt.CreateStringWihValuesList(RandomNumbersList,ResultedSortedValuesString); //generate string for message Message('Executed in %1',EndTime-StartTime); Message(MessageText,InitialRandomValuesString,ResultedSortedValuesString); end; var local procedure InsertionSort(RandomNumbersList : List of [Integer]); var NumberOfElements : integer ; i : Integer; j : integer; CurrentElement : Integer; ProgressWindow : Dialog; begin ProgressWindow.Open('Sorting Random Nos @1@@@@@@@@@'); NumberOfElements := RandomNumbersList.Count; for i := 2 to NumberOfElements do begin ProgressWindow.UPDATE(1,ROUND(i / NumberOfElements * 10000,1)); CurrentElement := RandomNumbersList.Get(i); j := i-1; while RandomNumbersList.Get(j) > CurrentElement do begin RandomNumbersList.Set(j+1,RandomNumbersList.get(j)); j -= 1; if j = 0 then break; end; RandomNumbersList.Set(j+1,CurrentElement); end; ProgressWindow.Close; end; }
2) Insertion Sort Using Nav temporary table (pretty slow for a lot of random numbers because of the next statements. Just as exercise. If you have a better way of doing it please share it):
local procedure InsertionSort(var tempRandomNumbers : Record RandomNumbers temporary; NosCount : Integer); var CurrKey : Integer; CurrValue : Integer; IntToMoveRight : Integer; StepsMovedLeft : Integer; swapped : Boolean; ProgressWindow : Dialog; i: integer; begin ProgressWindow.Open('Sorting Random Nos @1@@@@@@@@@'); If tempRandomNumbers.FindSet then begin tempRandomNumbers.Next(1); //start with second record repeat i+=1; ProgressWindow.UPDATE(1,ROUND(i / NosCount * 10000,1)); swapped := false; CurrKey := tempRandomNumbers.PrimaryKey; CurrValue := tempRandomNumbers.RandomNumber; //move to the right any numbers greater than the current one StepsMovedLeft := tempRandomNumbers.Next(-1); while (StepsMovedLeft < 0) AND (tempRandomNumbers.RandomNumber > CurrValue) do begin IntToMoveRight := tempRandomNumbers.RandomNumber; tempRandomNumbers.Next(1); tempRandomNumbers.RandomNumber := IntToMoveRight; tempRandomNumbers.Modify; tempRandomNumbers.Next(-1); StepsMovedLeft := tempRandomNumbers.Next(-1); swapped := true; end; // if items where moved to right, if swapped then begin If StepsMovedLeft < 0 then tempRandomNumbers.Next(1); tempRandomNumbers.RandomNumber := CurrValue; tempRandomNumbers.Modify; end; tempRandomNumbers.Get(CurrKey); //go back to initial record until tempRandomNumbers.Next = 0; end; ProgressWindow.Close; end;
3) Now, the merge sort. The logic of this algorithm is best explained in this link.
This is much, much faster than Insertion Sort and other simple algorithms: for example it can sort millions of random numbers in just few seconds while the insertion sort needs minutes for 100.000 random numbers.
Let’s see the implementation of Merge Sort in Visual Studio Code using the AL List:
local procedure MergeSort(RandomNosList : List of [Integer]; leftStart : integer; rightEnd : Integer); var middle : integer; begin if leftStart >= rightEnd then Exit; middle := round(((leftStart-1 + rightEnd) / 2),1,'>'); MergeSort(RandomNosList,leftStart,middle); MergeSort(RandomNosList,middle+1,rightEnd); MergeHalves(RandomNosList,leftStart,rightEnd); end; local procedure MergeHalves(RandomNosList : List of [Integer]; leftStart : integer; rightEnd : Integer); var i : Integer; j : integer; k : Integer; leftEnd : integer; rightStart : Integer; x : integer; y:integer; tempList : List of [Integer]; begin leftEnd := Round(((rightEnd + leftStart - 1) / 2),1,'>'); rightStart := leftEnd + 1; i := leftStart; j := leftEnd + 1; k := leftStart; //create temp sorted list while (i <= leftEnd) and (j <= rightEnd) do begin If RandomNosList.Get(i) < RandomNosList.Get(j) then begin tempList.Add(RandomNosList.Get(i)); i+=1; end else begin tempList.Add(RandomNosList.Get(j)); j+=1; end; k+=1; end; while i < leftEnd + 1 do begin tempList.Add(RandomNosList.Get(i)); //add remaing elements from left list i += 1; end; while j < rightEnd + 1 do begin tempList.Add(RandomNosList.Get(j)); //add remaing elements from right list j += 1; end; //copy sorted elements to main list y := leftStart; for x := 1 to tempList.Count do begin RandomNosList.Set(y,tempList.Get(x)); y+=1; end; end;
–> Performance Comparison:
No. Of Random Nos. | Insertion sort temp table | Insertion Sort List | Merge Sort List |
---|---|---|---|
1.000 | 4 seconds | 110 miliseconds | 10 miliseconds |
5.000 | 1 minute 15 seconds | 2 seconds | 110 miliseconds |
10.000 | 5 minutes 29 seconds | 8 seconds | 120 miliseconds |
50.000 | N/A | 2 minutes 55 seconds | 500 miliseconds |
100.000 | N/A | 11 minutes 30 seconds | 1 second |
250.000 | N/A | N/A | 2.5 seconds |
500.000 | N/A | N/A | 5 seconds |
1.000.000 | N/A | N/A | 11 seconds |
5.000.000 | N/A | N/A | 1 minute |
–> Quick presentation video of how to use the sorting app:
*I used the Windows client because in the current Web Client there is a limitation and the Progress Dialog is not displayed correctly.
Conclusions:
– The insertion sort performs good when there are not a lot of numbers to be sorted or it is used for numbers that are already “almost” sorted. For example in case of adding new numbers to a previusly sorted list and then sorting the list again. For random numbers it works fine for 1000-3000 numbers, but in case of more than 10000 it takes some time. For this kind of situations there are better sorting algorithms, for example the Merge Sort.
– When possible use the AL List. It can be much faster compared to temporary tables for a lot of situations. Depending, of course, on your algorithm that uses it.
– If you need to sort an AL List, you can use the Merge Sort from this project until Microsoft implements the sorting method for this object in AL.
Next Steps:
– It would be interesting to create the QuickSort algorithm in NAV as well, in order to compare it with the Merge Sort, but I didn’t have time to do also that. Maybe will do it in future or if someone else does it, please share.
I hope you enjoyed this exercise with sorting algorithms, you can download the app from below GitHub link, install in NAV and play with it. Folder “SortingMethods“:
https://github.com/andreilungu/NAV_AL