Existen algoritmos de selección O(n) (lineal en el peor caso), y algoritmos sublineales son posibles para datos estructurados; en el caso extremos, O(1) para un vector de elementos ordenados.
Así como el ordenamiento total, el ordenamiento parcial significa que posteriores selecciones (debajo del k-ésimo elemento) pueden ser hechas en tiempo O(1) en una vector y en tiempo O(k) en una lista.
Un simple ejemplo de selección por ordenación parcial es usar el selection sort.
Esto es asintóticamente ineficiente, pero puede ser suficientemente eficiente si k es pequeño, y es fácil de implementar.
Concretamente, simplemente encontramos el mínimo y lo movemos al principio, repitiendo sobre la lista restante hasta haber acumulado k elementos, y luego retornando el k-ésimo elemento.
En la práctica el costo del cálculo del pivote es significativo, por lo que estos algoritmos no se utilizan generalmente, pero esta técnica es de interés teórico en relacionar los algoritmos de selección y ordenamiento.
como el mínimo número de comparaciones necesarias para encontrar los t menores elementos.
Knuth referencia el artículo publicado por S. S. Kislitsyn, que muestra un upper bound de este valor: Este límite es alcanzable para t=2 pero mejores, y más complejos límites son conocidos para mayores t. La complejidad espacial de la selección es k + O(1) (o n − k si k > n/2), y los algoritmos pueden seleccionar con solo O(1) memoria adicional.
Notar que la selección del mínimo (o máximo) es un caso especial de esto, con k = 1.
Notar, sin embargo, que la selección por ordenación parcial, mientras es eficiente en memoria, tiene complejidad superlineal, y que los algoritmos de selección basados en partición y eficientes en tiempo requieren O(n) memoria.
La selección en línea puede ser vista como el cálculo del k-ésimo menor elemento de un flujo de datos, en el cual los algoritmos de ordenamiento parcial (con k + O(1) memoria para los k menores elementos hasta el momento) pueden ser usados, pero los basados en partición no.
Además, el módulo Statistics::CaseResampling proporciona una función para calcular los cuantiles usando quickselect.