QuickSort

[Akvoz]

Estou precisando de uma ajuda para por QuickSort no codigo na qual já tem o BubbleSort. no caso seria substituir o metodo BubbleSort por QuickSort

Resumo: é um cadastro de veiculos por Nome, placa, cor,n de portas e combustivel, na qual quando exibir exibe um outro menu na qual pergunta se quer Ordernar por Placa ou por Nome.

#include <stdlib.h>
#include <string.h>

#define MAX 5

typedef enum{
GASOLINA, ALCOOL, FLEX, DIESEL, GAS
}TipoCombustivel;

typedef struct {
char nome[30];
char placa[12];
char cor[30];
int quantidadePortas;
TipoCombustivel tipoCombustivel;
}Carro;

int opcao();
Carro *alocarMemoria();
void incluirCarro(Carro *p[], int *q);
void incluir(Carro *p);
void excluirCarro(Carro *p[], int *q);
int pesquisarCarro(Carro *p[], int *q);
char *converteTipoCombustivel(TipoCombustivel t);
void exibir(Carro *p);
void exibirCarro(Carro *p[], int q);
void alterarCarro(Carro *p[], int q);
void sortnome(Carro *p[], int qtd);
void sortplaca(Carro *p[], int qtd);
void sortBolha(Carro *p[], int i);


int main(){
int op = 0;
int quantidade = 0;
Carro *vet[MAX];

do{
op = opcao();

switch(op){
case 1:
incluirCarro(vet, &quantidade);
break;

case 2:
excluirCarro(vet, &quantidade);
break;

case 3:
alterarCarro(vet, quantidade);
break;

case 4:
exibirCarro(vet, quantidade);
break;
}

}while(op != 5);

getchar();
return 0;
}

Carro *alocarMemoria(){
Carro *p = (Carro*) malloc(sizeof(Carro));

if(!p){
printf("Erro ao alocar memoria...");
exit(1);
}

return p;
}

int opcao(){
int op = 0;

do{
printf("\t\t\tMenu\n\n");
printf("\t\t\t1 - Incluir \n\n");
printf("\t\t\t2 - Excluir \n\n");
printf("\t\t\t3 - Alterar \n\n");
printf("\t\t\t4 - Exibir \n\n");
printf("\t\t\t5 - Sair \n\n");

printf("Opcao: ");
scanf("%d", &op);

}while( op < 1 || op > 5);

return op;
}

void incluirCarro(Carro *p[], int *q){
p [*q] = alocarMemoria();

if(*q < MAX){

incluir(p[*q]);
(*q)++;

}else{
printf("VETOR DE REGISTROS CHEIO.");
}
}

void incluir(Carro *p){
printf("Digite o nome do carro\n");
scanf("%s", p->nome);
printf("Digite a placa do carro\n");
scanf("%s", p->placa);
printf("Digite a cor do carro\n");
scanf("%s", p->cor);
printf("Digite quantidade de portas do carro\n");
scanf("%d", &p->quantidadePortas);
printf("Digite o tipo de combustivel do carro - 0 (Gasolina), 1 (Alcool), 2 (Flex), 3 (Diesel)\n");
scanf("%d", &p->tipoCombustivel);

system("pause");
system("cls");
}

void excluirCarro(Carro *p[], int *q){
int ultima = *q - 1;

int i = pesquisarCarro(p, q);

if(i > -1){
free(p[i]);
p[i] = p[ultima];
p[ultima] = NULL;
(*q)--;
}
}

int pesquisarCarro(Carro *p[], int *q){
char op;
int i;
for(i = 0; i < *q; i++){
exibir(p[i]);
printf("\n\n");
printf("Deseja excluir o carro acima? (S/N) ");
fflush(stdin);
scanf("%c", &op);

if(op == 'S' || op == 's'){
return i;
}
}

return -1;
}

void exibirCarro(Carro *p[], int q){
int i;
int op;
system("cls");
printf("\tOrdenar por:\n\n 1 - Nome\n 2 - Placa\n");
printf("Opcao: ");
scanf("%d", &op);

switch(op){
case 1:

sortnome(p,q);
system("cls");
printf("\tCarros Ordenados por nome:\n\n");
for (i=0; i < q; i++){
exibir(p[i]);
printf("\n");
}
break;

case 2:

sortplaca(p,q);
system("cls");
printf("\tCarros Ordenados por placa:\n\n");
for (i=0; i < q; i++){
exibir(p[i]);
printf("\n");
}
break;
default:
printf ("Opcao invalida");

break;
}
}


void exibir(Carro *p){
printf("Nome do carro: %s\n", p->nome);
printf("Placa do carro: %s\n", p->placa);
printf("Cor do carro: %s\n", p->cor);
printf("Quantidade de portas do carro: %d\n", p->quantidadePortas);
printf("Tipo de combustivel do carro: %s\n", converteTipoCombustivel(p->tipoCombustivel));
system("pause");
}

void alterarCarro(Carro *p[], int q){
int i = pesquisarCarro(p, &q);

if(i > -1){
printf("\nDigite os novos dados para o carro selecionado.\n");
incluir(p[i]);
}
}

char *converteTipoCombustivel(TipoCombustivel t){
switch(t){

case GASOLINA:
return "Gasolina";
break;

case ALCOOL:
return "Alcool";
break;

case FLEX:
return "Flex";
break;

case DIESEL:
return "Diesel";
break;

default:
return "Nao Especificado";
break;
}
}
void sortnome(Carro *p[], int qtd) {
int i;
int compara;
int swap;

do
{
qtd--;
swap=0;
for(i=0; i < qtd; i++)
{
compara=strcoll (strupr(p[i]->nome), strupr(p[i+1]->nome));
if (compara > 0)
{
sortBolha (p, i);
swap = 1;
}


}
}
while(swap);
}
void sortplaca(Carro *p[], int qtd) {
int i;
int compara;
int swap;

do
{
qtd--;
swap=0;
for(i=0; i < qtd; i++)
{
compara=strcoll(strupr (p[i]->placa), strupr (p[i+1]->placa));
if (compara > 0)
{
sortBolha (p, i);
swap = 1;
}

}
}

while (swap);
}
void sortBolha(Carro *p[], int i)
{
int aux;
aux = 0;
aux =(int) p[i];
p[i] = p[i+1];
p[i+1] = (Carro*)aux;
}

#include <stdio.h>

por favor preciso com urgencia.

Obrigado

[JoãoApenas]

cara, você sabe ou não como implementar o quicksort?

[Akvoz]

Cara, sei mais ou menos. Estou fazendo com muita pressa n sei de eu to fazendo corretamente. Tentei fazer por base no Bubble sort q eu fiz para aproveitar algumas coisas

[JoãoApenas]

Seguinte, o ideal é que você crie duas funções uma pra particionar o vetor, e outra para organizá-lo efetivamente. Eu acho que você precisa criar uma variavel para contar a quantidade de carros atuais no teu vetor dinâmico. Digamos que essa variavel se chame, ncarro.

você precisa criar a variavel 'ncar' quem seja um contador do numero de carros.

E falar que o inteiro 'ultimo' deve receber 'ncar'.

==================================================================================

void divide (Carro c[], int primeiro, int ultimo) {

int a, b;

a = primeiro;

for (b = primeiro + 1; b <= ultimo; b++) { // andar por todo o vetor

if (c < c[primeiro]) {

b++;

troca(c[primeiro], c; // essa função você já tem pronta

}

}

troca(c[primeiro], c[a]);

return a;

}

==================================================================================

void QuickSort (Carro c[], int primeiro, int ultimo) {

int meio;

if(ultimo > primeiro) {

meio = divide (c, primeiro, ultimo);

QuickSort(c, primeiro, meio);

QuickSort(c, meio + 1, ultimo);

}

}

acho que essa lógica deve dar certo!