Algoritmos de selección

El algoritmo de selección es un algoritmo para encontrar el número k-ésimo más pequeño (o más grande) en una lista o array . Ese número se llama estadístico de k-ésimo orden . Incluye los diversos casos para encontrar los elementos mínimo, máximo y mediano en una lista o una array . Para encontrar el elemento mínimo (o máximo) iterando a través de la lista, hacemos un seguimiento de los elementos mínimos (o máximos) actuales que ocurren hasta el momento y está relacionado con el ordenamiento por selección .
A continuación se muestran las diferentes formas de seleccionar el k-ésimo elemento más pequeño (o más grande) en una lista desordenada:

1. Selección por
   ordenación Ordenar la lista o una array y luego seleccionar el elemento requerido puede facilitar la selección. Este método es ineficiente para seleccionar un solo elemento, pero es eficiente cuando se deben realizar muchas selecciones de una array para la que solo se necesita ordenar una array. Porque la selección en una lista enlazada es O(n) incluso si la lista enlazada está ordenada debido a la falta de acceso aleatorio.
   En lugar de ordenar la lista completa o una array , podemos usar una clasificación parcial para seleccionar el k-ésimo elemento más pequeño (o más grande) en una lista o array. Entonces, el k-ésimo más pequeño (o más grande) es el elemento más grande (o más pequeño) de la lista parcialmente ordenada. Esto requiere O(1) para acceder a una array y O(k) para acceder a una lista.
   • Ordenación parcial desordenada La ordenación
     parcial desordenada es un algoritmo de ordenación de tal manera que los primeros k elementos están ordenados y el resto de elementos están en orden aleatorio. Para encontrar el k-ésimo elemento más pequeño (o más grande). La complejidad del tiempo se reduce a O(k log k) . Pero como K ≤ n, la Complejidad de Tiempo asintótica converge a O(n) . Nota: Debido a la posibilidad de igualdad de elementos, no se debe incluir el elemento menor o igual al k-ésimo elemento al ordenar una lista o una array , ya que el elemento mayor que el k-ésimo elemento también puede ser igual al k-ésimo elemento más pequeño.
     
   • Ordenación por selección parcial
     El concepto utilizado en la Ordenación por selección nos ayuda a ordenar parcialmente el arreglo hasta el késimo elemento más pequeño (o más grande) para encontrar el késimo elemento más pequeño (o más grande) en un arreglo. Por lo tanto, una ordenación por selección parcial produce un algoritmo de selección simple que toma O(k*n) tiempo para ordenar la array . Esto es asintóticamente ineficiente pero puede ser suficientemente eficiente si k es pequeño y es fácil de implementar.
     A continuación se muestra el algoritmo para la ordenación por selección parcial :

     function partialSelectionSort(arr[0..n], k) {
         for i in [0, k) {
             minIndex = i
             minValue = arr[i]
             for j in [i+1, n) {
                 if (arr[j] < minValue)  then
                     minIndex = j
                     minValue = arr[j]
                     swap(arr[i], arr[minIndex])
             }  
         }
         return arr[k]
     }
     

2. Selección basada
   en particiones Para la selección basada en particiones, se utiliza el algoritmo de selección rápida . Es una variante del algoritmo quicksort . En ambos, elegimos un elemento pivote y, utilizando el paso de partición del algoritmo de clasificación rápida , organiza todos los elementos más pequeños que el pivote a su izquierda y los elementos más grandes que él a su derecha.
   Pero mientras Quicksort recurre en ambos lados de la partición, Quickselect solo recurre en un lado, el lado en el que está presente el k-ésimo elemento deseado.
   Los algoritmos basados ​​en particiones se realizan en su lugar, lo que da como resultado una clasificación parcial de los datos. Se pueden hacer fuera de lugar al no cambiar los datos originales a costa de O(n)espacio auxiliar.
3. Mediana seleccionada como pivote
   Se puede utilizar un algoritmo de selección de mediana para realizar un algoritmo de selección o un algoritmo de ordenación, seleccionando la mediana de la array como el elemento pivote en el algoritmo Quickselect o Quicksort .
   En la práctica, la sobrecarga del cálculo del pivote es significativa, por lo que estos algoritmos generalmente no se utilizan, pero esta técnica es de interés teórico para relacionar los algoritmos de selección y clasificación.
   La mediana de una array es el mejor pivote para clasificar una array porque divide uniformemente los datos en dos partes y, por lo tanto, garantiza una clasificación óptima, suponiendo que el algoritmo de selección sea óptimo.