<jupyter_start><jupyter_text>Based on Approximating Lipschitz continuous functions withGroupSort neural networksGroup sort is really coolup to know no certification pertubation analysis have been proposedinspired from Lirpa based methods, we analyse different sort methods and their linear relaxations to apply CROWN IBP on GroupSort Neural Networkq The algorithms we will cover are:Bubble sortSelection sortMerge sortsources: https://towardsdatascience.com/3-must-know-sorting-algorithms-7ce725fee9f5<jupyter_code>def get_toy_example():
    return [3, 2, 8, 4, 1, 5]

def get_toy_example_ibp(eps):
    L_min = [e - eps_i for (e, eps_i) in zip(get_toy_example(), eps)]
    L_max = [e + eps_i for (e, eps_i) in zip(get_toy_example(), eps)]
    
    return L_min, L_max<jupyter_output><empty_output><jupyter_text>1) Bubble sortIn bubble sort algorithm, we go over a sequence of numbers by comparing consecutive numbers. If a number is smaller than its previous number, we swap them. We keep going over the list until all numbers are sorted.<jupyter_code>def bubble_sort(L):
    
    swap = False
    while not swap:
        swap = True
        for j in range(1, len(L)):
            if L[j-1] > L[j]:
                swap = False
                L[j], L[j-1] = L[j-1], L[j]
    print(L)
def bubble_sort_lirpa(L):
    for _ in range(len(L)**2):
        for j in range(1, len(L)):
            a = max(L[j], L[j-1])
            b = min(L[j], L[j-1])
            
            L[j]=a
            L[j-1]=b
            
    print(L)
def max_ibp(x_min, x_max, y_min, y_max):
    return max(x_min, y_min), max(x_max, y_max)

def min_ibp(x_min, x_max, y_min, y_max):
    return min(x_min, y_min), min(x_max, y_max)

def bubble_sort_IBP(L_min, L_max):
    n = len(L_min)
    for _ in range(n**2):
        for j in range(1, n):
            a_min, a_max = max_ibp(L_min[j], L_max[j], L_min[j-1], L_max[j-1])
            b_min, b_max = min_ibp(L_min[j], L_max[j], L_min[j-1], L_max[j-1])
            
            L_min[j] = a_min
            L_max[j] = a_max
            L_min[j-1] = b_min
            L_max[j-1] = b_max
            
    print(L_min)
    print(L_max)
bubble_sort(get_toy_example())
bubble_sort_lirpa(get_toy_example())
L_min, L_max = get_toy_example_ibp([0, 2.1, 0.2, 0.4, 1, 0.05])
bubble_sort_IBP(L_min, L_max)<jupyter_output>[-0.10000000000000009, 0, 3, 3.6, 4.95, 7.8]
[2, 3, 4.1, 4.4, 5.05, 8.2]<jupyter_text>2) Selection SortThe selection sort algorithm takes the first number and starting from the second one, all other numbers are compared with the first number. If a number is smaller than the first number, they are swapped.When the first iteration is complete, we make sure the smallest number is at the beginning of the list. Then, we take the second number and repeat the same process.After the execution is completed, the list is sorted in ascending order.<jupyter_code>def selection_sort(L):
    
    for i in range(len(L)-1):
        for j in range(i+1, len(L)):
            if L[j] < L[i]:
                L[i], L[j] = L[j], L[i]
                
    print(L)
def selection_sort_lirpa(L):
    
    for i in range(len(L)-1):
        for j in range(i+1, len(L)):
            a = max(L[j], L[i])
            b = min(L[j], L[i])
            
            L[j] = a
            L[i] = b
    print(L)
selection_sort(get_toy_example())
selection_sort_lirpa(get_toy_example())
def selection_sort_IBP(L_min, L_max):
    n = len(L_min)
    for i in range(n-1):
        for j in range(i+1, n):
            a_min, a_max = max_ibp(L_min[j], L_max[j], L_min[i], L_max[i])
            b_min, b_max = min_ibp(L_min[j],  L_max[j], L_min[i],  L_max[i])
            
            L_min[j] = a_min
            L_max[j] = a_max
            L_min[i] = b_min
            L_max[i] = b_max
            
    print(L_min)
    print(L_max)
L_min, L_max = get_toy_example_ibp([0, 2.1, 0.2, 0.4, 1, 0.05])
selection_sort_IBP(L_min, L_max)
# do an interactive plot
l = get_toy_example()

def func(i):
    l[i]=-1
l
func(5)
l<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12109955423476969, 'fraction_numerical': 0.024764735017335313, 'mean_word_length': 2.655203619909502, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '483351', 'license': 'MIT', 'n_tokens_mistral': 1614, 'n_tokens_neox': 1554, 'n_words': 419, 'path': 'tests/notebooks/Lirpa_SORT.ipynb', 'repo_name': 'airbus/decomon', 'size': '4038'}