Menu

Mesclar classificação em C ++ com exemplos

merge sort c with examples

Experimente Nosso Instrumento Para Eliminar Problemas

Técnica de classificação de mesclagem C ++.

O algoritmo de classificação de mesclagem usa o “ dividir e conquistar ”Estratégia em que dividimos o problema em subproblemas e resolvemos esses subproblemas individualmente.

Esses subproblemas são então combinados ou mesclados para formar uma solução unificada.

=> Leia a popular série de treinamento C ++ aqui.

Mesclar Classificar

O que você aprenderá:

conversor de youtube para mp4 para android

Visão geral

A classificação de mesclagem é realizada usando as seguintes etapas:

# 1) A lista a ser classificada é dividida em duas matrizes de igual comprimento, dividindo a lista no elemento do meio. Se o número de elementos na lista for 0 ou 1, a lista será considerada classificada.

#dois) Cada sublista é classificada individualmente usando a classificação por mesclagem recursivamente.

# 3) As sublistas classificadas são então combinadas ou mescladas para formar uma lista classificada completa.

Algoritmo Geral

O pseudo-código geral para a técnica de classificação por mesclagem é fornecido abaixo.

Declare uma matriz Arr de comprimento N
Se N = 1, Arr já está classificado
Se N> 1,
Esquerda = 0, direita = N-1
Encontre o meio = (esquerda + direita) / 2
Chame merge_sort (Arr, left, middle) => classificar primeiro semestre recursivamente
Chamar merge_sort (Arr, middle + 1, right) => classificar segunda metade recursivamente
Chame merge (Arr, left, middle, right) para mesclar matrizes classificadas nas etapas acima.
Saída

Conforme mostrado no pseudocódigo acima, no algoritmo de classificação por mesclagem dividimos o array pela metade e classificamos cada metade usando a classificação por mesclagem recursivamente. Depois que os subarrays são classificados individualmente, os dois subarrays são mesclados para formar um array classificado completo.

Pseudo código para mesclagem de classificação

A seguir está o pseudo código para a técnica de classificação por mesclagem. Primeiro, temos um procedimento merge sort para dividir o array em metades recursivamente. Em seguida, temos uma rotina de mesclagem que mesclará os arrays menores classificados para obter um array ordenado completo.

procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 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

Vamos agora ilustrar a técnica de classificação por mesclagem com um exemplo.

Ilustração

ilustração de classificação de fusão

A ilustração acima pode ser mostrada em uma forma tabular abaixo:

PassarLista não classificadadividirLista ordenada
1{12, 23,2,43,51,35,19,4}{12,23,2,43}
{51,35,19,4}		{}
dois{12,23,2,43}
{51,35,19,4}		{12,23} {2,43}
{51,35} {19,4}		{}
3{12,23} {2,43}
{51,35} {19,4}		{12,23} {2,43}
{35,51} {4,19}		{12,23} {2,43}
{35,51} {4,19}
4{12,23} {2,43}
{35,51} {4,19}		{2,12,23,43}
{4,19,35,51}		{2,12,23,43}
{4,19,35,51}
5{2,12,23,43}
{4,19,35,51}		{2,4,12,19,23,35,43,51}{2,4,12,19,23,35,43,51}
6{}{}{2,4,12,19,23,35,43,51}

Conforme mostrado na representação acima, primeiro a matriz é dividida em duas submatrizes de comprimento 4. Cada submatriz é ainda dividida em mais duas submatrizes de comprimento 2. Cada submatriz é então dividida em uma submatriz de um elemento cada. Todo esse processo é o processo de “divisão”.

Depois de dividir o array em submatrizes de elemento único cada, temos agora que mesclar esses arrays em ordem de classificação.

Conforme mostrado na ilustração acima, consideramos cada submatriz de um único elemento e primeiro combinamos os elementos para formar submatrizes de dois elementos em ordem classificada. Em seguida, as submatrizes classificadas de comprimento dois são classificadas e combinadas para formar duas submatrizes de comprimento quatro cada. Em seguida, combinamos esses dois subarrays para formar um array ordenado completo.

Classificação de fusão iterativa

O algoritmo ou técnica de merge sort que vimos acima usa recursão. Também é conhecido como “ classificação de mesclagem recursiva ”.

Sabemos que as funções recursivas usam a pilha de chamadas de função para armazenar o estado intermediário da função de chamada. Ele também armazena outras informações de contabilidade para parâmetros etc. e representa uma sobrecarga em termos de armazenamento de registro de ativação de chamada da função, bem como de retomada da execução.

Todos esses overheads podem ser eliminados se usarmos funções iterativas em vez de recursivas. O algoritmo de classificação por mesclagem acima também pode ser convertido facilmente em etapas iterativas usando loops e tomada de decisão.

Como a ordenação de mesclagem recursiva, a ordenação de mesclagem iterativa também tem complexidade O (nlogn), portanto, em termos de desempenho, eles têm um desempenho igual um ao outro. Simplesmente somos capazes de reduzir as despesas gerais.

Neste tutorial, nos concentramos na classificação por mesclagem recursiva e, a seguir, implementaremos a classificação por mesclagem recursiva usando as linguagens C ++ e Java.

A seguir, é fornecida uma implementação da técnica de classificação por mesclagem usando C ++.

#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array '; for (int i = 0; i < num; i++) { cout<

Resultado:

Insira o número de elementos a serem classificados: 10

Insira 10 elementos a serem classificados: 101 10 2 43 12 54 34 64 89 76

Matriz ordenada

2 10 12 34 43 54 64 76 89 101

Neste programa, definimos duas funções, merge_sort e vai . Na função merge_sort, dividimos o array em dois arrays iguais e chamamos a função merge em cada um desses sub arrays. Na função de mesclagem, fazemos a classificação real nesses subarrays e, em seguida, os fundimos em um array ordenado completo.

A seguir, implementamos a técnica Merge Sort na linguagem Java.

class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i

Resultado:

Matriz de entrada

101 10 2 43 12 54 34 64 89 76

Array classificado usando merge sort

2 10 12 34 43 54 64 76 89 101

Também na implementação Java, usamos a mesma lógica que usamos na implementação C ++.

A classificação por mesclagem é uma maneira eficiente de classificar listas e, principalmente, é usada para classificar listas vinculadas. Como ela usa uma abordagem de dividir e conquistar, a técnica de classificação por mesclagem tem um desempenho igualmente eficiente para matrizes menores e maiores.

Análise de complexidade do algoritmo de classificação de fusão

Sabemos que, para realizar a classificação usando a classificação por mesclagem, primeiro dividimos o array em duas metades iguais. Isso é representado por “log n” que é uma função logarítmica e o número de passos dados é log (n + 1) no máximo.

Em seguida, para encontrar o elemento do meio da matriz, exigimos uma única etapa, ou seja, O (1).

Então, para fundir as submatrizes em uma matriz de n elementos, levaremos O (n) quantidade de tempo de execução.

Portanto, o tempo total para realizar a classificação por mesclagem será n (log n + 1), o que nos dá a complexidade de tempo de O (n * logn).

Pior caso de complexidade de tempoO (n * log n)
Melhor caso de complexidade de tempoO (n * log n)
Complexidade de tempo médioO (n * log n)
Complexidade do espaçoSobre)

A complexidade de tempo para a classificação por mesclagem é a mesma em todos os três casos (pior, melhor e média), pois sempre divide a matriz em submatrizes e, em seguida, mescla as submatrizes levando um tempo linear.

A classificação por mesclagem sempre ocupa a mesma quantidade de espaço que os arrays não classificados. Portanto, quando a lista a ser classificada é um array, a classificação por mesclagem não deve ser usada para arrays muito grandes. No entanto, a classificação por mesclagem pode ser usada com mais eficácia para a classificação de listas vinculadas.

Conclusão

A classificação de mesclagem usa a estratégia “dividir e conquistar” que divide o array ou lista em vários subarrays e os classifica individualmente e, em seguida, mescla em um array ordenado completo.

A classificação por mesclagem tem um desempenho mais rápido do que outros métodos de classificação e também funciona com eficiência para arrays menores e maiores.

Exploraremos mais sobre a Classificação rápida em nosso próximo tutorial!

=> Cuidado com o Guia de treinamento para iniciantes em C ++ aqui.

Leitura recomendada

^