35. Barrejant l’ordenació¶
L’algoritme de gestió de la barreja (tipus de combinació en anglès) és un algorisme recursiu basat en les divisions de la tècnica i guanyarà.
Va ser desenvolupat el 1945 per Jonh von Neumann i s’adapta molt bé a l’ordenació d’una gran quantitat de dades seqüencials per ser molt ràpida i treballar fàcilment amb dades a les quals només es pot accedir d’un a un.
Descripció de l'algoritme¶
L’algoritme de gestió de la barreja es basa en dividir recursivament la llista de dades a ordenar dos sublistes de la meitat de la mida de cadascun que l’original, per tal d’ordenar -les amb més facilitat.
Quan la llista sigui de 0 o 1, s’ordenarà.
Un cop ordenats els dos sublistes, s’aplica un algorisme que barreja els dos sublistes ordenats en un sol conjunt ordenat de doble mida.
D’aquesta manera, els sublistes de mida creixent es barregen fins que s’ordena tota la llista original.
Programa de planificació¶
A continuació, apareix el codi de gestió d'una llista segons l'algorisme de la barreja
def ordenar(lista, inicio=0, final=None):
if final == None:
final = len(lista) - 1
if inicio == final:
return
medio = (inicio + final + 1) // 2
ordenar(lista, inicio, medio - 1)
ordenar(lista, medio, final)
mezclar(lista, inicio, medio, final)
def mezclar(lista, inicio, medio, final):
while (inicio < medio and inicio < final and medio <= final):
if lista[medio] < lista[inicio]:
temp = lista[medio]
i = medio
while (i > inicio):
lista[i] = lista[i - 1]
i = i - 1
lista[inicio] = temp
medio = medio + 1
inicio = inicio + 1
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]