Estruturas de dados - algoritmo de mesclagem de classificação

A classificação por mesclagem é uma técnica de classificação baseada na técnica de divisão e conquista. Com o pior caso de complexidade de tempo sendo Ο (n log n), é um dos algoritmos mais respeitados.

A classificação por mesclagem primeiro divide a matriz em metades iguais e, a seguir, as combina de maneira classificada.

Como funciona a mesclagem de classificação?

Para entender a classificação por mesclagem, consideramos uma matriz não classificada da seguinte forma -

Sabemos que a classificação por mesclagem primeiro divide todo o array iterativamente em metades iguais, a menos que os valores atômicos sejam alcançados. Vemos aqui que um array de 8 itens é dividido em dois arrays de tamanho 4.

Isso não altera a seqüência de aparência dos itens no original. Agora dividimos essas duas matrizes em metades.

Nós dividimos ainda mais essas matrizes e alcançamos o valor atômico que não pode mais ser dividido.

Agora, nós os combinamos exatamente da mesma maneira como foram divididos. Observe os códigos de cores dados a essas listas.

Primeiro comparamos o elemento de cada lista e, em seguida, os combinamos em outra lista de maneira classificada. Vemos que 14 e 33 estão em posições ordenadas. Comparamos 27 e 10 e na lista de destino de 2 valores colocamos 10 primeiro, seguido por 27. Alteramos a ordem de 19 e 35, enquanto 42 e 44 são colocados sequencialmente.

Na próxima iteração da fase de combinação, comparamos listas de dois valores de dados e os fundimos em uma lista de valores de dados encontrados, colocando todos em uma ordem de classificação.

Após a fusão final, a lista deve ser semelhante a esta -

Agora devemos aprender alguns aspectos de programação da classificação por mesclagem.

Algoritmo

A classificação por mesclagem continua dividindo a lista em metades iguais até que não possa mais ser dividida. Por definição, se for apenas um elemento da lista, ele é classificado. Em seguida, a classificação por mesclagem combina as listas classificadas menores mantendo a nova lista também classificada.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudo-código

Veremos agora os pseudocódigos para funções de classificação por mesclagem. Como nossos algoritmos apontam duas funções principais - dividir e mesclar.

Merge sort funciona com recursão e veremos nossa implementação da mesma maneira.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Para saber sobre a implementação de merge sort na linguagem de programação C, clique aqui .