Ir para o conteúdo
polska

php quick sort function error

Mensagens Recomendadas

polska

Boas pessoal, tinha que fazer um exercício na aula que consistia em criar um array de 10 elementos com números escolhidos por nós e depois imprimir o tamanho e a inversão do array, usando as funções adequadas.. Como último ponto tínhamos que ordenar o array e imprimir.. Achei engraçado tentar implementar o quick sort em php, mas surgiu um erro ao correr o ficheiro php -> Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 64 bytes) in C:\xampp\htdocs\php\ex1.php on line 22 .. A função para reverter o array também não funcionou...

Alguém me pode dar uma ajuda?

<?php

function quick_sort($arr, $first, $last)
{
	$esq = $first;
	$dir = $last;
	$aux;
	$middle = $arr[$esq + $dir] / 2;
	$middle = floor($middle);

	#swaps
	while($esq <= $dir)
	{
		while($arr[$esq] < $middle)
			$esq++;
		while($arr[$dir] > $middle)
			$dir--;

		if($esq <= $dir)
		{
			$aux = $arr[$esq];
			$arr[$esq] = $arr[$dir];
			$arr[$dir] = $aux;
			$esq++; $dir--;	
		}
	}

	#recursividade
	if($esq > $first)
		quick_sort($arr, $first, $esq);
	if($dir < $last)
		quick_sort($arr, $dir, $last);

}

$nums = array(4,6,7,8,9,1,2,3,4,8);

#length
echo sizeof($nums);
echo "<br />";

#reverse
array_reverse($nums);
foreach($nums as $valor)
	echo $valor ." ";
echo "<br />";

#ordered
quick_sort($nums, 0, 9);
foreach($nums as $valor)
	echo $valor ." ";
echo "<br />";

?>


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Se estás a trabalhar localmente, podes aumentar a memória disponível do PHP no php.ini

memory_limit = 128M;

o problema não pode ser de falta de memória, só pode ser mesmo de má implementação do algoritmo.

@Polska : eu não dei uma vista de olhos muito aprofundada ao teu algoritmo mas algo saltou logo à vista de como está errado:

function quick_sort($arr, $first, $last)
{
 // ...

 while($esq <= $dir) // este ciclo só para quando $esq for maior que $dir
 {
   // ...
 }

 if($esq > $first)
   quick_sort($arr, $first, $esq); // estás a chamar o quick sort de 0 a $esq ($esq > $dir)

 if($dir < $last)
  quick_sort($arr, $dir, $last); // estás a chamar o quick sort de $dir a $size ($dir < $esq)
}

// tens isto

0-------$dir-$esq-------$size

por outras palavras, os subarrays que estás a ordenar na recursividade não são exclusivos, existem elementos em comum.


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
polska

Utilizei o ini_set para resolver, se for o caso, o problema de memória, e já corrigi o código, mas agora tenho sempre o erro: Notice: Undefined offset: -1 in C:\xampp\htdocs\php\ex1.php on line 17 , continuamente...

<?php

   ini_set('memory_limit', '128M');

   function quick_sort($arr, $first, $last)
   {
       $esq = $first;
       $dir = $last;
       $aux;
       $middle = floor($arr[$esq + $dir] / 2);

       #swaps
       while($esq <= $dir)
       {
           while($arr[$esq] < $middle)
               $esq++;
           while($arr[$dir] > $middle)
               $dir--;

           if($esq <= $dir)
           {
               $aux = $arr[$esq];
               $arr[$esq] = $arr[$dir];
               $arr[$dir] = $aux;
               $esq++; $dir--;    
           }
       }

       #recursividade
       if($dir > $first)
           quick_sort($arr, $first, $dir);
       if($esq < $last)
           quick_sort($arr, $esq, $last);

       foreach($nums as $valor)
           echo $valor ." ";
       echo "<br />";

   }

   $nums = array(4,6,7,8,9,1,2,3,4,8);

   #length
   echo sizeof($nums);
   echo "<br />";

   #reverse
   array_reverse($nums);
   foreach($nums as $valor)
       echo $valor ." ";
   echo "<br />";

   #ordered
   quick_sort($nums, 0, 9);

?>

Editado por polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo
/**
* Função que implementa o quick sort sobre um array de elementos.
*
* @param $array   referência ao array a ser ordenado
* @param $left    índice inferior do array/subarray a ser ordenado
* @param $right   índice superior do array/subarray a ser ordenado
* @param $ordfunc função opcional usada para comparar os elementos do array
*/
function quick_sort(&$array, $left, $right, $ordfunc = null)
{
/* ignorar ordenações de arrays com menor de 2 elementos */
if ($right - $left < 1)
	return;

/* escolher o pivot : o último elemento */
$pivot = $array[$right];

/* inicialização do índice dos elementos menores que o pivot, este valor
 * representa o índice do próximo valor a ser inserido na lista de menores
 * que o pivot */
$store = $left;

/* ciclo de verificação do valor dos elemento do array/subarray em relação
 * ao pivot */
for ($i = $left; $i < $right; $i++) {
	/* verificação de:
	 * - se o parâmetro 'ordfunc' é uma função e o resultado desta for menor
	 *   que zero
	 * - ou se não for uma função, mas na comparação directa dos valores se
	 *   verificar que o elemento iterado é menor que o valor do pivot */
	if ((is_callable($ordfunc) && $ordfunc($array[$i], $pivot) < 0) ||
	     !is_callable($ordfunc) && $array[$i] < $pivot) {
		/* mover o elemento iterado para a lista de elementos menores
		 * (para a posição apontada pela variável $store) */
		$aux = $array[$i];
		$array[$i] = $array[$store];
		$array[$store] = $aux;

		/* incrementar o índice do próximo elemento a ser inserido na lista
		 * de valores menores que o pivot */
		$store++;
	}
}

/* colocar o pivot na sua posição, entre a lista de menores e a lista de
 * maiores, isto equivale ao valor do índice do próximo valor a ser inserido
 * na lsita de menores valores que o pivot */
$aux = $array[$right];
$array[$right] = $array[$store];
$array[$store] = $aux;

/* chamada recursiva da sub-lista antes da posição do pivot e da sub-list
 * pós a posição pivot, tanto uma como outra exclusivé */
quick_sort($array, $left, $store - 1, $ordfunc);
quick_sort($array, $store + 1, $right, $ordfunc);

return;
}

/* lista de valores a serem ordenados */
$nums = array(4,6,7,8,9,1,2,3,4,8);

/* chamada da função de ordenação usando a ordem natural dos valores guardados
* no array passado como parâmetro da função */
quick_sort($nums,
          0,
          count($nums) - 1);
print_r($nums);

/* chamada da função de ordenação usando uma função de comparação entre os
* elementos a serem ordenados */
quick_sort($nums,
          0,
          count($nums) - 1,
          function ($a, $b) {
              return($b - $a); // menor que zero só se $a for menor que $b (ordem inversa)
          });
print_r($nums);


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

/**
* Função que implementa o quick sort sobre um array de elementos.
*
* @param $array   referência ao array a ser ordenado
* @param $left    índice inferior do array/subarray a ser ordenado
* @param $right   índice superior do array/subarray a ser ordenado
* @param $ordfunc função opcional usada para comparar os elementos do array
*/
function quick_sort(&$array, $left, $right, $ordfunc = null)
{
   /* ignorar ordenações de arrays com menor de 2 elementos */
   if ($right - $left < 1)
       return;

   /* escolher o pivot : o último elemento */
   $pivot = $array[$right];

   /* inicialização do índice dos elementos menores que o pivot, este valor
    * representa o índice do próximo valor a ser inserido na lista de menores
    * que o pivot */
   $store = $left;

   /* ciclo de verificação do valor dos elemento do array/subarray em relação
    * ao pivot */
   for ($i = $left; $i < $right; $i++) {
       /* verificação de:
        * - se o parâmetro 'ordfunc' é uma função e o resultado desta for menor
        *   que zero
        * - ou se não for uma função, mas na comparação directa dos valores se
        *   verificar que o elemento iterado é menor que o valor do pivot */
       if ((is_callable($ordfunc) && $ordfunc($array[$i], $pivot) < 0) ||
            !is_callable($ordfunc) && $array[$i] < $pivot) {
           /* mover o elemento iterado para a lista de elementos menores
            * (para a posição apontada pela variável $store) */
           $aux = $array[$i];
           $array[$i] = $array[$store];
           $array[$store] = $aux;

           /* incrementar o índice do próximo elemento a ser inserido na lista
            * de valores menores que o pivot */
           $store++;
       }
   }

   /* colocar o pivot na sua posição, entre a lista de menores e a lista de
    * maiores, isto equivale ao valor do índice do próximo valor a ser inserido
    * na lsita de menores valores que o pivot */
   $aux = $array[$right];
   $array[$right] = $array[$store];
   $array[$store] = $aux;

   /* chamada recursiva da sub-lista antes da posição do pivot e da sub-list
    * pós a posição pivot, tanto uma como outra exclusivé */
   quick_sort($array, $left, $store - 1, $ordfunc);
   quick_sort($array, $store + 1, $right, $ordfunc);

   return;
}

/* lista de valores a serem ordenados */
$nums = array(4,6,7,8,9,1,2,3,4,8);

/* chamada da função de ordenação usando a ordem natural dos valores guardados
* no array passado como parâmetro da função */
quick_sort($nums,
          0,
          count($nums) - 1);
print_r($nums);

/* chamada da função de ordenação usando uma função de comparação entre os
* elementos a serem ordenados */
quick_sort($nums,
          0,
          count($nums) - 1,
          function ($a, $b) {
              return($b - $a); // menor que zero só se $a for menor que $b (ordem inversa)
          });
print_r($nums);

Offtopic:

Podes aproveitar para colocar o algoritmo no wiki (por exemplo, aqui) :)

(Eu também o podia colocar, mas acho que faz mais sentido ser o autor a colocá-lo.)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
polska

Utilizei o ini_set para resolver, se for o caso, o problema de memória, e já corrigi o código, mas agora tenho sempre o erro: Notice: Undefined offset: -1 in C:\xampp\htdocs\php\ex1.php on line 17 , continuamente...

<?php

ini_set('memory_limit', '128M');

function quick_sort($arr, $first, $last)
{
	$esq = $first;
	$dir = $last;
	$aux;
	$middle = floor($arr[$esq + $dir] / 2);

	#swaps
	while($esq <= $dir)
	{
		while($arr[$esq] < $middle)
			$esq++;
		while($arr[$dir] > $middle)
			$dir--;

		if($esq <= $dir)
		{
			$aux = $arr[$esq];
			$arr[$esq] = $arr[$dir];
			$arr[$dir] = $aux;
			$esq++; $dir--;	
		}
	}

	#recursividade
	if($dir > $first)
		quick_sort($arr, $first, $dir);
	if($esq < $last)
		quick_sort($arr, $esq, $last);

	foreach($nums as $valor)
		echo $valor ." ";
	echo "<br />";

}

$nums = array(4,6,7,8,9,1,2,3,4,8);

#length
echo sizeof($nums);
echo "<br />";

#reverse
array_reverse($nums);
foreach($nums as $valor)
	echo $valor ." ";
echo "<br />";

#ordered
quick_sort($nums, 0, 9);

?>

Obrigado @Happy, só uma coisa, porque é que está a ordenar inversamente? é por causa da função de ordenação?


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Offtopic:

Podes aproveitar para colocar o algoritmo no wiki (por exemplo, aqui) :)

(Eu também o podia colocar, mas acho que faz mais sentido ser o autor a colocá-lo.)

feito com algumas alterações ao nível da validação de parâmetros de entrada da função

Obrigado @Happy, só uma coisa, porque é que está a ordenar inversamente? é por causa da função de ordenação?

eu apresentei dois casos, um a usar a ordenação natural dos elementos (neste caso inteiros) e um segundo a usar uma função de comparação, que por acaso serve para efectuar a ordem inversa


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pikax

Aqui vai outro codigo para fazer isso :)

Nao tenho as validacoes da callback.

function swapp(&$arr,$num1,$num2)
  {
    $aux = $arr[$num1];
   $arr[$num1] = $arr[$num2];
   $arr[$num2] = $aux;
  }

  function Comparar($num1,$num2)
  {
       return $num1>$num2?1:-1;
  }

  function CompararInvertido($num1,$num2)
  {
       return $num1<$num2?1:-1;
  }
   function quick_sort(&$arr, $first, $last,$comparer)
   {
       if($first>$last)
           return;

       if($first<0)
           return;

       $esq = $first;
       $dir = $last+1;
       $current = $arr[$first];

       $done = false;
       while(!$done)
       {
           while(++$esq<=$last && call_user_func($comparer, $arr[$esq],$current)<0)
               ;
           while(call_user_func($comparer, $arr[--$dir] , $current )>0)
               ;
           if($esq<$dir)
               swapp($arr,$esq,$dir);
           else
               $done=true;    
       }

       swapp($arr,$first,$dir);
       quick_sort($arr,$first,$dir-1,$comparer);
       quick_sort($arr,$dir+1,$last,$comparer);
   }

   $nums = array(4,6,7,8,9,1,2,3,4,8);

   #length
   echo sizeof($nums);
   echo "<br />";

   #reverse
   array_reverse($nums);
   foreach($nums as $valor)
           echo $valor ." ";
   echo "<br />";

   #ordered
   quick_sort($nums, 0, 9,"Comparar");
   foreach($nums as $valor)
           echo $valor ." ";
   echo "<br />";

   #reverse order
   quick_sort($nums, 0, 9,"CompararInvertido");
   foreach($nums as $valor)
           echo $valor ." ";
   echo "<br />";

Editado por pikax

Por muito mais que que estude só aprendo uma coisa, que ainda tenho muita coisa para aprender.

A beleza de um código está em decompor problemas complexos em pequenos blocos simples.

"learn how to do it manually first, then use the wizzy tool to save time."

"Kill the baby, don't be afraid of starting all over again. Fail soon, learn fast."

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.