| Clasificación de selección | |
|---|---|
| | |
| objetivo | Algoritmo de clasificación |
| Estructura de datos | formación |
| peor momento | O( n 2 ) |
| Mejor tiempo | O( n 2 ) |
| Tiempo promedio | O( n 2 ) |
| costo de memoria | O(1) |
| Archivos multimedia en Wikimedia Commons | |
La clasificación por selección es un algoritmo de clasificación . Puede ser estable o inestable. En una matriz de n elementos, tiene un tiempo de ejecución en el peor de los casos, en el promedio y en el mejor de los casos de Θ ( n 2 ), suponiendo que las comparaciones se realizan en tiempo constante.
Pasos del algoritmo:
Un ejemplo de una implementación inestable :
plantilla < nombre de tipo type_arr > void selection_sort ( type_arr * arr , int size ) { para ( int i = 0 ; i < tamaño - 1 ; i ++ ) { int min_index = yo ; para ( int j = i + 1 ; j < tamaño ; j ++ ) { si ( arr [ j ] < arr [ min_index ]) { índice_min = j ; } } si ( min_index ! = i ) { intercambio ( arr [ i ], arr [ min_index ]); } } } IList estática pública < T > Selección < T > ( IList < T > lista ) donde T : IComparable < T > { for ( int i = 0 ; i < lista . Cuenta - 1 ; ++ i ) { int min = yo ; for ( int j = i + 1 ; j < lista . Cuenta ; ++ j ) { if ( lista [ j ]. CompareTo ( lista [ min ]) < 0 ) { mín = j ; } } vardummy = lista [ i ] ; lista [ i ] = lista [ min ]; lista [ min ] = dummy ; } lista de retorno ; }PL/SQL
tipo sort_choice_list es una tabla de índice de enteros por binary_integer ; -------------------------------------------------- -- función SORT_CHOICE devuelve sort_choice_list ES lista sort_choise_list ; l_min pls_integer ; l_dummy pls_integer ; empezar para n en 1 .. 100 bucles lista ( n ): = dbms_random . aleatorio ; --inicialización de matriz con números aleatorios bucle final ; para i en la lista . primero .. lista . último bucle l_min : = yo ; para j en ( i + 1 ) .. lista . último bucle si ( lista ( j ) < lista ( l_min )) entonces l_mín : = j ; terminar si ; bucle final ; l_dummy : = lista ( i ); lista ( i ): = lista ( l_min ); lista ( l_min ) : = l_dummy ; bucle final ; lista de retorno ; fin SORT_CHOICE ; public static < T se extiende Comparable <? súper T >> clasificación vacía ( T [] matriz ) { for ( int i = 0 ; i < arreglo . longitud - 1 ; ++ i ) { int minPos = i ; for ( int j = i + 1 ; j < matriz . longitud ; ++ j ) { if ( matriz [ j ] . compareTo ( matriz [ minPos ] ) < 0 ) { minPos = j ; } } T saveValue = matriz [ minPos ] ; arreglo [ minPos ] = arreglo [ i ] ; matriz [ i ] = saveValue ; } } def selección_ordenar ( matriz ) para min en 0 .. matriz . contar - 2 menos = min para j en ( min + 1 ) .. matriz . contar - 1 si matriz [ j ] < matriz [ menos ] menos = j final final temperatura = matriz [ min ] matriz [ min ] = matriz [ menor ] matriz [ menor ] = temporal final final func selectionSort < Elemento >( _ array : inout Array < Elemento >) where Elemento : Comparable { para min en 0. .< matriz . contar - 1 { para j en min ..< matriz . contar { si matriz [ j ] < matriz [ min ] { let temp = matriz [ min ] matriz [ min ] = matriz [ j ] matriz [ j ] = temporal } } } } empezar var a := ArrRandom ; un . Imprimir ; para var i := 0 a a . alto hacer Intercambiar ( a [ i ] , a [ i + a [ i : ] . IndexMin ]) ; un . Imprimir ; final def seleccionar_ordenar ( A ): para i en rango ( len ( A ) - 1 ): para k en rango ( i + 1 , len ( A )): si A [ k ] < A [ i ]: UNA [ k ], UNA [ yo ] = UNA [ yo ], UNA [ k ] func selecciónOrdenar ( nums [] int ) { n := len ( numeros ) para yo := 0 ; yo < n ; yo ++ { min := yo para j := i + 1 ; j < norte ; j ++ { si números [ j ] < números [ min ] { mín = j } } números [ i ], números [ min ] = números [ min ], números [ i ] } }Demostremos por qué esta implementación es inestable.
Considere la siguiente matriz de elementos, cada uno con dos campos. La clasificación va en el primer campo.
Matriz antes de ordenar:
{ (2, a), (2, b), (1, a) }
Ya después de la primera iteración del bucle externo, tendremos una secuencia ordenada:
{ (1, a), (2, b), (2, a) }
Ahora observe que la posición relativa de los elementos (2, a) y (2, b) ha cambiado. Por lo tanto, la implementación considerada es inestable.
Dado que solo se realiza un intercambio después de cada paso por el circuito interno, el número total de intercambios es N-1, que es N/2 veces menor que en el tipo de burbuja .
El número de pases a través del bucle interno es N-1 incluso si se clasifica una matriz ordenada parcial o completamente.
Peor caso:
el número de comparaciones en el cuerpo del bucle es (N-1)*N/2.
Número de comparaciones en encabezados de bucle (N-1)*N/2.
Número de comparaciones antes de la operación de cambio N-1.
El número total de comparaciones es N 2 −1.
Número de intercambios N-1.
Mejor caso:
El tiempo de clasificación de 10.000 enteros cortos en el mismo sistema de hardware y software por clasificación por selección fue de ≈40 segundos, y la clasificación de burbuja aún más mejorada fue de ≈30 segundos.
Heapsort mejora en gran medida el algoritmo subyacente mediante el uso de una estructura de datos de montón para acelerar la búsqueda y eliminación del elemento mínimo.
También existe una variante bidireccional de clasificación por selección, en la que tanto los valores mínimos como máximos se encuentran y se establecen en cada pasada.
| Algoritmos de clasificación | |
|---|---|
| Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
| Intercambio | |
| Elección | |
| inserciones | |
| fusión | |
| sin comparaciones | |
| híbrido | |
| Otro | |
| poco práctico | |