Função da biblioteca C para realizar a classificação

Existe alguma função de biblioteca disponível na biblioteca padrão C para fazer a classificação?

qsort()é a função que você está procurando. Você o chama com um ponteiro para seu array de dados, o número de elementos nesse array, o tamanho de cada elemento e uma função de comparação.

Ele faz sua mágica e seu array é classificado no local. Segue um exemplo:

#include <stdio.h>
#include <stdlib.h>
int comp (const void * elem1, const void * elem2) 
{
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return  1;
    if (f < s) return -1;
    return 0;
}
int main(int argc, char* argv[]) 
{
    int x[] = {4,5,2,3,1,0,9,8,6,7};

    qsort (x, sizeof(x)/sizeof(*x), sizeof(*x), comp);

    for (int i = 0 ; i < 10 ; i++)
        printf ("%d ", x[i]);

    return 0;
}

A biblioteca padrão C / C ++ <stdlib.h>contém qsortfunções.

Esta não é a melhor implementação de classificação rápida do mundo, mas é rápida e MUITO FÁCIL de ser usada ... a sintaxe formal do qsort é:

qsort(<arrayname>,<size>,sizeof(<elementsize>),compare_function);

A única coisa que você precisa implementar é compare_function, que recebe dois argumentos do tipo "const void", que podem ser convertidos para a estrutura de dados apropriada e, em seguida, retorna um destes três valores:

• negativo, se a deve ser antes de b
• 0, se a igual a b
• positivo, se a deve ser após b

1. Comparando uma lista de inteiros :

simplesmente fundido a e b para se inteiros x < y, x-yé negativo, x == y, x-y = 0, x > y, x-yé positiva x-yé uma forma de atalho para fazê-lo :) reverter *x - *ypara *y - *xpor ordem decrescente / ordem inversa

int compare_function(const void *a,const void *b) {
int *x = (int *) a;
int *y = (int *) b;
return *x - *y;
}

2. Comparando uma lista de strings :

Para comparar strings, você precisa de uma strcmpfunção dentro de <string.h>lib. strcmpirá, por padrão, retornar -ve, 0, ve apropriadamente ... para classificar na ordem reversa, apenas inverta o sinal retornado por strcmp

#include <string.h>
int compare_function(const void *a,const void *b) {
return (strcmp((char *)a,(char *)b));
}

3. Comparando números de ponto flutuante :

int compare_function(const void *a,const void *b) {
double *x = (double *) a;
double *y = (double *) b;
// return *x - *y; // this is WRONG...
if (*x < *y) return -1;
else if (*x > *y) return 1; return 0;
}

4. Comparando registros com base em uma chave :

Às vezes você precisa classificar coisas mais complexas, como o registro. Aqui está a maneira mais simples de fazer isso usando a qsortbiblioteca.

typedef struct {
int key;
double value;
} the_record;

int compare_function(const void *a,const void *b) {
the_record *x = (the_record *) a;
the_record *y = (the_record *) b;
return x->key - y->key;
}

Com certeza: qsort()é uma implementação de um tipo (não necessariamente quicksort como seu nome pode sugerir).

Tente man 3 qsort ou leia em http://linux.die.net/man/3/qsort

Embora não esteja exatamente na biblioteca padrão, https://github.com/swenson/sort tem apenas dois arquivos de cabeçalho que você pode incluir para obter acesso a uma ampla variedade de roteamentos de classificação incrivelmente rápidos, como:

#define SORT_NAME int64 #define SORT_TYPE int64_t #define SORT_CMP ( x , y ) (( x ) - ( y )) #include "sort.h" / * Agora você tem acesso a int64_quick_sort, int64_tim_sort, etc., por exemplo, * / 
int64_quick_sort ( arr , 128 ); / * Presume que você tenha algum int * arr ou int arr [128]; * /

   
 
  

Isso deve ser pelo menos duas vezes mais rápido que a biblioteca padrão qsort, já que não usa ponteiros de função e tem muitas outras opções de algoritmo de classificação para escolher.

Está no C89, então deve funcionar basicamente em todos os compiladores C.

tente qsortem stdlib.h.

Use qsort()em <stdlib.h>.

@paxdiablo A qsort()função está de acordo com a ISO / IEC 9899: 1990 (`` ISO C90 '').

Existem várias funções de classificação C disponíveis em stdlib.h. Você pode fazer man 3 qsortem uma máquina Unix para obter uma lista deles, mas eles incluem:

• heapsort
• ordenação rápida
• mergesort