Jump to content

Quicksort


killezio
 Share

Recommended Posts

Pessoal, fiz aqui o meu algoritmo quicksort (para quem nao conhece procure na wikipédia ou assim se estiver interessado) em C, no entanto já me tinham dito alguma coisa sobre usar apontadores para funções e coisas estranhas assim do género... De qualquer modo, se tiverem um código mais eficiente e/ou até mais limpo por favor partilhem!

PS: já agora, o meu código fica todo desformatado quando ponho aqui no fórum, mesmo usando a cena para postar o código. poderá ser do meu editor de texto (Sublime 2)?

#include <stdio.h>
#define N 10

void printf_vetor(int *vetor){
   int e;
   printf("\nVETOR");
   putchar('\n');
   for (e = 0;e<N;e++)
       printf(" %d ",vetor[e]);
   putchar('\n');
}


void find_pivot(int *vetor,int *usados,int *pivot){ // recebe o vetor onde vai percorrer todas as posições até encontrar um pivot (que ainda nao foi usado), transfere o pivot que vai utilizar já para os usados e grava o pivot no seu vetor próprio
   int e,k,_continue = 0;
   for (e = 0;e < N;e++){
       for (k = 1;k<=usados[0];k++){
           if (usados[k] == vetor[e]){ // foi encontrada uma ocorrência nos usados, faz-se continue no primeiro for
               _continue = 1;
               break;
           }
       }
       if (_continue == 1){
           _continue = 0;
           continue;
       }
       usados[++usados[0]] = vetor[e]; // incrementa o número de elementos que o vetor "usados" tem e também coloca lá o pivot
       pivot[++pivot[0]] = vetor[e]; 
       break;
   }
}

void comparar(int *vetor,int *menor,int *pivot,int *maior){ // k é o número do vetor que estamos a comparar com o pivot
   int e,k = 0;
   for (e = 0; e < N;e++) {
       if (pivot[1] == vetor[e])
           k++;
       else if (pivot[1] < vetor[e])
           maior[++maior[0]] = vetor[e];
       else 
           menor[++menor[0]] = vetor[e];
   }
   for (e = 1;e<k;e++)
       pivot[++pivot[0]] = pivot[1];
}

void concatenar(int * vetor,int * menor,int * pivot, int * maior) {
   int pos = 0,e;
   for (e = 1;e<= menor[0];e++)
       vetor[pos++] = menor[e];

   for (e = 1;e <= pivot[0];e++)
       vetor[pos++] = pivot[e];

   for (e = 1;e <= maior[0];e++)
       vetor[pos++] = maior[e];
}

int confirmar(int *vetor){
   int e,j;
   for ( e = 0; e < N - 1 ; e++, j = e +1 )
       if (vetor[e] > vetor[j])
           return 2; // ainda não acabou
   return 1; // o vetor já está ordenado

}

void quicksort(int *vetor){
   int menor[N];    // primeira posição é a contagem de quantos elementos já estão no vetor
   int pivot[N];    // aspas aspas
   int maior[N];    // aspas aspas
   int usados[N];   // aspas aspas & guardar os pivots que já foram percorridos
   usados[0] = 0;
   while (confirmar(vetor) != 1){
       menor[0] = pivot[0] = maior[0] = 0;
       find_pivot(vetor,usados,pivot);
       comparar(vetor,menor,pivot,maior);
       concatenar(vetor,menor,pivot,maior);
   }
}




int main(){
   int vetor[N+1] = {10,4,2,5,3,8,9,7,9,0};
   quicksort(vetor);
   printf_vetor(vetor);
   return 0;
}

Edited by thoga31
GeSHi
Link to comment
Share on other sites

se a pergunta é como fazer isso de forma muito mais simples, ok :

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define VECTOR_SIZE 10
#define VECTOR_MIN_VALUE 0
#define VECTOR_MAX_VALUE 10000

#define XORSWAP(a, b) (*(a) ^= *(b), *(b) ^= *(a), *(a) ^= *(b))

// função de apresentação da lista
void print_int_vector(int* vector, const size_t length)
{
   for (int i = 0; i < VECTOR_SIZE; ++i)
       printf("%d -> %d\n", i, vector[i]);
   printf("\n");
}

// função de comparação de dois inteiros a ser usada na ordenação ascendente da lista
int compare_int_asc(const void* a, const void* b)
{
   return *(int*) a - *(int*) b;
}

// função de comparação de dois inteiros a ser usada na ordenação descendente da lista
int compare_int_desc(const void* a, const void* b)
{
   return *(int*) b - *(int*) a;
}

// função que implementa um "in-place quicksort"
void quicksort_int(int* vector, int imin, int imax, int (*compare)(const void*, const void*))
{
   // verificar se existe elementos a serem ordenados
   if (imin >= imax)
       return;

   // determinar o estado inicial da ordenação
   int anchor = imin, amin = anchor + 1, amax = imax;

   // ciclo de verificação dos elementos de ordem superior ou inferior ao valor de âncora escolhido
   while(amin <= amax)
   {
       // comparar o valor iterado com a âncora
       if (compare(&vector[anchor], &vector[amin]) < 0)
       {
           // passar o valor para a lista dos valores superiores
           if (amin != amax)
               XORSWAP(&vector[amin], &vector[amax]);
           --amax;
       }
       else
           // passar o valor para a lista dos valores inferiores
           ++amin;
   }

   // colocar a âncora entre a lista dos valores inferiores e superiores
   if (anchor != amin - 1)
       XORSWAP(&vector[anchor], &vector[amin - 1]);

   // ordenar as duas listas de valores (inferiores e superiores)
   quicksort_int(vector, imin, amin - 2, compare);
   quicksort_int(vector, amin, imax, compare);
}

int main(int argc, char** argv)
{
   // criar a lista
   int vector[VECTOR_SIZE];
   srand((unsigned int) time(NULL));
   for (int i = 0; i < VECTOR_SIZE; ++i)
       vector[i] = (rand() % (VECTOR_MAX_VALUE - VECTOR_MIN_VALUE)) + VECTOR_MIN_VALUE;

   // apresentar a lista desordenada
   print_int_vector(vector, VECTOR_SIZE - 1);

   // ordenar a lista pela ordem ascendente e apresentar-la na consola
   quicksort_int(vector, 0, VECTOR_SIZE - 1, compare_int_asc);
   print_int_vector(vector, VECTOR_SIZE - 1);

   // ordenar a lista pela ordem descendente e apresentar-la na consola
   quicksort_int(vector, 0, VECTOR_SIZE - 1, compare_int_desc);
   print_int_vector(vector, VECTOR_SIZE - 1);

   return 0;
}

#include "funcoes.c" // aspas em vez de '<' e '>'

nunca se faz a inclusão dos ficheiros .c

se pretendes separar o código ou reutilizar o código, criar ficheiros .h com alusões às funções existentes dentro do ficheiro .c, e é sobre esse ficheiro que deverá ser feita a inclusão.

no final, será trabalho do linker juntar tudo, algo como

gcc -c -o codigo1.o codigo1.c
gcc -c -o codigo2.o codigo2.c
gcc -o exec codigo1.o codigo2.o
Edited by HappyHippyHippo
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

HHH, só um comentário ao excelente código: aparce algumas vezes "&"

Calculo seja devida a algum copy&paste de uma página web...

não foi copy paste da web que eu não necessito disso ... foi da edição do post

vou corrigir : CORRIGIDO

Edited by HappyHippyHippo
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

Pessoal, fiz aqui o meu algoritmo quicksort

estive a analisar o teu código e infelizmente o que tens implementado não é o quicksort.

a ideia fundamental do quicksort é "dividir para conquistar". usto é, após a escolha de um pivot, a lista é separada em duas listas (números inferiores e números superiores ao pivot) das quais serão alvo do mesmo processo de ordenação.

isto quer dizer que as duas novas listas, são mais pequenas até ao ponto que não existe nada a ordenar.

para verificar que o teu código não faz isso, basta ver a tua função comparar onde estás constantemente a usar a lista toda como alvo da separação dos elementos em relação ao pivot.

conclusão, apesar de o código que implementas usa pivot's, não quer dizer que implementas o algoritmo de forma correcta

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.