The other day I felt my computer files were a little disorganized, so I went through some old files to do some hard-core cleanup. I wanted to purge and archive old programs, documents, and repos. While reviewing the files, I found some old C# code (from the days of when I tried to stay sharp through CodeWars), I wrote to test different sorting algorithms. Sorting algorithms are used to organize data in a specific order, and in my code, there was the good ole Bubble Sort, the Merge Sort, and their friend, the Quick Sort.
There are several options when sorting data, and depending on the data set, some are better than others. Once I came across the sorting code, For no other reason than wanting to, I strayed from my task and converted them to AL for Microsoft Dynamics 365 Business Central.
Bubble Sort
One such sorting algorithm is called Bubble Sort. It’s a basic comparison-based method that gets its name from how smaller or larger elements “bubble” to the top of the list. With a Bubble Sort, start at the beginning of the list and compare the first element to the second. If the first element is greater than the second, swap their positions. If not, leave them as they are. Move one position to the right and compare the second and third elements. Continue this process for each pair of adjacent numbers until the end of the list is reached. It’s important to note that Bubble Sort is not very efficient, especially for large lists.
procedure BubbleSort(List: List of [Integer])
var
i, j : Integer;
ListItem: Integer;
begin
for i := 1 to List.Count do begin
for j := 1 to List.Count - 1 do begin
if List.Get(i) < List.Get(j) then begin
ListItem := List.Get(i);
List.Set(i, List.Get(j));
List.Set(j, ListItem);
end;
end;
end;
end;
Merge Sort
Another option, if you need to sort data, is Merge Sort. This type of comparison-based sorting algorithm is effective for most practical data sets, especially on larger lists. The strategy is to divide and conquer. The data set is split in half continuously until each set contains only one element, which is considered a sorted list. Then, the adjacent lists are merged back together while maintaining sorted order. This is done by comparing the first elements of each list and adding the smaller one to the new list, then moving on to the next element in the list from which the element was taken. The process is repeated until all the elements have been merged back into a single sorted list. Compared to Bubble Sort, Merge Sort is more efficient.
procedure MergeSort(List: List of [Integer])
begin
MergeSort(List, 1, List.Count);
end;
local procedure Merge(List: List of [Integer]; Left: Integer; Middle: Integer; Right: Integer)
var
i, j, k : Integer;
LeftList: List of [Integer];
RightList: List of [Integer];
begin
for i := Left to Middle do begin
LeftList.Add(List.Get(i));
end;
for i := Middle + 1 to Right do begin
RightList.Add(List.Get(i));
end;
i := 1;
j := 1;
k := Left;
while (i <= LeftList.Count) and (j <= RightList.Count) do begin
if LeftList.Get(i) <= RightList.Get(j) then begin
List.Set(k, LeftList.Get(i));
i := i + 1;
end else begin
List.Set(k, RightList.Get(j));
j := j + 1;
end;
k := k + 1;
end;
while i <= LeftList.Count do begin
List.Set(k, LeftList.Get(i));
i := i + 1;
k := k + 1;
end;
while j <= RightList.Count do begin
List.Set(k, RightList.Get(j));
j := j + 1;
k := k + 1;
end;
end;
local procedure MergeSort(List: List of [Integer]; Left: Integer; Right: Integer)
var
Middle: Integer;
begin
if Left < Right then begin
Middle := (Left + Right) div 2;
MergeSort(List, Left, Middle);
MergeSort(List, Middle + 1, Right);
Merge(List, Left, Middle, Right);
end;
end;
Quick Sort
Quicksort is another efficient and commonly used sorting algorithm that uses a divide-and-conquer approach. It’s widely used due to its efficiency and ease of implementation. The first step in the Quicksort algorithm is to choose a pivot. The pivot can be any element from the array, but one commonly chooses the first, last, or middle elements. The role of the pivot is to assist in splitting the array. Next, rearrange the array elements so that all elements less than or equal to the pivot come before (to the left of) the pivot and all elements greater than the pivot come after (to the right of) the pivot. At this point, the pivot is in its final position in the sorted array.
procedure QuickSort(List: List of [Integer])
var
i: Integer;
begin
QuickSort(List, 1, List.Count);
end;
local procedure Partition(List: List of [Integer]; Left: Integer; Right: Integer): Integer
var
i, j : Integer;
Pivot: Integer;
begin
Pivot := List.Get(Right);
i := Left - 1;
for j := Left to Right - 1 do begin
if List.Get(j) <= Pivot then begin
i := i + 1;
Swap(List, i, j);
end;
end;
Swap(List, i + 1, Right);
exit(i + 1);
end;
local procedure QuickSort(List: List of [Integer]; Left: Integer; Right: Integer)
var
Pivot: Integer;
begin
if Left < Right then begin
Pivot := Partition(List, Left, Right);
QuickSort(List, Left, Pivot - 1);
QuickSort(List, Pivot + 1, Right);
end;
end;
local procedure Swap(List: List of [Integer]; i: Integer; j: Integer)
var
ListItem: Integer;
begin
ListItem := List.Get(i);
List.Set(i, List.Get(j));
List.Set(j, ListItem);
end;
Note: The code and information discussed in this article are for informational and demonstration purposes only. This content was created referencing Microsoft Dynamics 365 Business Central 2023 Wave 1 online.
available.
