32. Gestió de la selecció¶

Amb aquest algorisme comencem a veure els algoritmes de la gestió de dades ** **. Aquest tipus d’algoritmes us permeten demanar una llista de dades de menys a més gran. Els ordinadors prenen el seu nom precisament d’aquesta funció important que poden realitzar, ordenar noms de noms o números per facilitar la creació de llistes o la cerca de dades posterior.

Algoritme de selecció¶

L’algoritme de gestió consisteix a buscar a tota la llista l’element més petit de tots. En principi, comencem amb el primer element de la llista com a nen. A continuació, un bucle compara un per un tots els elements de la llista amb el nen i selecciona en cada cas el més petit de tots

lista = [6, 3, 9, 5, 7, 1, 2, 4, 10, 8]
menor = 0
for i in range(len(lista)):
    if lista[i] < lista[menor]:
        menor = i

La variable menor valdrà 5, que és la posició de l’element inferior, 1.

Un cop hem trobat la posició de l’element més baix de tots, intercanviem aquest element amb el primer de la llista

temp = lista[0]
lista[0] = lista[menor]
lista[menor] = temp

Ara sabem que el primer element de la llista ja està ordenat que sigui el més mínim de tots els elements de la llista.

Per continuar repetim el procediment, però amb tots els elements de la llista des de la segona posició. Això ens permetrà tenir el segon element de la comanda.

Repetint el procediment una i altra vegada, estem ordenant tots els elements de la llista des del primer al penúltim. Un cop tots els elements, excepte un, l’últim element sabem que serà el més gran de tots i serà al final de la llista, de manera que no caldrà ordenar l’últim element.

Programa de planificació I¶

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

def busca_menor(lista, final):
    menor = final
    for i in range(final, len(lista)):
        if lista[i] < lista[menor]:
            menor = i
    return menor


def ordenar(lista):
    for final in range(len(lista) - 1):
        menor = busca_menor(lista, final)
        temp = lista[final]
        lista[final] = lista[menor]
        lista[menor] = temp


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]

Programa de planificació II¶

En aquesta segona versió del programa de gestió, l'algoritme es modificarà una mica. Després de trobar l’element més petit de la llista, passarem a la dreta tots els elements no ordenats per sota de l’element inferior, deixant un forat per col·locar -lo al seu lloc.

Aquest algorisme modificat té l’avantatge de mantenir amb el seu ordre original tots els elements de la llista que encara no s’han mogut al començament de la llista

def busca_menor(lista, comienzo):
    menor = comienzo
    for i in range(comienzo, len(lista)):
        if lista[i] < lista[menor]:
            menor = i
    return menor


def desplaza_derecha(lista, comienzo, final):
    temp = lista[final]
    for i in range(final, comienzo, -1):
        lista[i] = lista[i - 1]
    lista[comienzo] = temp


def ordenar(lista):
    for comienzo in range(len(lista) - 1):
        menor = busca_menor(lista, comienzo)
        desplaza_derecha(lista, comienzo, menor)


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¶

Reescriviu el programa de gestió I 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 Planificació II per començar a ordenar els elements de la dreta, començant per ordenar el més gran de tots els elements, que han de moure's al final de la llista.
Escriviu un programa basat en la selecció que mogui tots els zeros des d'una llista a l'esquerra. La resta d’elements de la llista han de mantenir l’ordre que tenia al principi
```
lista = [1, 0, 5, 3, 0, 0, 6, 2]
separar_ceros(lista)
print(lista)
```
Sortida
```
[0, 0, 0, 1, 5, 3, 6, 2]
```
El programa es basarà en el programa de planificació II. Heu de seleccionar el zeros un per un i moure els zeros a l'esquerra. Si en algun moment no troba un zero a la llista, el programa s’acabarà.
Escriviu un algorisme de gestió de selecció que ordeni 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 la més llarga
```
lista = ['manzana', 'uva', 'melocotón', 'sandía', 'melón']
```