Página 1 de 1
QuickSort

Enviado:
18 Dez 2006 11:26
por Jorge_Francisco
Então pessoal ,queria saber se esta forma de organização é a mais aconselhavel para usar em um PIC?A que estou querendo usar é recursiva.Alguem tem esperiencia nesse assunto?O meu objetivo até que é simples,seria organizar 100 numeros, que estão em um vetor, do menor para o maior!
Abraços!!!
Re: QuickSort

Enviado:
18 Dez 2006 11:56
por Jorge_Francisco
PIC aceita função recursiva?Acho que não neh?Então se tiverem um ideia em C,eu agradeço!Ah,um grande detalhe,não posso gastar muito tempo para organizar este vetor!
Abraços!!!

Enviado:
18 Dez 2006 11:56
por KrafT
Talvez essa jóia do antigo fórum te ajude:
http://www.asm51.eng.br/forum/topic.asp?TOPIC_ID=805
PS: Não liga para o meu stress com o Prof Francisco... Isso já tá resolvido a muito tempo...

Enviado:
18 Dez 2006 12:24
por Jorge_Francisco
Ola Kraft,ajudar até ajuda,mas queria algo com melhor desempenho.Não queria só o código,queria entende-lo tb,mas mesmo assim muito obrigado!!
algoritimo de ordenacao

Enviado:
18 Dez 2006 12:30
por Rogerio Brasiliense
Envei para teu email.
Não entendo de PIC, mas acho que usar funcao recursiva vai estourar a pilha.
Re: algoritimo de ordenacao

Enviado:
18 Dez 2006 14:35
por Jorge_Francisco
Rogerio Brasiliense escreveu:Envei para teu email.
Não entendo de PIC, mas acho que usar funcao recursiva vai estourar a pilha.
Não recebi nada ainda!realmente com recursiva não deu!A função que tem no link do asm antigo esta gastando muito tempo!

Enviado:
18 Dez 2006 15:29
por lucaszampar
Boa tarde Prof. Francisco,
Eu já tive que ordenar alguns dados uma vez e implementei o algorítimo da bolha. Comigo ele resolveu. Dê uma olhada:
http://www.cs.princeton.edu/~ah/alg_ani ... eSort.html
http://www.gamedev.net/reference/articl ... cle298.asp
jorge, vou repetir

Enviado:
18 Dez 2006 15:30
por Rogerio Brasiliense
abracos
Deu zebra. Tentei rodar e deu estouro de pilha.
E alterando outra vez. Dos 6 modelos de memoria do C++3.1 deu a mesma mensagem. Isto que eu tenho um Athalon 2200+ e 256 Megas de ram.
Antes eu tinha um P166 com uns 64MEGAS e funcionou.
Não sei se modifiquei muito o programa ou não mais entendo de computador.
Me desculpe se mandei uma droga.

Enviado:
19 Dez 2006 13:01
por chipselect
Faça um algoritmo iterativo de ordenação por árvore (heap sort), com a unificação dos "arquivos" de saída.
Na universidade eu propus uma variação do heap sort em que não era necessário formar dois arquivos de saída, adicionando-se umas poucas variáveis de controle de índice para guardar a posição dos registros das subárvores.
Um grupo de colegas fizeram o algoritmo, funcionou. Infelizmente não tenho o código.
Detalhe.: o Quicksort é mais fácil de ser implementado que o Heap Sort, mas o Heap Sort, no pior, melhor e no caso médio é de ordem nLogn enquanto que o Quick Sort no pior caso é exponencial, igual à ordenação bolha... apesar de no caso médio ser de ordem logarítmica como o Heap Sort.
Logo, na média, o QuickSort em a mesma velocidade que o Heap Sort, mas considerando até os casos raros, o Heap Sort é melhor.
O Heap Sort não é tão difundido quanto o QuickSort pq ele é chato pacas pra ser implementado e os algoritmos necessitavam de 2 stream de saída.

Enviado:
19 Dez 2006 14:37
por Jorge_Francisco
chipselect escreveu:Faça um algoritmo iterativo de ordenação por árvore (heap sort), com a unificação dos "arquivos" de saída.
Na universidade eu propus uma variação do heap sort em que não era necessário formar dois arquivos de saída, adicionando-se umas poucas variáveis de controle de índice para guardar a posição dos registros das subárvores.
Um grupo de colegas fizeram o algoritmo, funcionou. Infelizmente não tenho o código.
Detalhe.: o Quicksort é mais fácil de ser implementado que o Heap Sort, mas o Heap Sort, no pior, melhor e no caso médio é de ordem nLogn enquanto que o Quick Sort no pior caso é exponencial, igual à ordenação bolha... apesar de no caso médio ser de ordem logarítmica como o Heap Sort.
Logo, na média, o QuickSort em a mesma velocidade que o Heap Sort, mas considerando até os casos raros, o Heap Sort é melhor.
O Heap Sort não é tão difundido quanto o QuickSort pq ele é chato pacas pra ser implementado e os algoritmos necessitavam de 2 stream de saída.
Bom, o QuickSort em complexidade de tempo é O(n lg2 n) no melhor caso e no caso médio e O(n2) no pior caso e em complexidade de espaço é O(lg2 n) no melhor caso e no caso médio e O(n) no pior caso.Enquanto o HeapSort no melhor e pior caso é O(n log2n),praticamente constante!!
Existem n tipos de ordenação:
* Bubble sort
* Quick sort
* Merge sort
* Selection sort
* Heapsort
* Insertion sort
* Shell sort
* Radix sort
* Gnome sort
* Count sort
* Bogosort
Vou usar o ShellSort ou HeapSort no pic e testar o desempenho!!!
Um exemplo de HeapSort:
- Código: Selecionar todos
heapsort(tipo a[], int n)
{
int i = n/2, pai, filho;
tipo t;
for (;;)
{
if (i > 0)
{
i--;
t = a[i];
}
else
{
n--;
if (n == 0)
return;
t = a[n];
a[n] = a[0];
}
pai = i;
filho = i*2 + 1;
while (filho < n)
{
if ((filho + 1 < n) && (a[filho + 1] > a[filho]))
filho++;
if (a[filho] > t)
{
a[pai] = a[filho];
pai = filho;
filho = pai*2 + 1;
}
else
break;
}
a[pai] = t;
}
}

Enviado:
19 Dez 2006 15:06
por Ander_sil

Enviado:
19 Dez 2006 15:27
por chipselect
tem esse aqui, dá pra adaptar no pic, não é recursivo:
void maxHeap(int p, int m, int v[])
{
int x = v[p];
while (2*p <= m) {
int f = 2*p;
if (f < m && v[f] < v[f+1]) ++f;
if (x >= v[f]) break;
v[p] = v[f];
p = f;
}
v[p] = x;
}
void heapsort (int n, int v[])
{
int p, m, x;
for (p = n/2; p >= 1; --p)
maxHeap(p, n, v);
for (m = n; m >= 2; --m) {
x = v[1], v[1] = v[m], v[m] = x;
maxHeap(1, m-1, v);
}
}
dá pra implementar o Quicksort de maneira iterativa também, daí dá pra executar no PIC, mas acho que não vale a pena. Pra ter certeza, só fazendo e comparando.
Corrigindo: não foi o heap sort que precisa de 2 arquivos.
Pra quem quiser conhecer bem de algoritmos de ordenação, sugiro o livro "The Art of Computer Programming" volume 3 de Donald E. Knuth, é um clássico.