ASM51

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!!!

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!!!

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...

KrafT escreveu: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...

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!!

Envei para teu email.
Não entendo de PIC, mas acho que usar funcao recursiva vai estourar a pilha.

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!

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

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.

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.

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;
   }
}



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.