sábado, 27 de outubro de 2007

Quicksort PHP - Ordenando itens

Pessoal, ta aí um código muito interessante em PHP que
acredito que muitos conhecem, mas como eu não conhecia,
acho que vale compartilhar.
Basicamente o código ordena um array usando recursividade, método chamado Quicksort.
O link para maiores explicações é este: http://pt.wikipedia.org/wiki/Quicksort

//troca elementos
function troca($v1, $v2){
   $vaux = $v1;
   $v1 = $v2;
   $v2 = $vaux;
}
//divide o array em dois
function divide($vet=array(), $ini, $fim){
   $i = $ini;
   $j = $fim;
   $dir = 1;
   while ($i > $j){
      if ($vet[$i] > $vet[$j]){
      troca($vet[$i], $vet[$j]);
      $dir = - $dir;
      }
      if ($dir == 1) {
      $j--;
      }else{
      $i++;
      }
      return $i;
   }
}
//ordena
function quicksort($vet=array(), $ini, $fim){
   if ($ini < $fim){
   $k = divide($vet, $ini, $fim);
   quicksort($vet, $ini, $k-1);
   quicksort($vet, $k+1, $fim);
   }
}
quicksort($vet,0,count($vet));

4 comentários:

Anônimo disse...

http://br.php.net/ksort

Daniel Ribeiro disse...

kkkkkkkk.....ta certo...negocio é mais por curiosidade, para mostrar o método em php e em outras linguagens, principalmente a ruby que detruiu tudo em algumas linhas rss..!
E se for o guidão mór que postou isso , quero lembrá-lo que...ksort() é coisa pronta cara...rsssss!!!!

Danniel disse...

Se o vetor tiver 5 posições...
Você chama quiksort com
$ini = 0;
$fim = 5;
Como $i e $j recebem os valor de $ini e $fim, a linha

while ($i > $j)

nunca vai ser executada. Ou seja, esse código não faz nada :P

Anônimo disse...

errado Danniel, a função é recursiva! Procure por quick sort e você vai ver que ela funciona sim! Belo post!