Quicksort

[killezio]

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 January 21, 2016 at 04:08 PM by thoga31
GeSHi

[tiago.f]

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)?

no canto inferior direito so sublime, convert os tabs para espaços. Deve aparecer bem depois.

[killezio]

Uma questão, precisei de fazer o quicksort para resolver um exercício. mas agora nao queria estar a colar o código na folha onde estou a trabalhar,mas sim importar de alguma forma o código. isso é possível? como é que se faz?

[killezio]

no canto inferior direito so sublime, convert os tabs para espaços. Deve aparecer bem depois.

muito melhor, obrigado

[tiago.f]

acho que usando, por exemplo,

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

importará um ficheiro do directório actual (onde está o ficheiro que tem este include)

[killezio]

acho que usando, por exemplo,

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

importará um ficheiro do directório actual (onde está o ficheiro que tem este include)

não terá que haver uma espécie de main 2 ou assim?

[HappyHippyHippo]

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 January 21, 2016 at 01:15 PM by HappyHippyHippo

[tiago.f]

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

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

[HappyHippyHippo]

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 January 21, 2016 at 01:15 PM by HappyHippyHippo

[HappyHippyHippo]

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

[killezio]

tenho uma dúvida, o que é que a linha 5 faz?

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

[HappyHippyHippo]

tenho uma dúvida, o que é que a linha 5 faz?

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

troca os valores, a para b, e b para a

[killezio]

troca os valores, a para b, e b para a

obrigado 🙂 podes também explicar como é que isso está a acontecer? não sei o que é o "^="...

[HappyHippyHippo]

obrigado 🙂 podes também explicar como é que isso está a acontecer? não sei o que é o "^="...

https://en.wikipedia.org/wiki/XOR_swap_algorithm