Сортировка массива вставками php

H Алгоритм сортировки вставками: реализация на PHP в черновиках Из песочницы

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

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

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

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

insertion_sort (item s[], int n) < int i,j; // счетчики for (i=1; i0) && (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().

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

 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; $i0) && ($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" 

Источник

php сортировка

В PHP есть замечательные функции для сортировки массивов данных, но речь пойдет не о них. В данной заметке я разместил примеры реализации алгоритмов сортировок на PHP, так сказать, что бы не отпускать далеко из головы. Подробно расписывать не буду, а буду приводить ссылки на Википедию. Кому надо добавляем в закладки 😉

Сортировка пузырьком на PHP

//Сортировка пузырьком function bubbleSort(array $arr) < $count = count($arr); if ($count for ($i = 0; $i < $count; $i++) < for ($j = $count - 1; $j >$i; $j--) < if ($arr[$j] < $arr[$j - 1]) < $tmp = $arr[$j]; $arr[$j] = $arr[$j - 1]; $arr[$j - 1] = $tmp; >> > return $arr; >

Сортировка вставками на PHP

//Сортировка вставками function insertSort(array $arr) < $count = count($arr); if ($count for ($i = 1; $i < $count; $i++) < $cur_val = $arr[$i]; $j = $i - 1; while (isset($arr[$j]) && $arr[$j] >$cur_val) < $arr[$j + 1] = $arr[$j]; $arr[$j] = $cur_val; $j--; >> return $arr; >

Сортировка слиянием на PHP

//Сортировка слиянием function mergeSort(array $arr) < $count = count($arr); if ($count $left = array_slice($arr, 0, (int)($count/2)); $right = array_slice($arr, (int)($count/2)); $left = mergeSort($left); $right = mergeSort($right); return merge($left, $right); > function merge(array $left, array $right) < $ret = array(); while (count($left) >0 && count($right) > 0) < if ($left[0] < $right[0]) < array_push($ret, array_shift($left)); >else < array_push($ret, array_shift($right)); >> array_splice($ret, count($ret), 0, $left); array_splice($ret, count($ret), 0, $right); return $ret; >

Быстрая сортировка на PHP

//Быстрая сортировка function quickSort(array $arr) < $count= count($arr); if ($count $first_val = $arr[0]; $left_arr = array(); $right_arr = array(); for ($i = 1; $i < $count; $i++) < if ($arr[$i] else < $right_arr[] = $arr[$i]; >> $left_arr = quickSort($left_arr); $right_arr = quickSort($right_arr); return array_merge($left_arr, array($first_val), $right_arr); >

Сортировка выбором на PHP

//Сортировка выбором function selectSort(array $arr) < $count= count($arr); if ($count for ($i = 0; $i < $count; $i++)< $k = $i; for($j = $i + 1; $j < $count; $j++)< if ($arr[$k] >$arr[$j]) < $k = $j; >if ($k != $i) < $tmp = $arr[$i]; $arr[$i] = $arr[$k]; $arr[$k] = $tmp; >> > return $arr; >

Использование примеров сортировок на PHP

echo "
"; echo "
", "Bubble Sorting - 1, 99, 3, 77, 5, 998, 7, 45, 32", "
"; $arr = array(1, 99, 3, 77, 5, 998, 7, 45, 32); $reuslt = bubbleSort($arr); print_r($reuslt); echo "
", "Insert Sorting - 1, 88, 5, 77, 99, 98, 97, 55, 56, 52, 59, 37", "
"; $arr = array(1, 88, 5, 77, 99, 98, 97, 55, 56, 52, 59, 37); $reuslt = insertSort($arr); print_r($reuslt); echo "
", "Merge Sorting - 6, 5, 3, 1, 8, 7, 9, 2, 4", "
"; $arr = array(6, 5, 3, 1, 8, 7, 9, 2, 4); $reuslt = mergeSort($arr); print_r($reuslt); echo "
", "Quick Sorting - 1, 99, 87, 2, 5, 9, 1999, 899, 777", "
"; $arr = array(1, 99, 87, 2, 5, 9, 1999, 899, 777); $reuslt = quickSort($arr); print_r($reuslt); echo "
", "Select Sorting - 11, 3, 51, 7, 99, 33, 55, 9", "
"; $arr = array(11, 3, 51, 7, 99, 33, 55, 9); $reuslt = selectSort($arr); print_r($reuslt);
 
Источник
 
Русские Блоги 
 
Хотя реализация кода сортировки вставкой не такая простая и грубая, как сортировка по пузырькам и сортировка по выбору, ее принцип должен быть самым простым для понимания, потому что любой, кто играл в покер, должен понять его за секунды. Сортировка вставкой - это самый простой и интуитивно понятный алгоритм сортировки. Принцип ее работы заключается в построении упорядоченной последовательности. Для несортированных данных выполните сканирование от начала до конца в отсортированной последовательности, чтобы найти соответствующую позицию и вставить.
 
Сортировка вставкой, как и сортировка пузырьков, также имеет алгоритм оптимизации, называемый вставкой с разделением половин.
 
Шаги алгоритма
 
1. Первый элемент первой сортируемой последовательности рассматривается как упорядоченная последовательность, а второй элемент до последнего элемента рассматривается как несортированная последовательность.
 
2. Отсканируйте неотсортированную последовательность от начала до конца и вставьте каждый отсканированный элемент в правильную позицию упорядоченной последовательности. (Если вставляемый элемент равен элементу в упорядоченной последовательности, вставляемый элемент вставляется после такого же элемента.)
 
Демонстрация анимации
 
Реализация кода PHP
 
function InsertSort($arr)< $num = count($arr); Обойти массив for ($i = 1;$i < $num; $i++) < Получить текущее значение $iTemp = $arr[$i]; Получить предыдущую позицию текущего значения $iPos = $i - 1; Если текущее значение меньше предыдущего значения, оно не достигнет начала массива. while (($iPos >= 0) && ($iTemp < $arr[$iPos])) < Поместите значение предыдущего назад $arr[$iPos + 1] = $arr[$iPos]; Убывающая позиция $iPos--; >$arr[$iPos+1] = $iTemp; > return $arr; >
 
function InsertSort($arr) < $length = count($arr); for ($i = 0; $i < $length - 1; $i++) < for ($j = $i + 1; $j >0; $j--) < if ($arr[$j] < $arr[$j - 1]) < $temp = $arr[$j - 1]; $arr[$j - 1] = $arr[$j]; $arr[$j] = $temp; >else < break; >> > return $arr; >
 
Источник
 
Алгоритм поиска и сортировки PHP: сортировка вставками
 
 
Алгоритм поиска и сортировки PHP: упражнение-3 с решением
 
Напишите программу PHP для сортировки списка элементов с помощью сортировки вставками.
 
Вставка сортировки - это простой алгоритм сортировки, который создает окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен в больших списках, чем более продвинутые алгоритмы, такие как быстрая сортировка, heapsort или сортировка слиянием.
 
Иллюстрированная презентация: вставка сортировки 
 
 
Графический пример вставки сортировки:
 
Пример решения: 
 
=0 && $my_array[$j] > $val) < $my_array[$j+1] = $my_array[$j]; $j--; >$my_array[$j+1] = $val; > return $my_array; > $test_array = array(3, 0, 2, 5, -1, 4, 1); echo "Original Array :\n"; echo implode(', ',$test_array ); echo "\nSorted Array :\n"; print_r(insertion_Sort($test_array)); ?> 
 
Оригинальный массив: 3, 0, 2, 5, -1, 4, 1 Сортированный массив: массив ( [0] => -1 [1] => 0 [2] => 1 [3] => 2 [4] => 3 [5] => 4 [6] => 5 )
 
 
Редактор кода PHP: 
 
Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus. 
 
Каков уровень сложности этого упражнения? 
 
Источник