introduction sorting techniques c
Lista das várias técnicas de classificação em C ++.
A classificação é uma técnica implementada para organizar os dados em uma ordem específica. A classificação é necessária para garantir que os dados que usamos estejam em uma ordem específica para que possamos facilmente recuperar a parte necessária de informações da pilha de dados.
Se os dados estiverem desorganizados e não classificados, quando quisermos uma determinada informação, teremos que pesquisá-la um a um todas as vezes para recuperar os dados.
=> Leia a série de treinamento Easy C ++.
Assim, é sempre aconselhável manter nossos dados organizados em uma ordem específica para que a recuperação da informação, bem como outras operações realizadas nos dados, possam ser feitas de forma fácil e eficiente.
Armazenamos dados na forma de registros. Cada registro é composto por um ou mais campos. Quando cada registro possui um valor único de um determinado campo, o chamamos de campo-chave. Por exemplo, em uma classe, Roll No pode ser um campo único ou chave.
onde está localizada a chave de segurança da rede
Podemos classificar os dados em um campo-chave específico e, em seguida, organizá-los em ordem crescente / crescente ou decrescente / decrescente.
Da mesma forma, em um dicionário telefônico, todo registro consiste no nome de uma pessoa, endereço e número de telefone. Nesse caso, o número de telefone é um campo único ou chave. Podemos classificar os dados do dicionário neste campo de telefone. Como alternativa, também podemos classificar os dados numericamente ou alfanumericamente.
Quando podemos ajustar os dados a serem classificados na própria memória principal sem qualquer necessidade de outra memória auxiliar, então chamamos isso de Classificação Interna .
Por outro lado, quando precisamos de memória auxiliar para armazenar dados intermediários durante a classificação, chamamos a técnica de Classificação Externa .
Neste tutorial, aprenderemos as várias técnicas de classificação em C ++ em detalhes.
O que você aprenderá:
Técnicas de classificação em C ++
C ++ oferece suporte a várias técnicas de classificação, conforme listado abaixo.
Tipo de bolha
A classificação por bolha é a técnica mais simples na qual comparamos cada elemento com seu elemento adjacente e trocamos os elementos se eles não estiverem em ordem. Dessa forma, no final de cada iteração (chamada de passagem), o elemento mais pesado é borbulhado no final da lista.
A seguir está um exemplo de classificação por bolha.
Matriz a ser classificada:
Como visto acima, uma vez que é uma pequena matriz e foi quase classificada, conseguimos uma matriz completamente classificada em algumas passagens.
Vamos implementar a técnica de Bubble Sort em C ++.
#include using namespace std; int main () { int i, j,temp; int a[5] = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < Resultado:
Lista de entrada ...
10 2 0 43 12
Lista de elementos classificados ...
0 2 10 12 43
Como pode ser visto na saída, na técnica de classificação por bolha, a cada passagem, o elemento mais pesado é borbulhado até o final da matriz, classificando assim a matriz completamente.
Ordem de Seleção
É uma técnica simples, mas fácil de implementar, na qual encontramos o menor elemento da lista e o colocamos em seu devido lugar. Em cada passagem, o próximo menor elemento é selecionado e colocado em sua posição adequada.
Vamos pegar a mesma matriz do exemplo anterior e executar a Classificação por seleção para classificar essa matriz.
Conforme mostrado na ilustração acima, para N número de elementos, usamos N-1 passagens para classificar completamente a matriz. No final de cada passagem, o menor elemento da matriz é colocado em sua posição adequada na matriz classificada.
A seguir, vamos implementar a Classificação de Seleção usando C ++.
#include using namespace std; int findSmallest (int[],int); int main () { int myarray[5] = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< Resultado:
Lista de entrada de elementos a serem classificados
12 45 8 15 33
A lista ordenada de elementos é
8 12 15 33 45
Na classificação por seleção, a cada passagem, o menor elemento do array é colocado em sua posição adequada. Portanto, no final do processo de classificação, obtemos um array completamente classificado.
Ordem de inserção
A classificação por inserção é uma técnica na qual partimos do segundo elemento da lista. Comparamos o segundo elemento com o anterior (1st) elemento e coloque-o em seu devido lugar. Na próxima passagem, para cada elemento, nós o comparamos com todos os seus elementos anteriores e inserimos esse elemento em seu devido lugar.
As três técnicas de classificação acima são simples e fáceis de implementar. Essas técnicas funcionam bem quando o tamanho da lista é menor. Conforme a lista aumenta de tamanho, essas técnicas não funcionam tão eficientemente.
A técnica ficará clara com a compreensão da ilustração a seguir.
A matriz a ser classificada é a seguinte:
Agora, para cada passagem, comparamos o elemento atual com todos os seus elementos anteriores. Assim, na primeira passagem, começamos com o segundo elemento.
Portanto, exigimos N número de passagens para classificar completamente uma matriz contendo N número de elementos.
Vamos implementar a técnica de classificação por inserção usando C ++.
#include using namespace std; int main () { int myarray[5] = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < Resultado:
Lista de entrada é
12 4 3 1 15
A lista ordenada é
1 3 4 12 15
A saída acima mostra a matriz classificada completa usando a classificação por inserção.
Ordenação rápida
Quicksort é o algoritmo mais eficiente que pode ser usado para classificar os dados. Esta técnica usa a estratégia de “dividir para conquistar”, na qual o problema é dividido em vários subproblemas e depois de resolvidos esses subproblemas individualmente são mesclados para uma lista ordenada completa.
No quicksort, primeiro dividimos a lista em torno do elemento pivô e, em seguida, colocamos os outros elementos em suas posições adequadas de acordo com o elemento pivô.
Conforme mostrado na ilustração acima, na técnica Quicksort dividimos a matriz em torno de um elemento pivô de forma que todos os elementos menores que o pivô estejam à sua esquerda, e aqueles maiores que o pivô estão à sua direita. Então pegamos esses dois arrays independentemente e os classificamos e então os unimos ou conquistamos para obter um array ordenado resultante.
A chave para Quicksort é a seleção do elemento pivô. Ele pode ser o primeiro, o último ou o elemento do meio da matriz. O primeiro passo depois de selecionar o elemento pivô é colocar o pivô em sua posição correta para que possamos dividir o array apropriadamente.
Vamos implementar a técnica Quick Sort usando C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr[], int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr[j] <= pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } //quicksort algorithm void quickSort(int arr[], int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr[], int size) { int i; for (i=0; i < size; i++) cout< Resultado:
Matriz de entrada
12 23 3 43 51
Array classificado com Quicksort
3 12 23 43 51
Na implementação do quicksort acima, temos uma rotina de partição que é usada para particionar o array de entrada em torno de um elemento pivô que é o último elemento do array. Em seguida, chamamos a rotina quicksort recursivamente para classificar individualmente as submatrizes, conforme mostrado na ilustração.
Mesclar Classificar
Esta é outra técnica que usa a estratégia “Dividir para conquistar”. Nesta técnica, dividimos a lista primeiro em metades iguais. Em seguida, executamos a técnica de classificação por mesclagem nessas listas de forma independente para que ambas as listas sejam classificadas. Por fim, mesclamos ambas as listas para obter uma lista ordenada completa.
A classificação por mesclagem e a classificação rápida são mais rápidas do que a maioria das outras técnicas de classificação. Seu desempenho permanece intacto mesmo quando a lista aumenta de tamanho.
Vamos ver uma ilustração da técnica Merge Sort.
Na ilustração acima, vemos que a técnica de classificação por mesclagem divide a matriz original em submatrizes repetidamente até que haja apenas um elemento em cada submatriz. Uma vez feito isso, os subarranjos são então classificados independentemente e mesclados para formar um array ordenado completo.
A seguir, vamos implementar Merge Sort usando a linguagem 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:
Digite o número de elementos a serem classificados: 5
Insira 5 elementos a serem classificados: 10 21 47 3 59
Matriz ordenada
3 10 21 47 59
Classificação Shell
A classificação shell é uma extensão da técnica de classificação por inserção. Na classificação por inserção, lidamos apenas com o próximo elemento, ao passo que, na classificação por shell, fornecemos um incremento ou uma lacuna com a qual criamos listas menores a partir da lista pai. Os elementos nas sublistas não precisam ser contíguos, em vez disso, eles geralmente estão separados por ‘gap_value’.
A classificação por Shell tem um desempenho mais rápido do que a classificação por Inserção e requer menos movimentos do que a classificação por Inserção.
Se fornecermos uma lacuna de, teremos as seguintes sublistas com cada elemento que está separado por 3 elementos.
Em seguida, classificamos essas três sublistas.
A matriz acima, obtida após a fusão das submatrizes classificadas, está quase classificada. Agora podemos realizar a ordenação por inserção neste array para ordenar todo o array.
Assim, vemos que, uma vez que dividimos o array em sublistas usando o incremento apropriado e depois os fundimos, obtemos a lista quase classificada. A técnica de classificação por inserção nesta lista pode ser executada e a matriz é classificada em menos movimentos do que a classificação por inserção original.
A seguir está a implementação do Shell Sort em C ++.
#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}; //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
Array após classificação de shell:
18 23 43 45 53
A classificação Shell, portanto, atua como uma grande melhoria em relação à classificação por inserção e nem mesmo leva a metade do número de etapas para classificar a matriz.
Classificação de pilha
Heapsort é uma técnica na qual a estrutura de dados de heap (min-heap ou max-heap) é usada para classificar a lista. Primeiro, construímos um heap a partir da lista não classificada e também usamos o heap para classificar a matriz.
Heapsort é eficiente, mas não tão rápido quanto o tipo Merge.
Conforme mostrado na ilustração acima, primeiro construímos um heap máximo a partir dos elementos da matriz a serem classificados. Em seguida, atravessamos o heap e trocamos o último e o primeiro elemento. Neste momento, o último elemento já está classificado. Em seguida, construímos novamente um heap máximo com os elementos restantes.
Percorra novamente o heap e troque o primeiro e o último elemento e adicione o último elemento à lista classificada. Este processo continua até que haja apenas um elemento restante na pilha que se torna o primeiro elemento da lista classificada.
Vamos agora implementar o Heap Sort usando C ++.
#include using namespace std; // function to heapify the tree void heapify(int arr[], int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr[largest]) largest = l; // If right child is larger than largest so far if (r arr[largest]) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr[root], arr[largest]); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr[], int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr[0], arr[i]); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr[], int n) { for (int i=0; i Resultado:
Matriz de entrada
4 17 3 12 9
Matriz ordenada
3 4 9 12 17
Até agora, discutimos brevemente todas as principais técnicas de classificação com uma ilustração. Aprenderemos cada uma dessas técnicas em detalhes em nossos tutoriais subsequentes, juntamente com vários exemplos para compreender cada técnica.
Conclusão
A classificação é necessária para manter os dados classificados e na ordem adequada. Não classificado e descuidado pode levar mais tempo para acessar e, portanto, pode afetar o desempenho de todo o programa. Portanto, para quaisquer operações relacionadas a dados, como acesso, pesquisa, manipulação, etc., precisamos que os dados sejam classificados.
Existem muitas técnicas de classificação empregadas na programação. Cada técnica pode ser empregada dependendo da estrutura de dados que estamos usando ou do tempo gasto pelo algoritmo para classificar os dados ou do espaço de memória usado pelo algoritmo para classificar os dados. A técnica que estamos usando também depende de qual estrutura de dados estamos classificando.
As técnicas de classificação nos permitem classificar nossas estruturas de dados em uma ordem específica e organizar os elementos em ordem crescente ou decrescente. Vimos as técnicas de classificação como classificação por bolha, classificação por seleção, classificação por inserção, classificação rápida, classificação por Shell, classificação por mesclagem e classificação por pilha. A classificação por bolha e a classificação por seleção são mais simples e fáceis de implementar.
Em nossos tutoriais subsequentes, veremos cada uma das técnicas de classificação mencionadas acima em detalhes.
=> Clique aqui para obter o curso C ++ grátis.
Leitura recomendada
- Classificação de heap em C ++ com exemplos
- Mesclar classificação em C ++ com exemplos
- Classificação de inserção em C ++ com exemplos
- Vídeo 1 do JMeter: introdução, download do JMeter e instalação
- Introdução à linguagem de programação Java - tutorial em vídeo
- Introdução ao Python e processo de instalação
- Comando de classificação Unix com sintaxe, opções e exemplos
- Método MongoDB Sort () com exemplos