TechCodeview

En este tutorial, implementaremos el algoritmo de clasificación por selección en Python. Es un algoritmo bastante sencillo que utiliza menos intercambio.

En este algoritmo, seleccionamos el elemento más pequeño de una matriz sin clasificar en cada pasada y lo intercambiamos con el comienzo de la matriz sin clasificar. Este proceso continuará hasta que todos los elementos estén colocados en el lugar correcto. Es un algoritmo de clasificación de comparación simple y local.

Trabajo de clasificación por selección

Los siguientes son los pasos para explicar el funcionamiento del tipo de selección en Python.

Tomemos una matriz sin clasificar para aplicar el algoritmo de clasificación por selección.

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

algoritmo de clasificación por fusión

Paso 1: Obtenga la longitud de la matriz.

longitud = len(matriz) → 6

Paso 2: Primero, configuramos el primer elemento como elemento mínimo.

Paso 3: Ahora compare el mínimo con el segundo elemento. Si el segundo elemento es menor que el primero, lo asignamos como mínimo.

Nuevamente comparamos el segundo elemento con el tercero y si el tercer elemento es más pequeño que el segundo, lo asignamos como mínimo. Este proceso continúa hasta que encontramos el último elemento.

Etapa 4: Después de cada iteración, el elemento mínimo se intercambia delante de la matriz sin ordenar.

árbol binario transversal de pedidos por correo

Paso - 5: Los pasos segundo a tercero se repiten hasta que obtengamos la matriz ordenada.

Algoritmo de clasificación de selección

El algoritmo de clasificación de selección es el siguiente.

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>

Explicación -

Entendamos el código anterior:

• Primero, definimos el selección_sort() Función que toma una matriz como argumento.
• En la función, obtenemos la longitud de la matriz que se utiliza para determinar el número de pasadas a realizar comparando valores.
• Como podemos ver, utilizamos dos bucles: bucle exterior e interior. El bucle externo se utiliza para iterar a través de los valores de la lista. Este bucle se repetirá de 0 a (longitud-1). Entonces la primera iteración se realizará (5-1) o 4 veces. En cada iteración, el valor de la variable i se asigna a la variable
• El bucle interno se utiliza para comparar cada valor del elemento del lado derecho con el otro valor del elemento más a la izquierda. Entonces el segundo ciclo comienza su iteración desde i+1. Sólo seleccionará el valor que no esté ordenado.
• Busque el elemento mínimo en la lista desordenada y actualice la posición minIndex.
• Coloque el valor al principio de la matriz.
• Una vez que se completa la iteración, se devuelve la matriz ordenada.
• Por último creamos una matriz sin clasificar y la pasamos al selección_sort() Imprime la matriz ordenada.

Complejidad temporal de la clasificación de selección

La complejidad del tiempo es esencial en términos de cuánto tiempo tarda un algoritmo en ordenarlo. En la clasificación de selección hay dos bucles. El bucle externo se ejecuta n veces (n es el número total de elementos).

El bucle interno también se ejecuta n veces. Compara el resto del valor con el valor del bucle externo. Entonces, hay n*n tiempos de ejecución. Por lo tanto, la complejidad temporal del algoritmo de clasificación por fusión es O (n²).

La complejidad del tiempo se puede clasificar en tres categorías.