Función de comparación de qsort() en C

La biblioteca C estándar proporciona qsort() que se puede usar para ordenar una array. Como sugiere el nombre, la función usa el algoritmo QuickSort para ordenar la array dada. El siguiente es un prototipo de qsort()

void qsort (void* base, size_t num, size_t size, 
            int (*comparator)(const void*,const void*));

El punto clave sobre qsort() es la función de comparación comparador . La función de comparación toma dos argumentos y contiene lógica para decidir su orden relativo en la salida ordenada. La idea es proporcionar flexibilidad para que qsort() se pueda usar para cualquier tipo (incluidos los tipos definidos por el usuario) y se pueda usar para obtener cualquier orden deseado (creciente, decreciente o cualquier otro).

La función de comparación toma dos punteros como argumentos (ambos convertidos a const void*) y define el orden de los elementos devolviendo (de manera estable y transitiva)

int comparator(const void* p1, const void* p2);
Return value meaning
<0 The element pointed by p1 goes before the element pointed by p2
0  The element pointed by p1 is equivalent to the element pointed by p2
>0 The element pointed by p1 goes after the element pointed by p2

Source: http://www.cplusplus.com/reference/cstdlib/qsort/

Por ejemplo, deje que haya una array de estudiantes donde el siguiente es el tipo de estudiante.

struct Student
{
    int age, marks;
    char name[20];
};

Digamos que necesitamos clasificar a los estudiantes según las calificaciones en orden ascendente. La función de comparación se verá así:

int comparator(const void *p, const void *q) 
{
    int l = ((struct Student *)p)->marks;
    int r = ((struct Student *)q)->marks; 
    return (l - r);
}

Consulte las siguientes publicaciones para ver más ejemplos de usos de qsort().
Dada una secuencia de palabras, imprima todos los anagramas juntos
Problema de apilamiento
de cajas Par de puntos más cercano

El siguiente es un problema interesante que se puede resolver fácilmente con la ayuda de qsort() y la función de comparación.
Dada una array de números enteros, ordénela de tal manera que los números impares aparezcan primero y los números pares aparezcan después. Los números impares deben ordenarse en orden descendente y los números pares deben ordenarse en orden ascendente.

El enfoque simple es modificar primero la array de entrada de modo que los números pares e impares se separen y luego aplicar algún algoritmo de clasificación en ambas partes (pares e impares) por separado.

Sin embargo, existe un enfoque interesante con una pequeña modificación en la función de comparación de Quick Sort. La idea es escribir una función de comparación que tome dos direcciones p y q como argumentos. Sean l y r el número apuntado por p y q. La función usa la siguiente lógica:
1) Si ambos (l y r) son impares, coloque primero el mayor de dos.
2) Si ambos (l y r) son pares, coloque primero el menor de dos.
3) Si uno de ellos es par y el otro es impar, pon primero el número impar.

A continuación se muestra la implementación en C del enfoque anterior.

#include <stdio.h>
#include <stdlib.h>
  
// This function is used in qsort to decide the relative order
// of elements at addresses p and q.
int comparator(const void *p, const void *q)
{
    // Get the values at given addresses
    int l = *(const int *)p;
    int r = *(const int *)q;
  
    // both odd, put the greater of two first.
    if ((l&1) && (r&1))
        return (r-l);
  
    // both even, put the smaller of two first
    if ( !(l&1) && !(r&1) )
        return (l-r);
  
    // l is even, put r first
    if (!(l&1))
        return 1;
  
    // l is odd, put l first
    return -1;
}
  
// A utility function to print an array
void printArr(int arr[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
}
  
// Driver program to test above function
int main()
{
    int arr[] = {1, 6, 5, 2, 3, 9, 4, 7, 8};
  
    int size = sizeof(arr) / sizeof(arr[0]);
    qsort((void*)arr, size, sizeof(arr[0]), comparator);
  
    printf("Output array is\n");
    printArr(arr, size);
  
    return 0;
}

Producción:

Output array is
9 7 5 3 1 2 4 6 8

Ejercicio:
Dada una array de enteros, ordénela de manera alterna. Moda alternativa significa que los elementos en índices pares se ordenan por separado y los elementos en índices impares se ordenan por separado.

Este artículo ha sido compilado por Aashish Barnwal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.