shell sort c with examples
Técnica de classificação de shell em C ++: uma visão geral completa.
A classificação de casca é freqüentemente denominada como um aprimoramento da classificação por inserção. Na classificação por inserção, pegamos incrementos de 1 para comparar os elementos e colocá-los em suas posições adequadas.
Na classificação shell, a lista é classificada dividindo-a em várias sublistas menores. Não é necessário que as listas precisem ser com elementos contíguos. Em vez disso, a técnica de classificação de shell usa incremento i, que também é chamado de “lacuna” e o usa para criar uma lista de elementos que são elementos “i” separados.
=> Veja aqui para explorar a lista completa de tutoriais C ++.
gerador de número aleatório 0-1
O que você aprenderá:
Algoritmo Geral
O algoritmo geral para classificação de shell é fornecido abaixo.
shell_sort (A, N)
onde A - lista a ser classificada; N - gap_size
definir gap_size = N, flag = 1
enquanto gap_size> 1 ou flag = 1, repita
começar
definir sinalizador = 0
definir gap_size = (gap_size + 1) / 2
fim
para i = 0 para i<(N-gap_size) repeat
começar
se A (i + gap_size)> A (i)
trocar A (i + gap_size), A (i)
definir sinalizador = 0
fim
fim
Assim, no algoritmo acima, primeiro definimos N, que é a lacuna para classificar a matriz A usando classificação por shell. Na próxima etapa, dividimos a matriz em submatrizes usando a lacuna. Então, na próxima etapa, classificamos cada uma das submatrizes para que, no final do loop, obtenhamos uma matriz classificada.
A seguir, vamos considerar um exemplo detalhado para entender melhor a classificação da casca usando uma representação pictórica.
Ilustração
Vamos ilustrar a classificação Shell com um exemplo.
Considere a seguinte matriz de 10 elementos.
Se fornecermos uma lacuna de 3, teremos as seguintes sublistas com cada elemento com 3 elementos separados. Em seguida, classificamos essas três sublistas.
As sublistas classificadas e a lista resultante que obtemos após combinar as três sublistas classificadas são mostradas abaixo.
A matriz acima que obtivemos após a fusão das submatrizes classificadas está quase classificada. Agora podemos realizar a ordenação por inserção nesta lista e ordenar todo o array. Esta etapa final é mostrada abaixo para sua referência.
Como visto acima, após realizar a classificação shell e mesclar as sublistas classificadas, exigimos apenas três movimentos para classificar a lista completamente. Assim, podemos ver que podemos reduzir significativamente o número de etapas necessárias para classificar o array.
A escolha de incremento para criar sublistas é um recurso exclusivo da classificação de shell.
Exemplo C ++
Vamos ver a implementação da classificação de shell em C ++ a seguir.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Resultado:
Matriz a ser classificada:
45 23 53 43 18 24 8 95 101
Array após classificação de shell:
8 18 23 24 43 45 53 95 101
Usamos a mesma lista que usamos na ilustração e podemos ver que começamos inicialmente criando duas sublistas e, em seguida, diminuindo ainda mais a lacuna. Depois que as sub-listas são criadas de acordo com a lacuna especificada, classificamos cada uma das sub-listas. Depois que todas as sub-listas são classificadas, obtemos a lista quase classificada. Agora, essa lista pode ser classificada usando a classificação de inserção básica, que exige poucos movimentos.
A seguir, vamos implementar a classificação de shell usando a linguagem Java.
Exemplo de Java
// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i Resultado:
Matriz a ser classificada:
45 23 53 43 18 24 8 95 101
Array após classificação de shell:
8 18 23 24 43 45 53 95 101
Implementamos a mesma lógica para classificação de shell em programas C ++ e Java. Assim, conforme explicado acima no programa Java, primeiro dividimos a matriz em submatrizes e, em seguida, os classificamos para obter uma matriz ordenada completa.
Conclusão
A classificação de shell é o algoritmo altamente eficiente que melhora a classificação por inserção.
Enquanto a ordenação por inserção funciona incrementando seus elementos em 1, a ordenação de shell usa o parâmetro “gap” para dividir o array em submatrizes cujos elementos estão separados por “gap”. Em seguida, podemos classificar a lista individual usando a classificação por inserção para obter o array classificado completo.
A classificação por shell tem um desempenho mais rápido do que a classificação por inserção e leva menos movimentos para classificar a matriz quando comparada à classificação por inserção. Nosso próximo tutorial irá explorar tudo sobre a técnica de classificação de heap para classificar estruturas de dados.
=> Visite aqui para aprender C ++ do zero.
Leitura recomendada
- Classificação de seleção em C ++ com exemplos
- Método MongoDB Sort () com exemplos
- Comando de classificação Unix com sintaxe, opções e exemplos
- Classificação por bolha em C ++ com exemplos
- Inserção de classificação em C ++ com exemplos
- Mesclar classificação em C ++ com exemplos
- Classificação de heap em C ++ com exemplos
- Classificação rápida em C ++ com exemplos