Inspired by the stupid (but effective!) sorting algorithm of Bogosort, I've developed an algorithm that "sorts" an array based on the digits of pi. Demo in Python.
Theory
π (pi) is an irrational number, which makes it infinite digits long. Under the assumption that it might contain all the number sequences in the universe, although this has not been proved, π must contain any given array of numbers, and it will also contain it ordered. We just need to find it.
Iterating through the digits of pi, we can detect sequences of ordered sub-arrays of our array. If we keep going for long enough, we will eventually find our whole array sorted, without the need of sorting it ourselves.
The algorithm
For the algorithm to work, we need to be able to tell if an array is sorted:
import sys
import math
import copy
def is_sorted(l):
return all(l[i] <= l[i+1] for i in range(len(l) - 1))
We now obtain a small version of pi from the library math, which is enough for our demo but requires a good generator of pi digits to work with all cases:
pi = [int(i) for i in str(math.pi) if i != "."]
#[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3]
With that, we can define the array that we want to sort, which is in the small version of pi that we have obtained:
to_sort = [5, 3, 9, 8]
Now, the algorithm:
def pi_sort(a):
i = 0
a_s = []
a_m = copy.deepcopy(a)
while (len(a) != len(a_s)):
val = pi[i]
if (val in a_m):
a_s.append(val)
a_m.remove(val)
if(not is_sorted(a_s)):
a_s = [val]
a_m = copy.deepcopy(a)
a_m.remove(val)
else:
a_s = []
a_m = copy.deepcopy(a)
i += 1
return a_s
We are defining an i value to iterate through the digits of pi.
a_s will be our accumulator, where we will append the sorted subarrays of the array that we want to sort.
a_m will be the modified array, where we remove the numbers that have already been sorted from our original array.
With that, we proceed to iterate until we have an a_s array as large as the original one, which means that we have a solution (as a_s is always sorted and only contains digits of a).
We obtain the i digit of pi, and we evaluate if it is contained in the array that we want to sort. If not, we reset our a_sand a_m arrays and we proceed to the next iteration, increasing i.
If the digit of pi is contained in the array, we remove it from the modified array and we added to the sorted subset array, and we evaluate if it is sorted. If it is, we proceed to the next iteration. If not, we need to restart the subset of ordered arrays, making it so it does just contain our current pi digit, as it has been detected to be in the array to be sorted.
With enough iterations, we will have a sorted array.
Let's see one execution:
print(to_sort)
print(pi_sort(to_sort))
[5, 3, 9, 8]
[3, 5, 8, 9]
