QuickSort

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

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

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

[Jorge_Francisco]

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

[Rogerio Brasiliense]

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

[Jorge_Francisco]

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!

[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

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

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

[Jorge_Francisco]

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



[Ander_sil]

http://www.ime.usp.br/~pf/algoritmos/aulas/ordena.html

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