clasificación q

qsort es una función de la biblioteca estándar de C que implementa un algoritmo de ordenamiento para matrices de objetos arbitrarios según una función de comparación proporcionada por el usuario. Recibe su nombre del algoritmo "quicker sort" ^[1] (una variante de quicksort debida a RS Scowen), que se utilizó originalmente para implementarlo en la biblioteca C de Unix , aunque el estándar de C no lo requiere para implementar quicksort. ^[2]

La capacidad de operar con diferentes tipos de datos ( polimorfismo ) se logra tomando 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 orden total en los elementos de la matriz de entrada. ^[3]

En 1972, en la versión 2 de Unix , aparece una función qsort como una subrutina de biblioteca de lenguaje ensamblador . Su interfaz es diferente a la versión moderna, en el sentido de que se puede crear un pseudoprototipo como qsort(void * start, void * end, unsigned length): ordenar cadenas de bytes de longitud -long almacenadas de forma contigua del rango [ inicio , fin ]. ^[1] Esto, y la falta de una función de comparación reemplazable, la hacen inadecuada para ordenar correctamente los números enteros little-endian del sistema o cualquier otra estructura de datos.

En la versión 3 de Unix , la interfaz se amplía llamando a compar(III), con una interfaz idéntica a la actual memcmp . Esta función puede ser reemplazada por el programa del usuario para implementar cualquier tipo de ordenación, de manera equivalente al argumento de qsortcompar estándar (aunque global para el programa, por supuesto). ^[4]

La versión 4 de Unix añade una implementación en C, con una interfaz equivalente al estándar. ^[5] Fue reescrita en 1983 para la distribución de software de Berkeley . ^[2] La función fue estandarizada en ANSI C (1989). La implementación en ensamblador se elimina en la versión 6 de Unix . ^[6]

En 1991, los empleados de Bell Labs observaron que las versiones AT&T y BSD de qsort consumirían tiempo cuadrático para algunas entradas simples. Por ello, Jon Bentley y Douglas McIlroy diseñaron una nueva implementación más rápida y robusta. ^[2] McIlroy produciría más tarde una entrada de tiempo cuadrático más compleja, denominada AntiQuicksort , en 1998. Esta función construye datos del adversario sobre la marcha. ^[7]

El siguiente fragmento de código C muestra cómo ordenar una lista de números enteros utilizando qsort.

#incluir <stdlib.h> 

/* Función de comparación. Recibe dos punteros genéricos (void) a los elementos bajo comparación. */ 
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 desea orden ascendente, 1 si desea orden descendente. else if ( x > y ) return 1 ; // Devuelve 1 si desea orden ascendente, -1 si desea orden descendente.       
          
        
          

    retorna 0 ; // Toda la lógica a menudo se escribe alternativamente: return ( x > y ) - ( x < y ); } 
    
           


/* Ordena una matriz de n enteros, apuntada por a. */ 
void sort_ints ( int * a , size_t n ) { qsort ( a , n , sizeof ( * a ), compare_ints ); }     
       

Dado que la función de comparación del original qsortsolo acepta dos punteros, el paso de parámetros adicionales (por ejemplo, producir una función de comparación que compare por la diferencia de dos valores con otro valor) debe hacerse utilizando variables globales . El problema fue resuelto por los sistemas BSD y GNU similares a Unixqsort_r al introducir una función, que permite pasar un parámetro adicional a la función de comparación. Las dos versiones de qsort_rtienen diferentes órdenes de argumentos. El Anexo K de C11 define un qsort_sesencialmente idéntico al de GNU qsort_r. Las libcs ​​de macOS y FreeBSD también contienen qsort_b, una variante que utiliza bloques , un análogo a los cierres , como una solución alternativa al mismo problema. ^[8]