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.
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;
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;
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.