Classificação rápida versus classificação de fusão comparada

“O objetivo deste artigo é dar as semelhanças e diferenças entre classificação rápida e classificação de mesclagem. O artigo “Classificação rápida em C” ou um título semelhante já foi escrito para Linuxhint.coma. O título pode ser digitado na caixa de pesquisa do Linuxhint.com a página inicial para chegar ao artigo. Outro artigo, "Merge Sort in C" ou um título semelhante, já foi escrito para Linuxhint.coma. O título pode ser digitado na caixa de pesquisa do Linuxhint.com a página inicial para chegar ao artigo. O leitor é aconselhado a se referir a esses dois artigos enquanto lê este.

Classificação rápida é um algoritmo de classificação. Merge Sort é outro algoritmo de classificação. O código para os dois artigos mencionados acima é escrito em C. O código para este artigo também é escrito em C. O leitor deve estar ciente disso. A ascensão de classificação é considerada para ambos os algoritmos de classificação neste artigo.”

Conteúdo do artigo

- Introdução - Veja acima
- Algoritmos para classificar e mesclar rapidamente
- Notação Big-O de O (n), O (n2) e O (N.log (n))
- Comparando classificação rápida e classificação
- Conclusão

Algoritmos para classificar e mesclar rapidamente
Algoritmo para Quicksort

1) Se houver apenas um ou nenhum elemento na lista, retorne. Um elemento significa que a lista já está classificada. Zero elemento significa que não há nada para classificar.
2) Com um palpite inteligente, escolha um elemento adequado na lista como um pivô.
3) Partição (divida) a lista em três sub-listas. Faça todos os elementos para a sub-lista esquerda menos que o pivô. A lista central tem apenas um elemento, que é o pivô. Faça todos os elementos na sub-lista direita maior que o pivô. Colocando elementos à esquerda que são menores que o pivô, e elementos à direita que são maiores que o pivô, sem pura classificação, que já é uma classificação (em um sentido amplo).
4) dividir recursivamente cada sub-lista (esquerda e direita) em três, como na etapa acima, com cada conjunto de três sub-listas tendo seu próprio novo pivô (de uma sub-lista de um elemento), até que toda a lista fornecida seja perfeitamente classificado.

Existem diferentes formulários de codificação para a etapa 2. Um formulário de codificação melhor levará a uma classificação completa mais rápida.
Existem diferentes formulários de codificação para a etapa 3. Um formulário de codificação melhor levará a uma classificação completa mais rápida.

Algoritmo para Mergesort

1) Se houver apenas um ou nenhum elemento na lista, retorne. Um elemento significa que a lista já está classificada. Zero elemento significa que não há nada para classificar.
2) Divida recursivamente a lista e suas sub-listas em duas metades até que cada sub-lista tenha apenas um elemento.
3) Classificar pares de sub-listas da esquerda para a direita recursivamente, incluindo pares maiores resultantes, até que toda a lista seja recuperada, mas completamente classificada.

Esta é a maneira normal de fazer o mesclado, e não dá espaço, para diferentes segmentos de código, para o mesmo objetivo que o Quicksort.

Notação Big-O de O (n), O (n2) e O (N.log (n))

Sobre)
Considere o seguinte código:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; isoma = soma + a [i];

printf ("%d \ n", soma);

n = 8. A saída, a soma é 36. No loop for, há uma operação que é executada 8 vezes. Na notação big-o, essa velocidade (complexidade do tempo) é escrita como,

Sobre)

Considere o seguinte código semelhante, onde apenas os números ímpares são adicionados:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; isoma = soma + a [i];

printf ("%d \ n", soma);

A saída, soma desta vez, é 16. No loop for, a única operação é executada 4 vezes, que é N/2 vezes. Na notação Big-O, essa velocidade (complexidade do tempo) ainda é escrita como O (n). O número máximo de operações possíveis é o que é considerado.

Sobre²)

Considere o seguinte código que adiciona a matriz de 8 por 8 números:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; ifor (int j = 0; jsoma = soma + a [j];


printf ("%d \ n", soma);

A saída, a soma, é 288. No loop for, há uma operação executada 8 x 8 vezes = 64 vezes. Na notação big-o, essa velocidade (complexidade do tempo) é escrita como,

O (n²)

Considere o seguinte código semelhante, onde apenas os números ímpares da matriz são adicionados:

int n = 8;
int sum = 0;
int a [] = 1, 2, 3, 4, 5, 6, 7, 8;
para (int i = 0; ifor (int j = 0; jsoma = soma + a [j];


printf ("%d \ n", soma);

A saída, soma desta vez, é 64. No loop for, a única operação é executada 4 x 4 vezes = 16 vezes, o que é n²/4 vezes. Isso é mais de 8 vezes (mais de n vezes), mas menos de 64 vezes (menos de n² tempos). Na notação Big-O, essa velocidade (complexidade do tempo) ainda pode ser escrita como O (n²). O número máximo de operações possíveis é o que é considerado.

Aqui, não confunda a soma, 64, e o número de operações, 16. Este caso de 16 operações, entre 8 (n) e 64 (n²), ainda pode ser escrito, como na seguinte subseção.

Sobre.log (n))

Considere a situação de uma matriz de 8 por 8, onde o número total de operações é 24. 24 pode ser visto como aproximadamente em torno do meio, entre 8 (n) e 64 (n²).

Agora,

24 = 8xlog₂(8)
=> 24 = 8xlog₂(2³)
=> 24 = 8 × 3

Agora compare,

24 = 8xlog₂(8)
com
24 = n.registro₂(n)

Para o máximo de n², Quando o número total de operações é entre n e n², E em torno do meio, na notação Big-O, essa velocidade (complexidade do tempo) é melhor escrita como n.registro₂(n) em vez de O (n²).

Comparando classificação rápida e classificação
Número de etapas no algoritmo

De cima, o Quicksort tem 4 etapas em seu algoritmo, enquanto o Mergesort tem 3 etapas em seu algoritmo.

Diferentes maneiras de codificar

O Slorping Quick tem maneiras diferentes de codificar, enquanto a Merge Sort tem apenas uma maneira principal de codificar.

Complexidade do tempo

A complexidade do tempo para Mergesort é n.registro₂(n). Sua velocidade é comparável à da função de classificação da biblioteca C ++ usada para fins comerciais.

Quando a função pivô mediana é usada para o Quicksort, a complexidade do tempo é aproximadamente 1.188n.registro₂(n), mais alto que a mesclagem, assumindo que uma boa função de partição seja usada. Muitos programas do Quicksort têm complexidade de maior tempo. A pior complexidade do tempo para o Quicksort é O (n²). No entanto, se o programa do QuickSort estiver bem codificado com segmentos de código muito bons, ele vencerá a Mergesort em velocidade.

Conclusão

O Quicksort normalmente corre mais devagar do que o mesclagem.