QuickSort Genérico

Publicado por Caio Dutra (última atualização em 11/08/2011)

[ Hits: 6.103 ]

Download sort.h




Implementação de um algoritmo de ordenação (Quick Sort) que recebe qualquer tipo de dado, desde que receba também como parâmetro, uma simples função de comparação.

  



Esconder código-fonte

/* -- sort.h
    
    Biblioteca para ordenação de vetores pelo método quicksort.
    Este algoritmo já vem disponível na biblioteca padrão da linguagem C,
    mas criei minha própria versão para fins didáticos.
    
    Copyright (c) Caio Dutra 2010
    <[email protected]> - BHzte/MG/Brasil
*/

#ifndef _SORT_H
#ifdef __cplusplus
extern "C" {
#endif

// --- Tools functions 

static void *access_at ( void *vetor, int pos, int tam ) {
    char *_r = (char *) vetor;
    _r += pos * tam;
    
    return ((void *)_r);
}

static void _swap ( void *a, void *b, int tam ) {
    char *i_a, *i_b, i, temp;
    i_a = (char *)a;
    i_b = (char *)b;
    
    for ( i = 0; i < tam; i++ ) {
        temp = *i_a;
        *i_a = *i_b;
        *i_b = temp;
        i_a++; i_b++;
    }
}

/* - quicksort method -
    */

#define _GENERIC_QUICKSORT

#if defined(_GENERIC_QUICKSORT)
// Quick sort
static void quicksort ( void *_array, int pos_i, int pos_f, int typesize, 
    int (*comp)( const void *, const void *));
#else
void quicksort ( int *_array, int pos_i, int pos_f );
#endif

static int
quicksort_part ( void *vetor, int pos_x, int pos_y, int sz, 
    int (*cmp)(const void *, const void *) )
{
    int x = pos_x,
        y = pos_y;
    // O pivot está em X
    while ( 1 )
    {
        while ( x < y && cmp (access_at ( vetor, x, sz ), 
            access_at ( vetor, y, sz )) <= 0 ) --y;
        if ( x < y )        
            _swap ( access_at ( vetor, x, sz ), access_at ( vetor, y, sz ),sz);
            // Agora, o pivot está em Y
        else break;
        while ( x < y && cmp (access_at ( vetor, y, sz ),
            access_at ( vetor, x, sz )) >= 0 ) ++x;
        if ( x < y )
            _swap ( access_at ( vetor, x, sz ), access_at ( vetor, y, sz ),sz);
            // Agora o pivot está em X
        else break;
    }    
    return (y);
}

static void
quicksort ( void *vetor, int pos_x, int pos_y, int sz,
    int (*cmp)(const void *, const void *) )
{
    if ( pos_x < pos_y )
    {
        int _r = quicksort_part ( vetor, pos_x, pos_y, sz, cmp );
        quicksort ( vetor, pos_x, _r - 1, sz, cmp );
        quicksort ( vetor, _r + 1, pos_y, sz, cmp );
    }
}

#ifdef __cplusplus
}
#endif
#define _SORT_H
#endif  /* _SORT_H */

Scripts recomendados

Função HASH em C++

BINCON 10

Arquivos utilizados no artigo: "Desenvolvendo um plugin para o XMMS"

Sudokou em C feito com matrizes e listas

analisador palavras


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts