qsort es una función de biblioteca estándar de C que implementa un algoritmo de clasificación polimórfica para matrices de objetos arbitrarios de acuerdo con una función de comparación proporcionada por el usuario. Se nombra por el algoritmo (una "rápida tipo" quicksort variante debido a RS Scowen), que se utilizó originalmente para implementarlo en el Unix biblioteca de C, aunque el estándar C no lo requiere para poner en práctica la clasificación rápida. [1]
Las implementaciones de la función qsort logran polimorfismo , la capacidad de ordenar diferentes tipos de datos, al llevar un puntero de función a una función de comparación de tres vías , así como un parámetro que especifica el tamaño de sus objetos de entrada individuales. El estándar C requiere que la función de comparación implemente un pedido total en los elementos de la matriz de entrada. [2]
Historia
Lee McMahon implementó una función qsort en 1972. [3] [1] Estaba en la versión 3 de Unix como una función de biblioteca, pero entonces era una subrutina de ensamblador . [3]
La versión AC, con aproximadamente la interfaz de la versión C estándar, estaba instalada en la Versión 6 Unix . [4] Fue reescrito en 1983 para BSD . [1] La función se estandarizó en ANSI C (1989).
En 1991, los empleados de Bell Labs observaron que las versiones de qsort de McMahon y BSD consumían tiempo cuadrático para algunas entradas simples. Por lo tanto, Jon Bentley y Douglas McIlroy diseñaron una nueva implementación más rápida y robusta. [1]
Ejemplo
El siguiente fragmento de código C muestra cómo ordenar una lista de enteros usando qsort.
#include / * Función de comparación. Recibe dos indicadores genéricos (nulos) a los elementos que se comparan. * / int compare_ints ( const void * p , const void * q ) { int x = * ( const int * ) p ; int y = * ( const int * ) q ; / * Evite devolver x - y, que puede causar un comportamiento indefinido debido al desbordamiento de enteros con signo. * / if ( x < y ) return -1 ; // Devuelve -1 si quieres ascender, 1 si quieres un orden descendente. de lo contrario, si ( x > y ) devuelve 1 ; // Devuelve 1 si quieres ascender, -1 si quieres un orden descendente. return 0 ; // Toda la lógica a menudo se escribe alternativamente: return ( x > y ) - ( x < y ); }/ * Ordena una matriz de n enteros, apuntados por a. * / void sort_ints ( int * a , size_t n ) { qsort ( a , n , sizeof ( * a ), compare_ints ); }
Referencias
- ↑ a b c d Bentley, Jon L .; McIlroy, M. Douglas (1993). "Ingeniería de una función de clasificación" . Software: práctica y experiencia . 23 (11): 1249-1265. CiteSeerX 10.1.1.14.8162 . doi : 10.1002 / spe.4380231105 .
- ^ ISO / IEC 9899: 201x, Lenguajes de programación — C (borrador). §7.22.5. 16 de noviembre de 2010.
- ^ a b "qsort (III), del Manual del programador de UNIX, tercera edición" . Archivo Unix .
- ^ "qsort (III), del Manual del programador de UNIX, sexta edición" . Archivo Unix .