Решил недавно повторить алгоритмы и структуры данных. Из разных источников у меня уже был составлен следующий список литературы по этим темам:
- С. Скиена – Алгоритмы. Руководство по разработке. 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"
комментарии (11)