TechCodeview

Neste tutorial, implementaremos o algoritmo de classificação por seleção em Python. É um algoritmo bastante simples que usa menos trocas.

Neste algoritmo, selecionamos o menor elemento de um array não classificado em cada passagem e trocamos com o início do array não classificado. Este processo continuará até que todos os elementos sejam colocados no lugar certo. É simples e um algoritmo de classificação de comparação local.

3º trimestre

Trabalho de classificação de seleção

A seguir estão as etapas para explicar o funcionamento da classificação por seleção em Python.

Vamos pegar um array não classificado para aplicar o algoritmo de classificação por seleção.

[30, 10, 12, 8, 15, 1]

Passo 1: Obtenha o comprimento da matriz.

comprimento = len(matriz) → 6

Passo 2: Primeiro, definimos o primeiro elemento como elemento mínimo.

Etapa 3: Agora compare o mínimo com o segundo elemento. Se o segundo elemento for menor que o primeiro, atribuímos-lhe o mínimo.

Novamente comparamos o segundo elemento com o terceiro e se o terceiro elemento for menor que o segundo, atribuímos-o como mínimo. Este processo continua até encontrarmos o último elemento.

Passo 4: Após cada iteração, o elemento mínimo é trocado na frente do array não classificado.

concatenação de strings

Etapa - 5: A segunda e a terceira etapas são repetidas até obtermos o array classificado.

Algoritmo de classificação por seleção

O algoritmo de classificação por seleção é o seguinte.

Algoritmo

 selection_sort(array) repeat (0, length - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element <currentminimum set element as new minimum swap with first unsorted position end selection_sort < pre> <h2>Selection Sort Program using Python</h2> <p>The following code snippet shows the selection sort algorithm implementation using Python.</p> <p> <strong>Code -</strong> </p> <pre> def selection_sort(array): length = len(array) for i in range(length-1): minIndex = i for j in range(i+1, length): if array[j] <array[minindex]: minindex="j" array[i], array[minindex]="array[minIndex]," array[i] return array print('the sorted is: ', selection_sort(array)) < pre> <p> <strong>Output:</strong> </p> <pre> The sorted array is: [3, 6, 9, 21, 33] </pre> <p> <strong>Explanation -</strong> </p> <p>Let&apos;s understand the above code -</p> <ul> <li>First, we define the <strong>selection_sort()</strong> function that takes array as an argument.</li> <li>In the function, we get the length of the array which used to determine the number of passes to be made comparing values.</li> <li>As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable</li> <li>The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.</li> <li>Find the minimum element in the unsorted list and update the minIndex position.</li> <li>Place the value at the beginning of the array.</li> <li>Once the iteration is completed, the sorted array is returned.</li> <li>At last we create an unsorted array and pass to the <strong>selection_sort()</strong> It prints the sorted array.</li> </ul> <h2>Time Complexity of Selection Sort</h2> <p>Time complexity is an essential in term of how much time an algorithm take to sort it. In the selection sort, there are two loops. The outer loop runs for the n times (n is a total number of element).</p> <p>The inner loop is also executed for n times. It compares the rest of the value to outer loop value. So, there is n*n times of execution. Hence the time complexity of merge sort algorithm is O(n<sup>2</sup>).</p> <p>The time complexity can be categorized into three categories.</p> <hr></array[minindex]:></pre></currentminimum>

Explicação -

Vamos entender o código acima -

• Primeiro, definimos o seleção_sort() função que recebe array como argumento.
• Na função, obtemos o comprimento do array que serve para determinar o número de passagens a serem feitas na comparação de valores.
• Como podemos ver, usamos dois loops - loop externo e interno. O loop externo usa para iterar pelos valores da lista. Este loop irá iterar de 0 a (comprimento-1). Portanto, a primeira iteração será executada (5-1) ou 4 vezes. Em cada iteração, o valor da variável i é atribuído à variável
• O loop interno é usado para comparar cada valor do elemento do lado direito com o outro valor do elemento mais à esquerda. Portanto, o segundo loop inicia sua iteração em i+1. Ele escolherá apenas o valor que não está classificado.
• Encontre o elemento mínimo na lista não classificada e atualize a posição minIndex.
• Coloque o valor no início da matriz.
• Assim que a iteração for concluída, o array classificado será retornado.
• Por fim, criamos um array não classificado e passamos para o seleção_sort() Ele imprime o array classificado.

Complexidade temporal da classificação de seleção

A complexidade do tempo é essencial em termos de quanto tempo um algoritmo leva para classificá-lo. Na classificação por seleção, existem dois loops. O loop externo é executado n vezes (n é o número total de elementos).

O loop interno também é executado n vezes. Ele compara o restante do valor com o valor do loop externo. Portanto, há n*n tempos de execução. Portanto, a complexidade de tempo do algoritmo de classificação por mesclagem é O (n²).

A complexidade do tempo pode ser categorizada em três categorias.