En este tutorial, aprenderá cómo funciona la ordenación por selección. Además, encontrará ejemplos prácticos de ordenación por selección en C, C ++, Java y Python.
El ordenamiento por selección es un algoritmo que selecciona el elemento más pequeño de una lista sin clasificar en cada iteración y coloca ese elemento al principio de la lista sin clasificar.
¿Cómo funciona el ordenamiento por selección?
- Establezca el primer elemento como
minimum.
Seleccione el primer elemento como mínimo - Compare
minimumcon el segundo elemento. Si el segundo elemento es más pequeño queminimum, asigne el segundo elemento comominimum.
Compareminimumcon el tercer elemento. Nuevamente, si el tercer elemento es más pequeño, entonces asigneminimumal tercer elemento; de lo contrario, no haga nada. El proceso continúa hasta el último elemento.
Compare el mínimo con los elementos restantes - Después de cada iteración,
minimumse coloca al principio de la lista sin clasificar.
Intercambia el primero con el mínimo - Para cada iteración, la indexación comienza desde el primer elemento sin clasificar. Se repiten los pasos 1 a 3 hasta que todos los elementos se colocan en sus posiciones correctas.
La primera iteración 
La segunda iteración 
La tercera iteración 
La cuarta iteración
Algoritmo de clasificación por selección
selectionSort (array, size) repeat (size - 1) times establece el primer elemento sin clasificar como el mínimo para cada uno de los elementos sin clasificar si el elemento <currentMinimum establece el elemento como nuevo mínimo de intercambio mínimo con la primera posición sin clasificar end selectionSort
Ejemplos de Python, Java y C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Complejidad
| Ciclo | Número de comparación |
|---|---|
| Primero | (n-1) |
| 2do | (n-2) |
| Tercero | (n-3) |
| … | … |
| último | 1 |
Número de comparaciones: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2casi igual a .n2
Complejidad =O(n2)
Además, podemos analizar la complejidad simplemente observando el número de bucles. Hay 2 bucles, por lo que la complejidad es .n*n = n2
Complejidades de tiempo:
- Complejidad del peor de los casos: si queremos clasificar en orden ascendente y la matriz está en orden descendente, entonces ocurre el peor de los casos.
O(n2) - Mejor complejidad de caso: ocurre cuando la matriz ya está ordenada
O(n2) - Complejidad de casos promedio: ocurre cuando los elementos de la matriz están en orden desordenado (ni ascendente ni descendente).
O(n2)
La complejidad temporal del tipo de selección es la misma en todos los casos. En cada paso hay que buscar el elemento mínimo y colocarlo en el lugar correcto. El elemento mínimo no se conoce hasta que no se alcanza el final de la matriz.
Complejidad espacial:
La complejidad del espacio se O(1)debe a que tempse utiliza una variable adicional .
Aplicaciones de clasificación por selección
La ordenación por selección se utiliza cuando:
- se debe ordenar una pequeña lista
- el costo del intercambio no importa
- Es obligatorio comprobar todos los elementos.
- el costo de escribir en una memoria importa como en la memoria flash (el número de escrituras / intercambios es
O(n)en comparación con el tipo de burbuja)O(n2)
