Quick Sort in Place

Programação Java
#1

Pessoal,

Alguem por favor poderia me dar uma dica de como implementar o algoritmo acima em java,já consigui o “quick sort” simples mas não consigo fazer o “quick sort in place”…

Valeu,

#2

Ninguem pode me ajudar?

#3

Eu nunca ouvi falar de Quick Sort In Place… qm sabe se vc explicar dá pra ajudar :grin:

#4

Ae humberto, tbm nunca ouvi falar desse algoritmo nao… o alg mais foda q o quick q eu conheco eh o HeapSort, e jah eh complicado pacas…

explica ai o algoritmo q a gente tenta codifica-lo

#5

heapSort :eek:

eita

posta ai o q q é o heapSort que eu tb não conheço isso

#6

[quote=“darkseid”]Ae humberto, tbm nunca ouvi falar desse algoritmo nao… o alg mais foda q o quick q eu conheco eh o HeapSort, e jah eh complicado pacas…

explica ai o algoritmo q a gente tenta codifica-lo[/quote]

O " Quick normal" pode crescer o uso da memoria indefinidamente ,dependendo da complexidade demonstrada na ordenação da forma como os elementos estão arranjados…já o “in place” ,como o nome já diz,dá uma restrição de uso de espaço na memoria onde pode-se efetuar a ordenação…Não estou conseguindo exatamente fazer essa restrição …

Talvez …em muitos cursos …o professor dá o algoritmo “in place” como se fosse o “quick normal”…pura confusão!!! se alguem tiver a implementação do Quick eu posso dar uma olhada… se posso converte-lo pra aquilo que eu não estou conseguindo fazer no “in place”…

#7

em java, quick sort é assim

public void quick(int inicio, int fim)

{
  int antes = inicio;
  int depois = fim;
  int mediana = vetor[(inicio+fim) div 2];
  int aux;
  do
  /* repete at? que troques os elementos maiores pelos menores */
    while (vetor[antes] < mediana) antes++;
    while vetor[depois] > mediana depois--;
    if (depois >= antes) /* se o depois tem um elemento que ? menor que a mediana
    e o antes tem um que e maior */
      {
        //troca as posições
        aux = vetor[antes];
        vetor[antes] = vetor[depois];
        vetor[depois] = aux;
        depois--;
        antes++;
      }
  while (antes <= depois);
  if (depois > inicio) 

    quick(inicio, depois);

  if  (antes < fim) 
  quick(antes, fim);
}
#8

O Quick Sort q eu conheço é esse ae que o microfilo colocou…

E quando vc fala de memoria… crescer em relação a recursividade?? nao entendi isso nao

#9