Скрипт сортировки значений алгоритмом SmoothSort
Вход Регистрация

Скрипт сортировки значений алгоритмом SmoothSort

Этот скрипт можно использовать для сортировки значений, используя алгоритм 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;
	}
}

Скачать архивы


Комментировать

captcha

Вход

Зарегистрируйтесь, если нет учетной записи

Напомнить пароль
Регистрация
Напомнить пароль
Войти в личный кабинет