ORDEN DE SELECCIÓN - TUTORIAL DS

En este artículo, analizaremos el algoritmo de clasificación por selección. El procedimiento de trabajo de clasificación por selección también es sencillo. Este artículo será muy útil e interesante para los estudiantes, ya que podrían enfrentarse a la clasificación de selección como una pregunta en sus exámenes. Por eso es importante discutir el tema.

En la ordenación por selección, el valor más pequeño entre los elementos no clasificados de la matriz se selecciona en cada pasada y se inserta en su posición apropiada en la matriz. También es el algoritmo más simple. Es un algoritmo de clasificación por comparación in situ. En este algoritmo, la matriz se divide en dos partes, la primera es la parte ordenada y la otra es la parte no ordenada. Inicialmente, la parte ordenada de la matriz está vacía y la parte no ordenada es la matriz dada. La parte ordenada se coloca a la izquierda, mientras que la parte sin clasificar se coloca a la derecha.

En la ordenación por selección, el primer elemento más pequeño se selecciona de la matriz sin ordenar y se coloca en la primera posición. Después de eso, se selecciona el segundo elemento más pequeño y se coloca en la segunda posición. El proceso continúa hasta que la matriz esté completamente ordenada.

La complejidad promedio y del peor de los casos del tipo de selección es En²) , dónde norte es el número de elementos. Por este motivo, no es adecuado para grandes conjuntos de datos.

La ordenación por selección se utiliza generalmente cuando:

Se debe ordenar una pequeña matriz
El costo de intercambio no importa
Es obligatorio comprobar todos los elementos.

Ahora, veamos el algoritmo de clasificación por selección.

Algoritmo

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

Funcionamiento del algoritmo de clasificación por selección

Ahora, veamos el funcionamiento del algoritmo de clasificación por selección.

Para comprender el funcionamiento del algoritmo de clasificación por selección, tomemos una matriz sin clasificar. Será más fácil entender el tipo de selección mediante un ejemplo.

Dejemos que los elementos de la matriz sean:

Ahora, para la primera posición en la matriz ordenada, se debe escanear secuencialmente toda la matriz.

Actualmente, 12 se almacena en la primera posición, después de buscar en toda la matriz, se encuentra que 8 es el valor más pequeño.

es5 frente a es6

Entonces, intercambie 12 con 8. Después de la primera iteración, 8 aparecerá en la primera posición en la matriz ordenada.

Para la segunda posición, donde se almacena actualmente 29, nuevamente escaneamos secuencialmente el resto de los elementos de la matriz sin clasificar. Después de escanear, encontramos que 12 es el segundo elemento más bajo de la matriz que debería aparecer en la segunda posición.

Ahora, intercambie 29 por 12. Después de la segunda iteración, aparecerá 12 en la segunda posición de la matriz ordenada. Entonces, después de dos iteraciones, los dos valores más pequeños se colocan al principio de forma ordenada.

El mismo proceso se aplica al resto de elementos de la matriz. Ahora mostramos una representación gráfica de todo el proceso de clasificación.

Ahora, la matriz está completamente ordenada.

Complejidad de clasificación de selección

Ahora, veamos la complejidad temporal de la clasificación de selección en el mejor de los casos, en el caso promedio y en el peor de los casos. También veremos la complejidad espacial del tipo de selección.

1. Complejidad del tiempo

Caso	Complejidad del tiempo
Mejor caso	En²)
Caso promedio	En²)
Peor de los casos	En²)

En²)

2. Complejidad espacial

Complejidad espacial	O(1)
Estable	SÍ

La complejidad espacial del tipo de selección es O (1). Esto se debe a que, en la clasificación por selección, se requiere una variable adicional para el intercambio.

Implementación de clasificación por selección.

Ahora, veamos los programas de selección ordenados en diferentes lenguajes de programación.

Programa: Escriba un programa para implementar la clasificación por selección en lenguaje C.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

Producción:

Programa: Escriba un programa para implementar la clasificación por selección en Java.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

Producción:

Después de la ejecución del código anterior, el resultado será:

Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo.

Este artículo no se limitó sólo al algoritmo. También hemos discutido la complejidad, el funcionamiento y la implementación del tipo de selección en diferentes lenguajes de programación.

TechCodeview

Algoritmo de clasificación de selección