С++,PHP.

[nvse]

Здравствуйте , не совсем понимаю почему не работает следующий кусок кода
( на С этот алгоритм работает верно , на PHP почему-то нет) .

на С

void swap( int &i , int &j) 
{
 int temp = i ;
 i = j;
 j = temp ;
}
 
void quick_sort(int * ar,int left,int right) 
{
int i , j ;
i = left ; j = right ;
int m = (i + j)/2 ;
while ( ( (i <= m) && (j >= m) ) && ( (i != m) || (j != m) ) )
{
i += (( ar[i] <= ar[m] ) && ( i != m ) ) ? 1:0 ; 
j -= (( ar[j] >= ar[m] ) && ( j != m ) ) ? 1:0 ;

if ( ( ar[i] >= ar[m] ) && ( ar[j] <= ar[m] ) && 
     ( ar[i] != ar[j] ) && ((i != m) || (j != m)))
{
	swap(ar[i],ar[j] ) ;
	if ( ( i != m ) && ( j != m) )  
	{ i++ ;
	  j-- ; }
	else if ( i == m )  
	{ m = j ; i++ ;}
	 else 
	{ m = i ; j-- ; }
}
}
if ((right - left ) > 1)
{
if ( m != left ) quick_sort( ar , left , m-1 );
if ( m != right ) quick_sort( ar , m+1, right );
}
}

на PHP

function swap(&$i,&$j) 
{ 
$temp = $i ;
$i = $j;
$j = $temp ;
}

function quick_sort(&$ar,$left,$right) // быстрая сортировка
{
$i = $left ; $j = $right ;
$m = ($i + $j)/2 ;
while ( ( ($i <= $m) && ($j >= $m) ) && ( ($i != $m) || ($j != $m) ) )
{
$i += (( $ar[$i] <= $ar[$m] ) && ( $i != $m ) ) ? 1:0 ; 
$j -= (( $ar[$j] >= $ar[$m] ) && ( $j != $m ) ) ? 1:0 ;

if ( ( $ar[$i] >= $ar[$m] ) && ( $ar[$j] <= $ar[$m] ) && 
   ( $ar[$i] != $ar[$j] ) && (($i != $m) || ($j != $m)))
{
	swap($ar[$i],$ar[$j] ) ;
	if ( ( $i != $m ) && ( $j != $m) )  
	{ $i++ ;
	  $j-- ; }
	else if ( $i == $m )  
	{ $m = $j ; $i++ ;}
	else 
	{ $m = $i ; $j-- ;}
}
}
if (($right - $left ) > 1)
{
if ( $m != $left ) quick_sort( $ar , $left , $m-1 );
if ( $m != $right ) quick_sort( $ar , $m+1, $right );
}
}

Заранее спасибо.

@темы: C++, PHP

Comments

[O]

Первое, что бросается в глаза:

$m = ($i + $j)/2 ;

если $i + $j - нечётное число, то $m будет float'ом, а вовсе не int'ом как в сях. И соответственно:
1) ($i != $m), ($j!=$m), ( $m != $left ), ( $m != $right ) в этом случае будет true для любых целочисленных $i, $m, $left и $right;
2) Во время рекурсии будет идти накопление ошибки в $m.

Попытайтесь заменить на

$m = floor(($i + $j)/2) ;

или

$m = ($i + $j)>>1 ;

[nvse]

Точно , всё дело было в этом , спасибо . Последний вопрос задам , если можно :
Реально самому написать сортировку на PHP , чтобы она быстрее работала , чем стандратные функции типа sort ?
А то я просто время засёк и сравнил , так оказалось что моя собcnвенная сортировка уступает стандартной , и это
при условии что,она вроде бы как работает за O(n*logn) ))

[O]

nvse

Реально самому написать сортировку на PHP , чтобы она быстрее работала , чем стандратные функции типа sort ?

Я очень сильно сомневаюсь в этом. Как я понимаю, нативные функции php являются составной частью Zend Engine, написаны на C и исполняются процессором напрямую. Написанные же на php функции переводятся в байткод виртуальной машины Zend Engine II, который уже потом исполняется самой виртуальной машиной. А это значит, что каждый раз, например, встречая переменную, Zend Engine должен её найти в памяти, проверить её тип и при необходимости привести его к нужному, определить, допустима ли данная операция для данного типа и т.д. и т.п.

[Тигр]

nvse, php использует алгоритм qsort на уровне C. Если хочется поднять скорость - имеет смысл написать свое расширение для пыха на C, которое будет использовать более быстрый алгоритм.