33. Gestió d'inserció¶

Aquest algorisme de gestió té l’avantatge que permet a la llista modificar mentre s’està produint l’ordenació. La part de la llista no ordenada pot créixer afegint elements i la part de la llista que ja està ordenada pot disminuir eliminant elements. Això el converteix en un algorisme flexible.

Aquest algorisme s’utilitza normalment quan el nombre d’elements que s’han d’ordenar és petit (menys de 100 elements). Per a conjunts de dades més grans, hi ha algoritmes més ràpids i eficients, com ara la barreja, per Mound o Fast Management.

Explicació de l'algoritme¶

Al principi, suposarem que el primer element de la llista ja està ordenat, mentre que tots els altres són desordenats.

A continuació, agafarem el segon element de la llista. Si aquest element és inferior al primer element de la llista, canviarem les vostres posicions. En aquest moment ja tenim dos elements de la llista ordenats.

Continuarem amb el tercer element de la llista. Com més baix intercanviarem amb el segon i amb el primer element de la llista, fins que s’ordeni.

L’algoritme continua ordenant la resta d’elements un per un fins que situi l’últim element de la llista al seu lloc, moment en què s’acaba l’ordenació de la llista.

Programa de planificació¶

El programa complet de gestió de programes segons l'algoritme d'inserció serà el següent

def inserta_elemento(lista, index):
    for i in range(index, 0, -1):
        if lista[i - 1] > lista[i]:
            temp = lista[i - 1]
            lista[i - 1] = lista[i]
            lista[i] = temp
        else:
            break

def ordenar(lista):
    for index in range(1, len(lista)):
        inserta_elemento(lista, index)


lista = [6, 3, 9, 5, 7, 1, 2, 4, 10, 8]
ordenar(lista)
print(lista)

Sortida

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Inserció binària¶

L’algoritme d’inserció permet una millora que consisteix a cercar el lloc d’inserció correcte per cerca binària, que ja s’ha estudiat en una unitat anterior.

L’algoritme d’inserció binari millorat és el següent

def inserta_elemento(lista, index):
    # Busqueda binaria
    primero = 0
    ultimo = index - 1
    while primero <= ultimo:
        medio = (primero + ultimo) // 2
        if lista[index] <= lista[medio]:
            ultimo = medio - 1
        else:
            primero = medio + 1

    # Desplaza elemento a su lugar
    temp = lista[index]
    for i in range(index, primero, -1):
        lista[i] = lista[i - 1]
    lista[primero] = temp


def ordenar(lista):
    for index in range(1, len(lista)):
        inserta_elemento(lista, index)


lista = [6, 3, 9, 5, 7, 1, 2, 4, 10, 8]
ordenar(lista)
print(lista)

Sortida

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Exercicis¶

Escriviu una funció que ordeni una llista de tres elements per l'algoritme d'inserció, sense utilitzar bucles de cap tipus, només amb frases `` si ''.

Truqueu a la funció amb el codi següent per verificar que el `` ordre () `` funciona correctament

listas = [
    [1, 2, 3], [1, 3, 2],
    [2, 1, 3], [2, 3, 1],
    [3, 1, 2], [3, 2, 1]
    ]
error = False
for lista in listas:
    ordenar(lista)
    if lista != [1, 2, 3]:
        error = True
if error:
    print('Error')
else:
    print('Correcto')

Reescriviu el programa de gestió per ordenar els elements en sentit contrari, de més alt a més baix. Heu de canviar els noms de les funcions i variables per adaptar -se a la nova funció que estan fent.
Reescriviu el programa de gestió per dur a terme la comanda de la llista en una sola funció, sense separar el codi en dues funcions diferents. No oblideu canviar el nom de les variables de la `` inserir_emento`` `` de manera que no siguin les mateixes.
Escriviu un algorisme de gestió d’inserció que ordena les cadenes de text per longitud de la cadena, de manera que al principi es col·loquen les paraules més curtes i al final el més llarg
```
lista = ['manzana', 'uva', 'melocotón', 'sandía', 'melón']
```