5.11. Mixing Order¶

Agora diriximos a nosa atención ao uso dunha estratexia de dividir e conquistar como unha forma de mellorar o rendemento dos algoritmos de ordenación. O primeiro algoritmo que estudamos está mesturando mesturando. A orde de mestura é un algoritmo recursivo que divide continuamente unha lista á metade. Se a lista está baleira ou ten un único elemento, é ordenado por definición (o caso base). Se a lista ten máis dun elemento, dividimos a lista e invisten recursivamente unha orde de mestura para ambas as metades. Unha vez que as dúas metades son ordenadas, realízase a operación fundamental, chamada Mestura. A mestura é o proceso de levar dúas listas ordenadas menores e combinalas nunha única lista nova e ordenada. A Figura 10 mostra a nosa lista de exemplos familiares xa que está dividida por ordenamientoPorMezcla. A Figura 11 mostra as listas sinxelas, agora ordenadas, xa que se unen de novo.

../_ imaxes / mergesorta.png

Figura 10: División da lista nunha orde de mestura

Figura 10: División da lista nunha orde de mestura

./_images/mergesortb .png 3figura 11: listas como fusionadas de novo

Figura 11: listas fusionadas de novo

a función ordenamientoPorMezcla Mostrado en Activecode 1 comeza pedindo o caso base. Se a lonxitude da lista é menor ou igual a unha, xa temos unha lista ordenada e non é necesario máis procesamento. Se, por outra banda, a lonxitude é maior que unha, entón usamos a operación slice de python para extraer as metades esquerda e dereita. É importante ter en conta que a lista pode non ter un número de elementos. Iso non importa, xa que as lonxitudes serán diferentes como máximo.

Unha vez que a función na metade esquerda e á metade dereita ( Liñas 8-9), suponse que son ordenados. O resto da función (liñas 11-31) é responsable de mesturar as dúas listas ordenadas máis pequenas nunha lista ordenada máis grande. Teña en conta que a operación de mestura localiza de novo os elementos na lista orixinal (unaLista) un a un tempo que leva repetidamente o menor elemento das listas ordenadas.

A función ordenamientoPorMezcla aumentou cunha instrución (liña 2) para mostrar o contido da lista que está sendo ordenado ao comezo de cada un Invocación. Tamén hai unha instrución print (liña 32) para mostrar o proceso de mestura. A impresión mostra o resultado da execución da función coa nosa lista de exemplo. Teña en conta que a lista con elementos 44, 55 e 20 non se dividirá en partes iguais. A primeira división dá e o segundo día. É fácil ver como o proceso de división produce ocasionalmente unha lista que se pode mesturar inmediatamente con outras listas ordenadas.

inicializerunstop empezando a avanzar cara atrás

para analizar a función

, debemos considerar os dous procesos diferentes que compoñen a súa implementación. En primeiro lugar, a lista está dividida en metades. Xa estamos calculados (nunha procura binaria) que podemos dividir unha lista á metade nun tempo \ (\ log n \) onde n é a lonxitude da lista. O segundo proceso é a mestura. Cada elemento da lista será procesado e colocado na lista ordenada. Polo tanto, a operación de mestura que resulta nunha lista de n require operacións n. O resultado desta análise é que se realizan as divisións \ (\ Log N), cada unha das cales custa \ (n \) un total de operacións \ (n \ log N). Unha orde de mestura é un algoritmo (ou (n \ log n) \).

Lembre que o operador de partición é \ (ou (k) \) onde K é o tamaño da partición. Para garantir que ordenamientoPorMezcla \ (ou (n \ log n) \) teremos que eliminar o operador de partición. Unha vez máis, isto é posible se simplemente pasamos os índices iniciais e finais xunto coa lista cando realizamos a chamada recursiva. Deixamos isto como un exercicio.

É importante notar que a función ordenamientoPorMezcla require espazo adicional para almacenar as dúas metades que se extraen con operacións de partición. Este espazo adicional pode ser un factor crítico se a lista é grande e pode facer problemática a esta orde cando se traballa en grandes conxuntos de datos.

autoavaliación

    Q-2: Dada a seguinte lista de números: cal das seguintes respostas corresponde á lista que se ordenará despois de 3 chamadas recursivas a moderación?

  • Esta é a segunda metade da lista.
  • Si, Order simezcla seguirá movéndose recursivamente cara ao inicio da lista ata que se deteña co caso base.
  • Lembre que a ordepormezcla non funciona á metade da metade A metade dereita está totalmente ordenada.
  • Esta é a lista despois de 4 chamadas recursivas
    Q-3: Dada a seguinte lista de números : Cal das seguintes respostas corresponde ás dúas primeiras anuncios que se mesturarán?

  • e
  • As dúas primeiras listas mixtas serán listas de base, aínda non alcanzamos un caso base.
  • e
  • Estes serán os últimos dúas listas mixtas
  • e
  • As listas e son os primeiros dous casos de base atopados ordenando a memoria e, polo tanto, serán as dúas primeiras listas mixtas.
  • e
  • Aínda que 9 e 16 son valores veciños, están en diferentes metades da lista da primeira partición.

Leave a Comment

O teu enderezo electrónico non se publicará Os campos obrigatorios están marcados con *