TechCodeview

En aquest tutorial, implementarem l'algorisme d'ordenació de selecció a Python. És un algorisme força senzill que utilitza menys intercanvis.

En aquest algorisme, seleccionem l'element més petit d'una matriu no ordenada a cada passada i intercanviem amb l'inici de la matriu no ordenada. Aquest procés continuarà fins que tots els elements es col·loquin al lloc correcte. És senzill i un algorisme d'ordenació de comparació in situ.

Funcionament de l'ordenació de selecció

A continuació es mostren els passos per explicar el funcionament de l'ordenació de selecció a Python.

Prenem una matriu no ordenada per aplicar l'algorisme d'ordenació de selecció.

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

Pas 1: Obteniu la longitud de la matriu.

són exemples model

longitud = len (matriu) → 6

Pas - 2: Primer, establim el primer element com a element mínim.

Pas - 3: Ara compareu el mínim amb el segon element. Si el segon element és més petit que el primer, l'assignem com a mínim.

De nou comparem el segon element amb el tercer i si el tercer element és més petit que el segon, assignem-lo com a mínim. Aquest procés continua fins que trobem l'últim element.

Pas - 4: Després de cada iteració, l'element mínim s'intercanvia davant de la matriu no ordenada.

Pas - 5: Els passos del segon al tercer es repeteixen fins que aconseguim la matriu ordenada.

Algoritme d'ordenació de selecció

L'algorisme d'ordenació de selecció és el següent.

Algorisme

gestor de tasques per a linux

 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ó -

Entenem el codi anterior:

• En primer lloc, definim el selecció_ordenar() funció que pren array com a argument.
• A la funció, obtenim la longitud de la matriu que solia determinar el nombre de passades a fer comparant valors.
• Com podem veure, fem servir dos bucles: bucle exterior i bucle interior. El bucle exterior s'utilitza per iterar pels valors de la llista. Aquest bucle repetirà de 0 a (longitud-1). Per tant, la primera iteració es realitzarà (5-1) o 4 vegades. En cada iteració, el valor de la variable i s'assigna a la variable
• El bucle interior s'utilitza per comparar cada valor de l'element del costat dret amb l'altre valor de l'element més esquerre. Així, el segon bucle comença la seva iteració des de i+1. Només escollirà el valor que no estigui ordenat.
• Cerqueu l'element mínim a la llista sense ordenar i actualitzeu la posició minIndex.
• Col·loca el valor al principi de la matriu.
• Un cop completada la iteració, es retorna la matriu ordenada.
• Per fi creem una matriu sense ordenar i passem a selecció_ordenar() Imprimeix la matriu ordenada.

Complexitat temporal de l'ordenació de la selecció

La complexitat del temps és essencial pel que fa al temps que triga un algorisme a ordenar-lo. A l'ordenació de selecció, hi ha dos bucles. El bucle exterior s'executa durant n vegades (n és un nombre total d'elements).

El bucle intern també s'executa n vegades. Compara la resta del valor amb el valor del bucle exterior. Per tant, hi ha n*n vegades d'execució. Per tant, la complexitat temporal de l'algorisme d'ordenació de fusió és O(n²).

La complexitat del temps es pot classificar en tres categories.