Ambas as técnicas de ordenação, quick sort e merge sort são construídas no método de divisão e conquista, 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 por mesclagem para classificar um grande conjunto de elementos.
Gráfico de comparação
| Base para comparação | Ordenação rápida | Merge sort |
|---|---|---|
| Particionamento dos elementos na matriz | A divisão de uma lista de elementos não é necessariamente dividida em metade. | Array é sempre dividido em metade (n / 2). |
| Complexidade do pior caso | O (n2) | O (n log n) |
| Funciona bem em | Matriz menor | Opera bem em qualquer tipo de array. |
| Rapidez | Mais rápido que outros algoritmos de ordenaçã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
A classificação rápida é um algoritmo de ordenação amplamente utilizado, pois é rápido para os arrays curtos. O conjunto dos elementos é dividido em partes repetidamente até que não seja possível dividi-lo ainda mais. A classificação rápida também é conhecida como classificação de troca de partição . Ele usa um elemento-chave (conhecido como o pivô) para particionar os elementos. Uma partição contém os elementos que são 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 [1], A [2], A [3], …… .., A [n] de n números que precisam ser classificados. O algoritmo de classificação rápida composto pelas etapas a seguir.
- O primeiro elemento ou qualquer elemento aleatório selecionado como a chave, assume a chave = A (1).
- O ponteiro “baixo” é colocado no segundo e o ponteiro “para cima” é posicionado no último elemento do array, ou seja, baixo = 2 e acima = n;
- Consistentemente, incremente o ponteiro “baixo” em uma posição até (tecla [A [baixo]>).
- Constantemente, diminua o ponteiro "para cima" em uma posição até (A [up] <= key).
- Se up for maior que low interchange A [low] com A [up].
- Repita o passo 3, 4 e 5 até que a condição no passo 5 falhe (ou seja, até <= baixo) e depois troque A [para cima] com a tecla.
- Se os elementos restantes 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.
- O procedimento acima é repetidamente aplicado às sub-redes até que toda a matriz seja classificada.
Vantagens e desvantagens
Possui um bom comportamento de caso médio. A complexidade do tempo de execução da classificação rápida é boa, ou seja, é 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 não é adequado para grandes matrizes.
Definição do tipo de mesclagem
Merge sort é um algoritmo externo que também é baseado na estratégia de dividir e conquistar. Os elementos são divididos em sub-arrays (n / 2) repetidamente até restar apenas um elemento, o que diminui significativamente o tempo de classificação. Ele usa armazenamento adicional para armazenar o array auxiliar. Merge sort usa três arrays, onde dois são usados para armazenar cada metade, e o terceiro é usado para armazenar a lista classificada final. Cada matriz é então classificada recursivamente. Por fim, os subarrays são mesclados para torná-lo n tamanho do elemento do array. A lista sempre dividida em apenas metade (n / 2) diferente da classificação rápida.
Seja A a matriz do número n de elementos a serem classificados A [1], A [2], ………, A [n]. A classificação de mesclagem segue as etapas fornecidas.
- Dividir o array A em sub-array ordenado n / 2 por 2, o que significa que os elementos em (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) sub-matrizes devem estar em ordem de classificação.
- Combine cada par de pares para obter a lista de subarranjos ordenados de tamanho 4; os elementos nos subarrays também estão em ordem de classificação, (A [1], A [2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……., (A [n-3], A [n-2], A [n-1], A [n]).
- A etapa 2 é executada repetidamente até que haja apenas uma matriz ordenada de tamanho n.
Vantagens e desvantagens
O algoritmo de classificação de mesclagem executa 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 maior parte da memória.
Principais diferenças entre ordenação rápida e ordenação de intercalação
- Na classificação de mesclagem, a matriz deve ser dividida em apenas duas metades (ou seja, n / 2). Como contra, em espécie rápida, não há compulsão de dividir a lista em elementos iguais.
- A pior complexidade do tipo quick sort é O (n2), pois são necessárias muito mais comparações nas piores condições. Em contraste, a classificação por mesclagem tem o mesmo pior cenário e complexidade de caso média, ou seja, O (n log n).
- A classificação direta pode funcionar bem em qualquer tipo de conjunto de dados, seja ele grande ou pequeno. Pelo contrário, a classificação rápida não pode funcionar bem com grandes conjuntos de dados.
- A classificação rápida é mais rápida que a mesclagem em alguns casos, como para conjuntos de dados pequenos.
- A ordenação por mesclagem requer espaço adicional na memória para armazenar as matrizes auxiliares. Por outro lado, a classificação rápida não requer muito espaço para armazenamento extra.
- Merge sort é mais eficiente que quick sort.
- A classificação rápida é o método de classificação interno, no qual os dados a serem classificados são ajustados por vez na memória principal. Por outro lado, a ordenação por mesclagem é um método de classificação externo no qual os dados que devem ser classificados não podem ser acomodados na memória ao mesmo tempo e alguns devem ser mantidos na memória auxiliar.
Conclusão
A classificação rápida é mais rápida, mas é ineficiente em algumas situações e também executa muitas comparações em comparação com a 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).
