Big O Exercice: Comment créer un algorithme efficace pour trier une liste en python ?

Big O Exercice

Exercice

Considérons la liste triée suivante avec des valeurs négatives et positives

l = [-4, -1, 0, 2, 5, 10]

Objectif : créer un algorithme efficace pour mettre les éléments au carré et trier la liste:

[0, 1, 4, 16, 25, 100]

Solution

Ma solution, peut-être pas la solution optimale mais la meilleure que j'ai trouvée jusqu'à présent :

l = [-4, -1, 0, 2, 5, 10]

min_value = 9999

l_new = []
for idx,i in enumerate(l):
    new_i = i**2
    if new_i < min_value: 
        min_value = new_i
        min_value_idx = idx
    l_new.append(new_i)
    #print(new_i,min_value,min_value_idx)

l_pop = []
for idx in range(min_value_idx):    
    l_pop.append(l_new.pop(0))

for value in l_pop:
    jdx = len(l_new) - 1
    cond = True
    while cond:
        jdx -= 1
        if value > l_new[jdx]:
            l_new.insert(jdx+1, value)
            cond = False

print('l_new',l_new)

donne

[0, 1, 4, 16, 25, 100]

Créer une fonction

def sort_list(l):

    nb_count = 0

    min_value = 9999

    l_new = []
    for idx,i in enumerate(l):
        new_i = i**2
        if new_i < min_value: 
            min_value = new_i
            min_value_idx = idx
        l_new.append(new_i)
        nb_count += 1
        #print(new_i,min_value,min_value_idx)

    l_pop = []
    for idx in range(min_value_idx):    
        l_pop.append(l_new.pop(0))
        nb_count += 1

    for value in l_pop:
        jdx = len(l_new) - 1
        cond = True
        while cond:
            jdx -= 1
            if value > l_new[jdx]:
                l_new.insert(jdx+1, value)
                cond = False
                nb_count += 1
            if jdx<0: cond = False

    return l_new, nb_count

l = [-4, -1, 0, 2, 5, 10]

l_new, nb_count = sort_list(l)

print(l_new)
print(nb_count)

donne

[0, 1, 4, 16, 25, 100]
10

Comparaison avec les fonctions "built-in" de python

l = [-4, -1, 0, 2, 5, 10]

l = [i**2 for i in l]
l.sort()

print(l)

donne

[0, 1, 4, 16, 25, 100]

Créer une visualisation

import matplotlib.pyplot as plt
import random
import math

n_list = []
nlogn_list = []
count_list = []
for n in range(10,1000):

    l = [random.randint(-100,100) for i in range(n)]
    l.sort()

    #print(l)

    l_new, nb_count = sort_list(l)

    n_list.append(n)
    nlogn_list.append(n*math.log(n))
    count_list.append(nb_count)

plt.xlabel('N List Size')
plt.ylabel('Iterations')

plt.scatter(n_list,count_list)
plt.scatter(n_list,nlogn_list)

Références

• Generate random integers between 0 and 9
• Sorting Algorithms in Python
• What is the complexity of the sorted() function?
• Complexity of Python Sort Method
• Python List insert()
• Python : How to remove element from a list by value or Index | remove() vs pop() vs del