Алгоритм сортировки вставками: реализация на PHP

Решил недавно повторить алгоритмы и структуры данных. Из разных источников у меня уже был составлен следующий список литературы по этим темам:

• С. Скиена – Алгоритмы. Руководство по разработке. 2011
• S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms. 2006
• А. Х. Шень. Программирование: теоремы и задачи. 2007
• М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных. 2012
• Т. Кормен, Ч. Лейзерсон, И. Ривест, К. Штайн. Алгоритмы: построение и анализ. 2013
• Н. Вирт. Алгоритмы и структуры данных. 2010

Так как у меня уже была первая книга, начал с нее. Содержание понравилось, примеры не на псевдокоде, а на реальных ЯП (в частности C) тоже вполне устроили.

В самом начале книги автор (Стивен С. Скиена) приводит наглядный пример с алгоритмом сортировки вставками, дабы подчеркнуть важность применения качественных алгоритмов в любой компьютерной программе.

Вот реализация на C, которую приводит автор:

insertion_sort (item s[], int n)
{
	int i,j; // счетчики
	for (i=1; i<n; i++) {
		j=i;
		while ((j>0) && (s[j] < s[j-1])) {
			swap(&s[j],&s[j-1]);
			j = j-i;
		}
	}
}

Мне стало интересно подробнее разобраться в этом коде и перевести его на PHP. Возможно, как-то улучшить.

Итак, пишем реализацию алгоритма сортировки вставками на PHP.

Как быстро оказалось, нативной функции swap (или, например, array_swap_values) нет ни в PHP, ни в C.
Написал свою (см. в коде алгоритма).

Далее выяснилось, что пример в книге содержит ошибкуопечатку, т.к. с j = j – i код работать не захотел. В итоге эта строка видоизменилась в j = j – 1, — теперь всё работает. Также стоит учесть, что количество элементов множества в PHP считается по-разному, в зависимости от типа: для массива применяем функцию count(), для строки strlen() или mb_strlen().

Код алгоритма:

<?php
function swap (&$array,$key1,$key2) 
{
	list($array[$key1],$array[$key2]) = array($array[$key2],$array[$key1]);
	/* еще один вариант с третьей переменной
	$temp = $array[$key1];
	$array[$key1] = $array[$key2];
	$array[$key2] = $temp; 
	*/
}

function insertion_sort ($s) 
{
	$i = $j = 0; // счетчики
	if (is_array($s)) {
		$n = count($s);
	} else {
		$s = (string)$s;
		$n = mb_strlen($s);
	}	
	for ($i=1; $i<$n; $i++) {
		$j = $i;
		while (($j>0) && ($s[$j] < $s[$j-1])) {
			swap($s,$j,$j-1);
			$j = $j-1;
		}
	}
	return $s;
}
?>

Готово! Обратите внимание, а данной реализации алгоритма на вход могут подаваться не только массив, но и другие типы данных: строка, целое число, число с плавающей точкой.

Тестируем алгоритм в действии:

$s = array(9,55,7,23,38);
var_dump(insertion_sort($s)); // выведет: array(5) { [0]=> int(7) [1]=> int(9) [2]=> int(23) [3]=> int(38) [4]=> int(55) }

$s = array('S','O','R','T');
var_dump(insertion_sort($s)); // выведет: array(4) { [0]=> string(1) "O" [1]=> string(1) "R" [2]=> string(1) "S" [3]=> string(1) "T" }

$s = 5078145;
var_dump(insertion_sort($s)); // выведет: string(7) "0145578"

$s = 'INSERTIONSORT';
var_dump(insertion_sort($s)); // выведет: string(13) "EIINNOORRSSTT"

Автор: ginx

Источник