probleamas com quicksort

haseo
(usa Suse)

Enviado em 05/12/2007 - 12:13h

boa tarde estou com um problema grave em c
tenho que usaar um quicksort nos seguintes numeros : 32-40-15-6-10-95-13-21-33-50

tenho que usar pivot central e deixar em ordem crecente ! porem o meu pivot central e uma pessima escolha que no caaso seria o 10 !
como eu faço isso eu posso trocar o pivot central durante o decorrer do codigo?

hbobenicio
(usa Ubuntu)

Enviado em 22/02/2008 - 23:01h

bem, se isso não for um trabalho de faculdade, se não precisar realmente implementar o quicksort, você pode usar o quicksort da stdlib.h
mais fácil e prático :)
(embora estudar o algoritmo do quicksort seja importantíssimo)

ex.:

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

int compara(const void* a, const void *b) {
int *x = (int*) a;
int *y = (int*) b;
if(*x > *y) return 1;
if(*x < *y) return -1;
return 0;
}

int main()
{
int lista[] = { 32, 40, 15, 6, 10, 95, 13, 21, 33, 50 };
int i;

qsort(lista, 10, sizeof(int), compara);

for(i=0; i<10; i++)
printf("%d ", lista[i]);

printf("\n");
return(0);
}

obs.: o segundo parâmetro da função qsort é o número de elementos do vetor.

f_Candido
(usa Ubuntu)

Enviado em 22/02/2008 - 23:15h

A solução apresentada acima é interessante. Mas vale lembrar que o algoritmo QuickSort da stdlib.h, é genérico. Desta forma, desenvolver a QuickSort no Braço haverá um ganho em velocidade.

Espero ter ajudado

Abraços

hbobenicio
(usa Ubuntu)

Enviado em 25/02/2008 - 02:17h

Cara, num sei não, viu.
Esse qsort da stdlib pode ser genérico, mas acho que qualquer implementação que nós consigamos fazer, não conseguirá ser mais rápido que essa da stdlib. Essa função é genérica, mas quase não há perda de desempenho quanto a isso, já que a implementação dela deve ser BEM otimizada (não duvido se tiver código assembly internamente)... a manipulação de bytes deve ser bem baixo nível.

Bem... viva o mundo de opções! Façam suas escolhas! :)

hbobenicio
(usa Ubuntu)

Enviado em 25/02/2008 - 02:29h

Bem... aproveitando a deixa, deixo aqui o quicksort em c++ (usando o 'vector' e o 'sort' da STL)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
vector<int> lista;
int i;

for(i=10; i>=1; i--)
lista.push_back(i);

for(i=0; i<lista.size(); i++)
printf("%d ", lista.at(i));
printf("\n");

sort( lista.begin(), lista.end() );

for(i=0; i<lista.size(); i++)
printf("%d ", lista.at(i));
printf("\n");

return(0);
}

espero que tenha sido útil! :)