Estrutura de ordenação Quicksort [RESOLVIDO]

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;

} 

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