5.11. L’ordenament per mezcla¶

Ara dirigim la nostra atenció a utilitzar una estratègia de dividir i conquerir com una forma de millorar l’acompliment dels algoritmes d’ordenament. El primer algorisme que estudiarem és l’ordenament per barreja. L’ordenament per barreja és un algoritme recursiu que divideix contínuament una llista per la meitat. Si la llista és buida o té un sol ítem, s’ordena per definició (el cas base). Si la llista té més d’un ítem, dividim la llista i invoquem recursivament un ordenament per barreja per a les dues meitats. Una vegada que les dues meitats estan ordenades, es realitza l’operació fonamental, anomenada barreja. La barreja és el procés de prendre dues llistes ordenades més petites i combinar-les en una sola llista nova i ordenada. La Figura 10 mostra la nostra llista d’exemple familiar a mesura que està sent dividida per ordenamientoPorMezcla. La Figura 11 mostra les llistes simples, ara ordenades, a mesura que es fusionen de nou.

../_ images / mergesortA.png

Figura 10: Divisió de la llista en un ordenament per barreja

Figura 10: Divisió de la llista en un ordenament per barreja

. ./_images/mergesortB.png

Figura 11: Llistes a mesura que es fusionen de nou

Figura 11: Llistes a mesura que es fusionen de nou

La funció ordenamientoPorMezcla mostrada en el ActiveCode 1 comença preguntant pel cas base. Si la longitud de la llista és menor o igual a un, llavors ja tenim una llista ordenada i no cal més processament. Si, d’altra banda, la longitud és més gran que un, llavors fem servir l’operació slice de Python per extreure les meitats esquerra i dreta. És important tenir en compte que la llista podria no tenir un nombre parell d’ítems. Això no importa, ja que les longituds seran diferents a molt en un.

Una vegada que s’invoca la funció ordenamientoPorMezcla a la meitat esquerra i la meitat dreta (línies 8-9), s’assumeix que estan ordenades. La resta de la funció (línies 11-31) és responsable de barrejar les dues llistes ordenades més petites en una llista ordenada més gran. Observi que l’operació de barreja situa els ítems de nou a la llista original (unaLista) un alhora prenent repetidament l’ítem menor de les llistes ordenades.

la funció ordenamientoPorMezcla s’ha augmentat amb una instrucció print (línia 2) per mostrar el contingut de la llista que s’està ordenant a l’inici de cada invocació. També hi ha una instrucció print (línia 32) per mostrar el procés de mescla. La impressió mostra el resultat de l’execució de la funció amb la nostra llista d’exemple. Noti que la llista amb els ítems 44, 55 i 20 no es dividirà en parts iguals. La primera divisió dóna i la segona dóna. És fàcil veure com el procés de divisió eventualment produeix una llista que es pot barrejar immediatament amb altres llistes ordenades.

a InitializeRunStop BeginningStep ForwardStep BackwardEnd

Per a analitzar la funció ordenamientoPorMezcla, hem de considerar els dos processos diferents que conformen la seva implementació. En primer lloc, la llista es divideix en meitats. Ja calculem (en una recerca binària) que podem dividir una llista per la meitat en un temps \ (\ log n \) on n és la longitud de la llista. El segon procés és la barreja. Cada ítem de la llista es processarà i es col·locarà a la llista ordenada. Així que l’operació de barreja que dóna lloc a una llista de grandària n requereix n operacions. El resultat d’aquesta anàlisi és que es fan \ (\ log n \) divisions, cadascuna de les quals costa \ (n \) per a un total de \ (n \ log n \) operacions. Un ordenament per barreja és un algoritme \ (O (n \ log n) \).

Recordeu que l’operador de partició és \ (O (k) \) on k és la mida de la partició. Per garantir que ordenamientoPorMezcla sigui \ (O (n \ log n) \) haurem de treure l’operador de partició. Un cop més, això és possible si simplement vam passar els índexs inicial i final juntament amb la llista quan fem la crida recursiva. Deixem això com a exercici.

És important notar que la funció ordenamientoPorMezcla requereix espai addicional per emmagatzemar les dues meitats a mesura que s’extreuen amb les operacions de partició. Aquest espai addicional pot ser un factor crític si la llista és gran i pot tornar problemàtic a aquest ordenament quan es treballa sobre grans conjunts de dades.

Autoavaluació

    Q-2: Donada la següent llista de nombres: Quina de les següents respostes correspon a la llista que serà ordenada després de 3 crides recursives a ordenamientoPorMezcla?

  • Aquesta és la segona meitat de la llista.
  • Sí, ordenamientoPorMezcla continuarà movent-se recursivament cap a l’inici de la llista fins que es límit amb el cas base.
  • Recordeu que ordenamientoPorMezcla no opera sobre la meitat dreta de la llista sinó fins que la meitat dreta estigui completament ordenada.
  • Aquesta és la llista després de 4 trucades recursives
    Q-3: Donada la següent llista de números: Quina de les següents respostes correspon a les primeres dues llistades que seran barrejades?

  • i
  • Les primeres dues llistes barrejades seran llistes de cas base, encara no hem arribat a un cas base.
  • i
  • Aquestes seran les dues últimes llistes barrejades
  • i
  • les llistes i són els dos primers casos base trobats per ordenamientoPorMezcla i, per tant, seran les dues primeres llistes barrejades.
  • i
  • Encara 9 i 16 són valors veïns, estan en meitats diferents de la llista des de la primera partició.

Leave a Comment

L'adreça electrònica no es publicarà. Els camps necessaris estan marcats amb *