QuickSort Genérico
Publicado por Caio Dutra (última atualização em 11/08/2011)
[ Hits: 6.965 ]
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.
/* -- 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 <caiodutra_bh@yahoo.com.br> - 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 */
Google Code Jam 2010 - Africa Classification Round
Jogo Final Fight - Haggar (com gráficos)
Nenhum comentário foi encontrado.
Como gerar um podcast a partir de um livro em PDF
Automatizando digitação de códigos 2FA no browser
Resolver problemas de Internet
Como compartilhar a tela do Ubuntu com uma Smart TV (LG, Samsung, etc.)
Conheça a 4Devs, caixa de ferramentas online para desenvolvedores
Como converter um vídeo MP4 para um GIF para publicar no README.md do seu repositório Github
Como Instalar o Microsoft Teams no Linux Ubuntu
Re: Copia e Cola no SED --> Processador de textos (3)
Ferramentas e métodos de criação de binários estáticos (0)
Alguém pode me explicar essa matemática? [RESOLVIDO] (6)