A classificação é um dos recursos mais usados na programação. E levará tempo para concluir a classificação se não usarmos o algoritmo correto.
Neste artigo, vamos discutir diferentes algoritmos de classificação.
Orientaremos você pelos diferentes algoritmos de classificação em cada etapa da implementação. A parte de implementação será em Python. Você pode convertê-lo facilmente em qualquer idioma depois de obter o algoritmo. Essa é a questão da sintaxe da linguagem.
Veremos diferentes algoritmos do pior ao melhor neste tutorial. Então, não se preocupe. Siga o artigo e implemente-os.
Vamos mergulhar nos algoritmos de ordenação.
últimas postagens
Ordenação por Inserção
A ordenação por inserção é um dos algoritmos de ordenação simples. É fácil de implementar. E vai custar mais tempo para classificar uma matriz. Não será usado na maioria dos casos para classificar arrays maiores.
O algoritmo de classificação por inserção mantém subpartes classificadas e não classificadas no array fornecido.
A subparte classificada contém apenas o primeiro elemento no início do processo de classificação. Pegaremos um elemento do array não classificado e os colocaremos na posição correta no subarray classificado.
Vamos ver as ilustrações visuais da ordenação por inserção passo a passo com um exemplo.
Vejamos os passos para implementar a ordenação por inserção.
- Inicialize a matriz com dados fictícios (inteiros).
- Iterar sobre a matriz fornecida a partir do segundo elemento.
- Pegue a posição atual e o elemento em duas variáveis.
- Escreva um loop que itere até que o primeiro elemento da matriz ou o elemento ocorra menor que o elemento atual.
- Atualize o elemento atual com o elemento anterior.
- Decremento da posição atual.
- Aqui, o loop deve atingir o início da matriz ou encontrar um elemento menor que o elemento atual. Substitua o elemento de posição atual pelo elemento atual.
A complexidade de tempo da ordenação por inserção é O(n^2), e a complexidade de espaço é O(1).
É isso; nós classificamos o array fornecido. Vamos executar o seguinte código. Espero que você tenha instalado o Python, caso contrário, verifique o guia de instalação. Como alternativa, você pode usar um compilador Python online.
def insertion_sort(arr, n): for i in range(1, n): ## current position and element current_position = i current_element = arr[i] ## iteratin until ### it reaches the first element or ### the current element is smaller than the previous element while current_position > 0 and current_element < arr[current_position - 1]: ## updating the current element with previous element arr[current_position] = arr[current_position - 1] ## moving to the previous position current_position -= 1 ## updating the current position element arr[current_position] = current_element if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] insertion_sort(arr, 9) ## printing the array print(str(arr))
Classificação de seleção
A classificação por seleção é semelhante à classificação por inserção, com uma pequena diferença. Esse algoritmo também divide a matriz em subpartes classificadas e não classificadas. E então, em cada iteração, pegaremos o elemento mínimo da subparte não classificada e o colocaremos na última posição da subparte classificada.
Vamos ilustrar o tipo de seleção para melhor entendimento.
Vamos ver os passos para implementar a ordenação por seleção.
- Inicialize a matriz com dados fictícios (inteiros).
- Iterar sobre a matriz fornecida.
- Manter o índice do elemento mínimo.
- Escreva um loop que itera do elemento atual até o último elemento.
- Verifique se o elemento atual é menor que o elemento mínimo ou não.
- Se o elemento atual for menor que o elemento mínimo, substitua o índice.
- Temos o índice mínimo de elementos conosco. Troque o elemento atual pelo elemento mínimo usando os índices.
A complexidade de tempo da ordenação de seleção é O(n^2), e a complexidade de espaço é O(1).
Tente implementar o algoritmo, pois ele é semelhante à ordenação por inserção. Você pode ver o código abaixo.
def selection_sort(arr, n): for i in range(n): ## to store the index of the minimum element min_element_index = i for j in range(i + 1, n): ## checking and replacing the minimum element index if arr[j] < arr[min_element_index]: min_element_index = j ## swaping the current element with minimum element arr[i], arr[min_element_index] = arr[min_element_index], arr[i] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] selection_sort(arr, 9) ## printing the array print(str(arr))
Tipo de bolha
Bubble sort é um algoritmo simples. Ele troca os elementos adjacentes em cada iteração repetidamente até que a matriz fornecida seja classificada.
Ele itera sobre a matriz e move o elemento atual para a próxima posição até que seja menor que o próximo elemento.
As ilustrações nos ajudam a entender visualmente a classificação por bolhas. Vamos vê-los.
Vamos ver os passos para implementar o bubble sort.
A complexidade de tempo do tipo de bolha é O(n^2), e a complexidade de espaço é O(1).
Você pode implementar facilmente o tipo de bolha agora. Vamos ver o código.
def bubble_sort(arr, n): for i in range(n): ## iterating from 0 to n-i-1 as last i elements are already sorted for j in range(n - i - 1): ## checking the next element if arr[j] > arr[j + 1]: ## swapping the adjucent elements arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) ## printing the array print(str(arr))
Mesclar Ordenar
Merge sort é um algoritmo recursivo para classificar o array fornecido. É mais eficiente do que os algoritmos discutidos anteriormente em termos de complexidade de tempo. Segue a abordagem de dividir e conquistar.
O algoritmo de classificação por mesclagem divide a matriz em duas metades e as classifica separadamente. Depois de classificar as duas metades do array, ele as mescla em um único array classificado.
Como é um algoritmo recursivo, ele divide o array até que o array se torne o mais simples (array com um elemento) para ordenar.
É hora da ilustração. Vamos ver isso.
Vamos ver os passos para implementar o merge sort.
- Inicialize a matriz com dados fictícios (inteiros).
- Escreva uma função chamada merge para mesclar subarrays em um único array classificado. Ele aceita a matriz de argumentos, os índices esquerdo, médio e direito.
- Obtenha os comprimentos dos sub-arrays esquerdo e direito usando os índices fornecidos.
- Copie os elementos da matriz nas respectivas matrizes esquerda e direita.
- Iterar sobre os dois sub-arrays.
- Compare os dois elementos dos sub-arrays.
- Substitua o elemento da matriz pelo elemento menor das duas submatrizes para classificação.
- Verifique se algum elemento permanece em ambos os sub-arrays.
- Adicione-os à matriz.
- Escreva uma função chamada merge_sort com array de parâmetros, índices esquerdo e direito.
- Se o índice esquerdo for maior ou igual ao índice direito, retorne.
- Encontre o ponto médio da matriz para dividir a matriz em duas metades.
- Chame recursivamente o merge_sort usando os índices esquerdo, direito e intermediário.
- Após as chamadas recursivas, mescle o array com a função merge.
A complexidade de tempo do merge sort é O(nlogn), e a complexidade de espaço é O(1).
Isso é tudo para a implementação do algoritmo de classificação por mesclagem. Verifique o código abaixo.
def merge(arr, left_index, mid_index, right_index): ## left and right arrays left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] ## getting the left and right array lengths left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index ## indexes for merging two arrays i = j = 0 ## index for array elements replacement k = left_index ## iterating over the two sub-arrays while i < left_array_length and j < right_array_length: ## comapring the elements from left and right arrays if left_array[i] < right_array[j]: arr[k] = left_array[i] i += 1 else: arr[k] = right_array[j] j += 1 k += 1 ## adding remaining elements from the left and right arrays while i < left_array_length: arr[k] = left_array[i] i += 1 k += 1 while j < right_array_length: j += 1 k += 1 def merge_sort(arr, left_index, right_index): ## base case for recursive function if left_index >= right_index: return ## finding the middle index mid_index = (left_index + right_index) // 2 ## recursive calls merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) ## merging the two sub-arrays merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) ## printing the array print(str(arr))
Conclusão
Existem muitos outros algoritmos de classificação, mas acima estão alguns dos mais usados. Espero que você tenha gostado de aprender a ordenação.
Em seguida, descubra os algoritmos de pesquisa.
Boa codificação 🙂 👨💻