Best Sorting Algorithm Bogosort

1

I implemented the algorithm Bogosort in FileMaker:

While(
[
unsorted_list = "Banana¶Cherry¶Kiwi¶Apple¶Peach¶Pinapple";
random_list = unsorted_list;
test = 0
];
test = 0;
[
random_list = While(
[
unsorted_list = unsorted_list;
count = ValueCount(unsorted_list);
random_list = ""
];
count > 0;
[
random_value = Round(Random * (count - 1) + 1; 0);
random_list = List(random_list; GetValue(unsorted_list; random_value));
unsorted_list = FilterValues(
List(
LeftValues(unsorted_list; random_value - 1);
RightValues(unsorted_list; count - random_value)
);
unsorted_list
);
count = count - 1
];
random_list
);
test = While(
[
random_list = random_list;
count = ValueCount(random_list);
test = ""
];
count > 1;
[
test = test + (GetValue(random_list; count) < GetValue(random_list; count - 1));
count = count - 1
];
test = 0
)
];
random_list
)

Wishing you a great start to April – Jan

3 Likes
2

hi @janhagemeister

Thanks for this function. There are however some serious issues with it in testing.

First I turned this into a custom function that accepted a return delimited list as parameter, and updated your hard-coded list at the top to be the parameter.

In passing a list of 6 values, the results of the Custom function varied quite a bit. It would jump from 170 ms to 60ms to 400ms , quite variable!

However, compare that to the native SortValues function which performed the same action in 0ms (I switched to microseconds and it's about 20 microseconds).

Your function also suffers from serious performance issues the more values that are added, almost exponentially worse. Increasing the size of the list to 8 values resulted in your function taking 5,365 milliseconds (5.3 seconds!) compared to 0ms again for SortValues.

There is something fundamentally broken in there where increasing the amount of values even by 1 each time results in serious delays. Hopefully a quick fix in your code somewhere, however I don't know where.

I would however strongly consider just using SortValues function as this is highly optimised and will be significantly faster than any function you write. This is because your function also makes use of a number of other FileMaker functions:

• While (x2)
• ValueCount
• Round
• Random
• List
• GetValue
• FilterValues
• LeftValues
• RightValues

The high use of additional functions, and the fact you have nested while loops, is always going to be slower, not to mention those functions such as LeftValues, FilterValues and RightValues become quite slow as lists get larger - and we're talking 10s of thousands of values, not 8 !

1 Like
3

Isn't a Bogosort an intentionally complex and therefore slow (and not recommended) way of sorting? This seems to be an interesting proof of concept, but never to be used in production.

4
5

April fool's perhaps?

4 Likes
6

Of course, Bogosort is the worst algorithm on Earth. It belongs to the class of Las Vegas algorithms, and we never know how long it will take to complete.

With my example, I want to show how outdated FileMaker’s function logic has become. FileMaker is being technologically left behind more and more.

@weetbicks you’re absolutely right — the built-in functions are painfully slow.

In Python, Bogosort can be implemented like this:

from random import shuffle

def bogosort(data: list) -> list:

while not all(a <= b for a, b in zip(data, data[1:])):

    shuffle(data)

return data

In FileMaker, it’s much more complicated — mainly because there’s no built-in Shuffle() function without a plugin (e.g MBS).

I wrote my own implementation since I couldn’t find one that also handles duplicate entries correctly.

That said, Shuffle() is actually very useful, unlike Bogosort:

While(
[
unsorted_list = "Banana¶Cherry¶Kiwi¶Apple¶Peach¶Pinapple";
count = ValueCount(unsorted_list);
random_list = ""
];
count > 0;
[
random_value = Round(Random * (count - 1) + 1; 0);
random_list = List(random_list; GetValue(unsorted_list; random_value));
unsorted_list = FilterValues(
List(
LeftValues(unsorted_list; random_value - 1);
RightValues(unsorted_list; count - random_value)
);
unsorted_list
);
count = count - 1
];
random_list
)

Thank you

Jan

2 Likes
7

Egg on my face lol you got me !

Here I am trying to figure out why the function is behaving as poorly as it did lol !

:blush:

3 Likes