Этот скрипт можно использовать для сортировки значений, используя алгоритм SmoothSort.
Он принимает массив значений и сортирует значения в порядке возрастания.
Скрипт может также применить функцию обратного вызова для сравнения двух значений для сортировки, поэтому он может сортировать значения любого типа.
Лицензия BSD.
Системные требования скрипта:
PHP не младше 5.0 версии.
Исходник скрипта
//////////////////////////////////////////////////////////
// API__MODULE_SMOOTHSORT (INTERFACE)
// CLS__MODULE_SMOOTHSORT (CLASS)
//////////////////////////////////////////////////////////
interface api__module_smoothsort
{
public static function smoothsort_run( &$array_data, $callback_comparator = 'cls__module_smoothsort::smoothsort_comparator_integer_ascending', $integer_offset_begin = null, $integer_offset_end = null );
public static function smoothsort_comparator_integer_ascending( $integer_value_base, $integer_value_test );
public static function smoothsort_comparator_integer_descending( $integer_value_base, $integer_value_test );
public static function smoothsort_comparator_string_ascending( $string_value_base, $string_value_test );
public static function smoothsort_comparator_string_descending( $string_value_base, $string_value_test );
}
class cls__module_smoothsort implements api__module_smoothsort
{
// 32 Bit Implementation
// Leonardo-Numbers-Count = 46 -> Fits into 32Bit
private static $smoothsort_array_leonardo_numbers =
array('1', '1', '3', '5', '9', '15', '25', '41', '67', '109', '177', '287', '465', '753',
'1219', '1973', '3193', '5167', '8361', '13529', '21891', '35421', '57313', '92735',
'150049', '242785', '392835', '635621', '1028457', '1664079', '2692537',
'4356617', '7049155', '11405773', '18454929', '29860703', '48315633', '78176337',
'126491971', '204668309', '331160281', '535828591', '866988873', '1402817465',
'2269806339', '3672623805'
);
private static $smoothsort_reference_data = null;
private static $smoothsort_callback_comparator = 'cls__module_smoothsort::smoothsort_comparator_integer_ascending';
//////////////////////////////////////////////////////////
public static function smoothsort_run( &$array_data, $callback_comparator = 'cls__module_smoothsort::smoothsort_comparator_integer_ascending', $integer_offset_begin = null, $integer_offset_end = null )
{
// Do SmoothSort on Data-Array
self::$smoothsort_reference_data = &$array_data;
self::$smoothsort_callback_comparator = $callback_comparator;
if( $integer_offset_begin === null ) $integer_offset_begin = 0;
if( $integer_offset_end === null ) $integer_offset_end = count($array_data);
if( $integer_offset_begin == $integer_offset_end || $integer_offset_begin +1 == $integer_offset_end ) return;
$integer_heap_index = 0;
for( $integer_heap_root = $integer_offset_begin; $integer_heap_root != $integer_offset_end; ++$integer_heap_root ) {
self::smoothsort_heap_add( $integer_offset_begin, $integer_heap_root, self::$smoothsort_array_leonardo_numbers, $integer_heap_index );
}
for( $integer_heap_root = $integer_offset_end; $integer_heap_root != $integer_offset_begin; --$integer_heap_root ) {
self::smoothsort_heap_remove( $integer_offset_begin, $integer_heap_root, self::$smoothsort_array_leonardo_numbers, $integer_heap_index );
}
}
//////////////////////////////////////////////////////////
private static function smoothsort_heap_remove( $integer_index_begin, $integer_index_end, $array_heap_list, &$integer_heap_index ) {
// Remove Item from Leonardo-Heap
// FIX: PHP E_NOTICE - ArrayOffset -> !Isset
if( !isset($array_heap_list[$integer_heap_index-1]) || $array_heap_list[$integer_heap_index-1] <= 1 ) {
--$integer_heap_index;
return;
}
$integer_heap_order = $array_heap_list[$integer_heap_index-1];
$array_heap_list[$integer_heap_index] = $integer_heap_order -2;
$array_heap_list[$integer_heap_index-1] = $integer_heap_order -1;
++$integer_heap_index;
$integer_index_left = self::smoothsort_child_first( $integer_index_end -1, $integer_heap_order );
$integer_index_right = self::smoothsort_child_second( $integer_index_end -1 );
self::smoothsort_heap_rectify( $integer_index_begin, $integer_index_left +1, $array_heap_list, $integer_heap_index -1 );
self::smoothsort_heap_rectify( $integer_index_begin, $integer_index_right +1, $array_heap_list, $integer_heap_index );
}
private static function smoothsort_heap_add( $integer_index_begin, $integer_index_end, $array_heap_list, &$integer_heap_index ) {
// Add Item to Leonardo-Heap
if( ($integer_heap_index >= 2) && (($array_heap_list[$integer_heap_index-1] +1) == $array_heap_list[$integer_heap_index-2] ) ) {
--$integer_heap_index;
++$array_heap_list[$integer_heap_index-1];
} else if( ($integer_heap_index >= 1) && ($array_heap_list[$integer_heap_index-1] == 1) ) {
$array_heap_list[$integer_heap_index] = 0;
++$integer_heap_index;
} else {
$array_heap_list[$integer_heap_index] = 1;
++$integer_heap_index;
}
self::smoothsort_heap_rectify( $integer_index_begin, $integer_index_end +1, $array_heap_list, $integer_heap_index );
}
private static function smoothsort_heap_rectify( $integer_index_begin, $integer_index_end, $array_heap_list, $integer_heap_index ) {
// Rectify Leonardo-Heap
$integer_heap_root = $integer_index_end -1;
$integer_heap_current = $integer_heap_index -1;
while( $integer_heap_current > 0 ) {
$integer_heap_compare = $integer_heap_root;
if( $array_heap_list[$integer_heap_current] > 1 ) {
$integer_index_larger = self::smoothsort_child_larger( $integer_heap_root, $array_heap_list[$integer_heap_current] );
if( self::smoothsort_compare( $integer_heap_compare, $integer_index_larger ) ) {
$integer_heap_compare = $integer_index_larger;
}
}
// FIX: PHP E_NOTICE - ArrayOffset -> !Isset
if( !isset( self::$smoothsort_array_leonardo_numbers[$array_heap_list[$integer_heap_current]] )) $integer_heap_prior = -1; else
$integer_heap_prior = $integer_heap_root - self::$smoothsort_array_leonardo_numbers[$array_heap_list[$integer_heap_current]];
if( !self::smoothsort_compare( $integer_heap_compare, $integer_heap_prior ) ) {
break;
}
self::smoothsort_swap( $integer_heap_root, $integer_heap_prior );
$integer_heap_root = $integer_heap_prior;
--$integer_heap_current;
}
self::smoothsort_heap_balance( $integer_heap_root, $array_heap_list[$integer_heap_current] );
}
private static function smoothsort_heap_balance( $integer_index_root, $integer_size ) {
// Balance Leonardo-Heap
while( $integer_size > 1 ) {
$integer_index_first = self::smoothsort_child_first( $integer_index_root, $integer_size );
$integer_index_second = self::smoothsort_child_second( $integer_index_root );
if( self::smoothsort_compare( $integer_index_first, $integer_index_second ) ) {
$integer_index_larger = $integer_index_second;
$integer_size_child = $integer_size -2;
} else {
$integer_index_larger = $integer_index_first;
$integer_size_child = $integer_size -1;
}
if( !self::smoothsort_compare( $integer_index_root, $integer_index_larger ) ) return;
self::smoothsort_swap( $integer_index_root, $integer_index_larger );
$integer_index_root = $integer_index_larger;
$integer_size = $integer_size_child;
}
}
//////////////////////////////////////////////////////////
private static function smoothsort_child_larger( $integer_index_root, $integer_size ) {
// Calculate order
return ( self::smoothsort_compare(
$integer_index_first = self::smoothsort_child_first( $integer_index_root, $integer_size ),
$integer_index_second = self::smoothsort_child_second( $integer_index_root )
)?$integer_index_second:$integer_index_first);
}
private static function smoothsort_child_second( $integer_index_root ) {
// Fetch second Child-Index
return $integer_index_root - 1;
}
private static function smoothsort_child_first( $integer_index_root, $integer_size ) {
// Fetch first Child-Index
// FIX: PHP E_NOTICE - ArrayOffset -> !Isset
if( !isset( self::$smoothsort_array_leonardo_numbers[$integer_size - 2] )) return -1;
return self::smoothsort_child_second( $integer_index_root ) - self::$smoothsort_array_leonardo_numbers[$integer_size - 2];
}
//////////////////////////////////////////////////////////
private static function smoothsort_swap( $integer_index_item_a, $integer_index_item_b ) {
// Swap Items in Data-Array
$mixed_item = self::$smoothsort_reference_data[$integer_index_item_a];
self::$smoothsort_reference_data[$integer_index_item_a] = self::$smoothsort_reference_data[$integer_index_item_b];
self::$smoothsort_reference_data[$integer_index_item_b] = $mixed_item;
}
private static function smoothsort_compare( $integer_index_base, $integer_index_test ) {
// Call Comparator for Data-Item
// FIX: PHP E_NOTICE - ArrayOffset -> !Isset
if( !isset( self::$smoothsort_reference_data[$integer_index_base] ) && isset(self::$smoothsort_reference_data[$integer_index_test]) ) return true;
if( isset( self::$smoothsort_reference_data[$integer_index_base] ) && !isset(self::$smoothsort_reference_data[$integer_index_test]) ) return false;
if( !isset( self::$smoothsort_reference_data[$integer_index_base] ) && !isset(self::$smoothsort_reference_data[$integer_index_test]) ) return false;
return call_user_func_array( self::$smoothsort_callback_comparator, array( self::$smoothsort_reference_data[$integer_index_base], self::$smoothsort_reference_data[$integer_index_test] ));
}
//////////////////////////////////////////////////////////
public static function smoothsort_comparator_integer_ascending( $integer_value_base, $integer_value_test ) {
// Compare 2 Items from Data-Array (Integer) -> Ascending order -> true: swap it, false: skip it
if( $integer_value_base < $integer_value_test ) return true; return false;
}
public static function smoothsort_comparator_integer_descending( $integer_value_base, $integer_value_test ) {
// Compare 2 Items from Data-Array (Integer) -> Descending order -> true: swap it, false: skip it
if( $integer_value_base > $integer_value_test ) return true; return false;
}
public static function smoothsort_comparator_string_ascending( $string_value_base, $string_value_test ) {
// Compare 2 Items from Data-Array (String) -> Ascending order -> true: swap it, false: skip it
if( strnatcmp( $string_value_base, $string_value_test ) >= 0 ) return false;
return true;
}
public static function smoothsort_comparator_string_descending( $string_value_base, $string_value_test ) {
// Compare 2 Items from Data-Array (String) -> Descending order -> true: swap it, false: skip it
if( strnatcmp( $string_value_base, $string_value_test ) <= 0 ) return false;
return true;
}
}
Скачать архивы
Скачать zip-архив со скриптом.
Скачать tar.gz-архив со скриптом.
