Reg Exp
Web Design
Notes Client
Selection Sort In Formula Language
ND6 has a built-in @Sort function to sort an array in either ascending or descending order. But what if you have two arrays with the same number of values and you want to sort one while maintaining the relative positions within each array? For example, let say you have two fields - FirstName and LastName. Each field holds multiple values, and each field has the same number of elements. Each element in FirstName has a corresponding value in LastName. In this tip, we'll sort the FirstName field and maintain the positions between FirstName and LastName so that all the names will correctly map after the sorting has been completed.

First, we need to take a look at Selection Sort. This is a sorting algorithm that, although is not the most efficient, is pretty easy to implement. This makes it ideal for formula language. And since we are dealing with a small number of elements in each field, efficiency is not a big concern. The idea behind the algorithm is that you select the smalled unsorted item remaining in the list, and then swap that element with the item in the next position to be filled. So the array is built from the first position to the last position. Here's some pseudo-code of the function:

for i=0 to array_size-1
   min = i;
   for j=i+1 to array_size
      if numbers[j] < numbers[min] then min = j;
   if i <> min then swap(numbers[i], numbers[min])

The swap function simply swaps the two array values, so that the "numbers[i]" value is now at "numbers[min]" and vice versa. Last week we talked about how to perform a swap of a multi-value array in formula language. Using this knowledge, we just need to convert the rest of the pseudo-code into formula language. Keep in mind that the whole reason for doing this is because we have two fields. (If we only had 1 field, we would simply use @Sort). So we have to perform two swaps at the end.

F := FirstName;
L := LastName;
@For(x := 1; x < @Elements(F); x := x+1;
        SwapPos := x;
        @For(y := x+1; y <= @Elements(F); y := y+1;
            @If(F[y] < F[SwapPos]; SwapPos := y; 0)
        @If(SwapPos = x; 0; F := @Trim(@If(x = 1; ""; @Subset(F; x-1)) : F[SwapPos] : @If(SwapPos-x = 1; ""; @Subset(@Subset(F; SwapPos-1); x-SwapPos+1)) : F[x] : @If(SwapPos = @Elements(F); ""; @Subset(F; SwapPos-@Elements(F)))));
        @If(SwapPos = x; 0; L := @Trim(@If(x = 1; ""; @Subset(L; x-1)) : L[SwapPos] : @If(SwapPos-x = 1; ""; @Subset(@Subset(L; SwapPos-1); x-SwapPos+1)) : L[x] : @If(SwapPos = @Elements(L); ""; @Subset(L; SwapPos-@Elements(L)))))
FIELD FirstName := F;
FIELD LastName := L;

First, get temporary variables F and L so they are easier to work with. We go through all the first name values from 1 to the total number of elements minus 1. Each time through the loop, we perform all the tasks in the big @Do function.

Using the pseudo-code as a model, set a variable called SwapPos to the current loop element ("x"). Go through the unsorted elements (from "x" to the end of the list) and find the minimum value. So SwapPos will now be pointing to the element to be swapped.

If there is something to swap (if SwapPos changed), then perform the swap for both F and L. Refer to this document for an explanation of the swapping. That ends the big @Do function, which will continue the looping. Once the looping is done, the variables F and L can be placed back into the document fields FirstName and LastName. The function is then complete.

So there you have it. Using looping in formula language, we have created our own routine to sort one array while keeping the relative positioning between the array to be sorted and another array.