PHP: Алгоритм сортировка выбором

Сортировка массива с помощью алгоритма «Сортировка выбором».

В каждой итерации минимальное значение массива извлекается и добавляется в новый массив.

Сложность: O(n log n)



function findMin( $list )
{
	$minIndex = 0;
	$min = $list[ $minIndex ];
	$size = sizeof( $list );
	for( $i = 1; $i < $size; $i++ )
	{
		if( $list[ $i ] < $min )
		{
			$minIndex = $i;
			$min = $list[ $minIndex ];			
		}
	}
	return $minIndex;	
}

function selectionSort( $list )
{
	$result = [];
	foreach( $list as $val )
	{
		$minIndex = findMin( $list );
		array_push( $result, $list[ $minIndex ] );
		array_splice( $list, $minIndex, 1 );		
	}
	return $result;	
}

$sampleList = [ 23, 42, 8, 4, 15, 16 ];

echo '<pre>', var_dump( findMin( $sampleList ) ) ,'</pre>';
// > 3

echo '<pre>', var_dump( selectionSort( $sampleList ) ) ,'</pre>';
// > array(6) {
// >   [0]=>
// >   int(4)
// >   [1]=>
// >   int(8)
// >   [2]=>
// >   int(15)
// >   [3]=>
// >   int(16)
// >   [4]=>
// >   int(23)
// >   [5]=>
// >   int(42)
// > }


PHP Алгоритм up: просмотров: 78