Es. 14. 15/05

Alice propone oggi 10 giugno questa soluzione:

def inserisciordinato(lista,e):
    if len(lista)==0:
        return [e]
    if len(lista)==1:
        if lista[0]>e:
            return [e]+lista
        else:
            return lista+[e]
    if len(lista)>1:
        p1=lista[0:len(lista)//2]
        p2=lista[len(lista)//2:len(lista)]
        if lista[len(lista)//2]>e:
            return inserisciordinato(p1,e)+p2
        else:
            return p1+inserisciordinato(p2,e)


listaInput=input("inserici la prima lista di numeri").split(',')

lista1=[]
for i in listaInput:
    lista1.append(int(i))
e=int(input("inserici un numero"))
lista=inserisciordinato(lista1,e)
print(lista)

E' molto interessante. E' in inserimento dicotomico. Se la lista ha zero elementi restituisce una lista composta solamente dall'elemento inserito. Se la lista ha un elemento la nuova lista avra' due elementi: quello nuovo e quello esistente posti in una delle due possibili sequenze a seconda del loro ordine relativo. In tutti gli altri casi si separa la lista in due parti uguali (o quasi). L'inserimento avverra' in una sola delle due a seconda del confronto con l'elemento centrale.

Copia Log(N) volte l'intero vettore, usa la dinamicita' delle liste in python, puo' essere efficiente per liste di grandi dimensione... sarebbe da valutare.

---

Antichi commenti: Ho tolto la proposta di Anna dalla pagina (e l'ho riportata qui) perche' non e' una soluzione all'esercizio proposto. Questa serie di direttive all'interprete (solo private del prompt >>>) non e' un programma o una funzione e non risolve un problema. Mostra solamente come, manualmente e nel caso specifico dell'esempio, si puo' inserire un elemento al punto giusto di una lista. Chi ha detto che vada inserito all'indice 4? La posizione doveva essere calcolata dalla funzione richiesta.

valori_ordinati= [1,3,4,5,15,22]
print valori_ordinati [4:4]
[]
valori_ordinati [4:4]=[10]
print valori_ordinati