Estrutura de ordenação Quicksort [RESOLVIDO]

1. Estrutura de ordenação Quicksort [RESOLVIDO]

Matheus Cunha
mccastro

(usa Outra)

Enviado em 19/01/2015 - 23:04h

E aí galera, meu professor passou um trabalho que devemos fazer uma animação do quicksort (estrutura de ordenação). Eu não sei fazer, será que vcs poderiam me ajudar? o exemplo abaixo é do método de ordenação bubblesort!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TAM 10
char c[]={'*','-','>','?',1,2,3,4,5,6};
void desenha(int vet[]){
int i,j;
system("cls");
for(i=0;i<TAM;i++){
switch (vet[i]){
case 1:
printf("%d\t",vet[i]);
break;
case 2:
printf("%d\t",vet[i]);
break;
case 3:
printf("%d\t",vet[i]);
break;
case 4:
printf("%d\t",vet[i]);
break;
case 5:
printf("%d\t",vet[i]);
break;
case 6: printf("%d\t",vet[i]);
break;
case 7:
printf("%d\t",vet[i]);
break;
case 8:
printf("%d\t",vet[i]);
break;
case 9:
printf("%d\t",vet[i]);
break;
case 10:
printf("%d\t",vet[i]);
break;
}
for(j=0;j<vet[i];j++){
switch (vet[i]){
case 1:
printf("%c",c[0]);
break;
case 2:
printf("%c",c[1]);
break;
case 3:
printf("%c",c[2]);
break;
case 4:
printf("%c",c[3]);
break; case 5:
printf("%c",c[4]);
break;
case 6:
printf("%c",c[5]);
break;
case 7:
printf("%c",c[6]);
break;
case 8:
printf("%c",c[7]);
break;
case 9:
printf("%c",c[8]);
break;
case 10:
printf("%c",c[9]);
break;
}
}
printf("\n");
}
// _sleep(300);
getchar();
}
void bubblesort(int vet[]){
int i,j,aux;
desenha(vet);
for(i=0;i<TAM;i++){ for(j=i;j<TAM;j++){
if(vet[i]>vet[j]){
aux = vet[i];
vet[i] = vet[j];
vet[j] = aux;
desenha(vet);
}
}
}
}
int main()
{
// int vet[] ={10,4,6,8,9,2,3,5,1,7};
int vet[] ={10,9,8,7,6,5,4,3,2,1};
// int vet[] ={1,2,3,4,5,6,7,8,9,10};
system("COLOR FC");
bubblesort(vet);
return 0;
}



  


2. Re: Estrutura de ordenação Quicksort [RESOLVIDO]

Enzo de Brito Ferber
EnzoFerber

(usa FreeBSD)

Enviado em 22/01/2015 - 09:28h

Bom dia, @mccastro.


/* vol_forum/abubble.c
*
* Enzo Ferber
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define ARRAY_SIZE 10

/* int_cmp
*
* a - endereco de local contendo um int
* b - endereco de local contendo um int
*
* A funcao converte endereços em interpretações int e devolve o valor
* interpretado como uma subtração de inteiros (a - b);
*/
int int_cmp (void *a, void *b)
{
return (*(int *)a) - (*(int *)b);
}

/* int_print
*
* element - endereço de um elemento int a ser impresso
* index - posição ocupada pelo elemento no array/buffer
*
* A função converte o endereço de element em um ponteiro para int e
* interpreta esse endereço. Imprime o index do array e seu elemento, um por
* linha.
*/
void int_print (void *element, int index )
{
printf ("Element[%d]: %d\n", index, *(int*)element);
}

/* int_swap
*
* a - endereco de local contendo um int
* b - endereco de local contendo um int
*
* A função realiza a troca de posições entre os conteúdos dos endereços
* apontados por 'a' e 'b'. Esses endereços são interpretados como 'int'.
*/
void int_swap (void *a, void *b)
{
int *pa = (int *)a;
int *pb = (int *)b;
int aux = *pa;

*pa = *pb;
*pb = aux;
}

/* draw
*
* buffer - buffer a ser impresso
* nmele - numero de elementos em 'buffer'
* size - tamanho de cada element ode 'buffer'
* print - ponteiro para funcao de impressao
*/
void draw (void *buffer, size_t nmele, size_t size,
void (*print)(void *, int))
{
register int i;

system ("clear");

for ( i = 0; i < nmele; i++ )
print ( (buffer + (size*i)), i );
}

/* bubblesort
*
* buffer - buffer a ser ordenado
* nmele - numero de elementos em 'buffer'
* size - tamanho de cada elemento em 'buffer'
* cmp - ponteiro para funcao de comparação
* swap - ponteiro para funcao de troca de elementos
*/
void bubblesort (void *buffer, size_t nmele, size_t size,
int (*cmp)(void *, void *),
void (*swap)(void *, void *))

{
register int i, j;
void *a, *b;

for (i = 0; i < nmele; i++ ) {

draw (buffer, nmele, size, int_print );
sleep (1);

for (j = i; j < nmele; j++) {
a = buffer + (size * i);
b = buffer + (size * j);

if (cmp(a, b) > 0)
swap(a, b);
}
}
}
int main (void)
{
int array[ ARRAY_SIZE ] = {5,7,1,3,2,8,10,6,4,9};

bubblesort ( array, ARRAY_SIZE, sizeof(int), int_cmp, int_swap );

return 0;
}



O código acima faz a animacão com o bubblesort, e coloquei as abstracões que você vai precisar pra implementar a qsort. Dá uma olhada na man page da qsort pra entender a API dela. No "Linguagem C" do K&R tem uma implementacão da qsort que você poderá usar pro seu trabalho.

Tenta aí e posta o resultado!
Qualquer dúvida, pergunta.
[]'s
Enzo Ferber






Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts