Contente

• Gráfico de comparação
• Definição de Classificação Rápida
• Definição de Classificação de Mesclagem
• Conclusão

Os algoritmos de classificação rápida e ordenação por mesclagem são baseados no algoritmo de dividir e conquistar, que funciona de maneira bastante semelhante. A diferença anterior entre a classificação rápida e a mesclagem é que, na classificação rápida, o elemento dinâmico é usado para a classificação. Por outro lado, a classificação de mesclagem não usa o elemento dinâmico para executar a classificação.

Ambas as técnicas de classificação, classificação rápida e classificação de mesclagem são construídas no método de dividir e conquistar, no qual o conjunto de elementos é dividido e depois combinado após o rearranjo. A classificação rápida geralmente requer mais comparações do que a classificação de mesclagem para classificar um grande conjunto de elementos.

1. 1. Gráfico de comparação
   2. Definição
   3. Principais diferenças
   4. Conclusão

Gráfico de comparação

Base para comparação	Ordenação rápida	Mesclar classificação
Particionamento dos elementos na matriz	A divisão de uma lista de elementos não é necessariamente dividida pela metade.	A matriz é sempre dividida em metade (n / 2).
Pior complexidade	Em2)	O (n log n)
Funciona bem em	Matriz menor	Opera bem em qualquer tipo de matriz.
Rapidez	Mais rápido que outros algoritmos de classificação para pequenos conjuntos de dados.	Velocidade consistente em todos os tipos de conjuntos de dados.
Requisito adicional de espaço de armazenamento	Menos	Mais
Eficiência	Ineficiente para matrizes maiores.	Mais eficiente.
Método de classificação	interno	Externo

Definição de Classificação Rápida

Ordenação rápida é um algoritmo de classificação amplamente utilizado, pois é rápido para matrizes curtas. O conjunto dos elementos é dividido em partes repetidamente até que não seja possível dividi-lo ainda mais. A ordenação rápida também é conhecida como classificação de troca de partição. Ele usa um elemento-chave (conhecido como pivô) para particionar os elementos. Uma partição contém os elementos menores que o elemento chave. Outra partição contém os elementos que são maiores que o elemento chave. Os elementos são classificados recursivamente.

Suponha que A seja uma matriz A, A, A, ……, A de n número que deve ser classificado. O algoritmo de classificação rápida composto pelas etapas a seguir.

1. O primeiro elemento ou qualquer elemento aleatório selecionado como chave, assume a chave = A (1).
2. O ponteiro "baixo" é colocado no segundo e o ponteiro "para cima" é posicionado no último elemento da matriz, isto é, baixo = 2 e acima = n;
3. Consistentemente, aumente o ponteiro "baixo" em uma posição até (tecla A>).
4. Constantemente, diminua o ponteiro "para cima" em uma posição até (A <= tecla).
5. Se up for maior que o baixo intercâmbio A com A.
6. Repita as etapas 3,4 e 5 até que a condição na etapa 5 falhe (ou seja, <= baixo) e depois troque A com a tecla
7. Se os elementos à esquerda da chave forem menores que a chave e os elementos à direita da chave forem maiores que a chave, a matriz será particionada em duas sub-matrizes.
8. O procedimento acima é aplicado repetidamente às sub-matrizes até que toda a matriz seja classificada.

   

Vantagens e desvantagens

Possui um bom comportamento médio de caso. A complexidade do tempo de execução da classificação rápida é boa, pois é mais rápida do que algoritmos como classificação de bolha, classificação de inserção e classificação de seleção. No entanto, é complexo e muito recursivo, é por isso que não é adequado para grandes matrizes.

Definição de Classificação de Mesclagem

Mesclar classificação é um algoritmo externo que também se baseia na estratégia de dividir e conquistar. Os elementos são divididos em sub-matrizes (n / 2) repetidamente até restar apenas um elemento, o que diminui significativamente o tempo de classificação. Ele usa armazenamento adicional para armazenar a matriz auxiliar. A classificação de mesclagem usa três matrizes, nas quais duas são usadas para armazenar cada metade e a terceira é usada para armazenar a lista final de classificação. Cada matriz é então classificada recursivamente. Por fim, as sub-matrizes são mescladas para torná-lo o tamanho do elemento n da matriz. A lista sempre é dividida em apenas metade (n / 2) diferente da classificação rápida.

Seja A a matriz de n número de elementos a serem classificados A, A, ……… A. A classificação por mesclagem segue as etapas fornecidas.

1. Divida a matriz A em aproximadamente n / 2 sub-matriz classificada por 2, o que significa que os elementos nas sub-matrizes (A, A), (A, A), (A, A), (A, A) devem estar em ordem classificada.
2. Combine cada par de pares para obter a lista de subarranjos classificados de tamanho 4; os elementos nas sub-matrizes também estão em ordem classificada (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. A etapa 2 é executada repetidamente até que haja apenas uma matriz classificada de tamanho n.

   

Vantagens e desvantagens

O algoritmo de classificação de mesclagem é executado da mesma maneira exata e precisa, independentemente do número de elementos envolvidos na classificação. Funciona bem mesmo com o grande conjunto de dados. No entanto, consome grande parte da memória.

1. Na classificação de mesclagem, a matriz deve ser dividida em apenas duas metades (ou seja, n / 2). Ao contrário, de maneira rápida, não há compulsão de dividir a lista em elementos iguais.
2. A pior complexidade do tipo classificação rápida é O (n²), pois são necessárias muito mais comparações nas piores condições. Por outro lado, a classificação de mesclagem tem as mesmas complexidades de pior caso e média de casos, ou seja O (n log n).
3. A classificação por mesclagem pode operar bem em qualquer tipo de conjunto de dados, seja grande ou pequeno. Pelo contrário, a classificação rápida não pode funcionar bem com grandes conjuntos de dados.
4. A classificação rápida é mais rápida que a classificação de mesclagem em alguns casos, como em pequenos conjuntos de dados.
5. A classificação de mesclagem requer espaço de memória adicional para armazenar as matrizes auxiliares. Por outro lado, a classificação rápida não exige muito espaço para armazenamento extra.
6. A classificação de mesclagem é mais eficiente que a classificação rápida.
7. A classificação rápida é o método de classificação interna, onde os dados a serem classificados são ajustados por vez na memória principal. Por outro lado, a classificação de mesclagem é um método de classificação externa, no qual os dados a serem classificados não podem ser acomodados na memória ao mesmo tempo e alguns precisam ser mantidos na memória auxiliar.

Conclusão

A classificação rápida ocorre em casos mais rápidos, mas é ineficiente em algumas situações e também realiza muitas comparações em comparação à classificação de mesclagem. Embora a classificação de mesclagem exija menos comparação, ela precisa de um espaço de memória adicional de 0 (n) para armazenar a matriz extra, enquanto a classificação rápida precisa de espaço de O (log n).