0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: php, php программирование, сортировка шелла, алгоритм сортировки</p>
1
<p>Теги: php, php программирование, сортировка шелла, алгоритм сортировки</p>
2
<p>Эту статью я бы хотел посвятить замечательному алгоритму сортировки, носящему имя<strong>Дональда Шелла</strong>. Не секрет, что сортировка Шелла зачастую работает медленнее, чем быстрая сортировка (<strong>сортировка Хоара</strong>), которую мы рассматривали<a>здесь</a>. Однако, быстрая сортировка быстро замедляется до квадратичной сложности при неудачном наборе данных, что является худшим результатом, чем худшее время для сортировки<strong>Шелла</strong>.</p>
2
<p>Эту статью я бы хотел посвятить замечательному алгоритму сортировки, носящему имя<strong>Дональда Шелла</strong>. Не секрет, что сортировка Шелла зачастую работает медленнее, чем быстрая сортировка (<strong>сортировка Хоара</strong>), которую мы рассматривали<a>здесь</a>. Однако, быстрая сортировка быстро замедляется до квадратичной сложности при неудачном наборе данных, что является худшим результатом, чем худшее время для сортировки<strong>Шелла</strong>.</p>
3
<p>При сортировке мы сравниваем и сортируем элементы в массиве, отстоящие друг от друга на n ячеек. Далее n уменьшается и процедура повторяется снова с обновленным значением n. Так до тех пор, пока n не уменьшится до 1.</p>
3
<p>При сортировке мы сравниваем и сортируем элементы в массиве, отстоящие друг от друга на n ячеек. Далее n уменьшается и процедура повторяется снова с обновленным значением n. Так до тех пор, пока n не уменьшится до 1.</p>
4
<p>Особое внимание нужно уделить выбору набора расстояний n. Сам<strong>Дональд Шелл</strong>предложил последовательность N1 = L/2, Ni = Ni-1/2, Nk = 1. Такая последовательность в худшем случае обеспечивает квадратичную сложность.</p>
4
<p>Особое внимание нужно уделить выбору набора расстояний n. Сам<strong>Дональд Шелл</strong>предложил последовательность N1 = L/2, Ni = Ni-1/2, Nk = 1. Такая последовательность в худшем случае обеспечивает квадратичную сложность.</p>
5
<p>Улучшение этой последовательности разработал<strong>Роберт Седжвик</strong>(кстати, автор отличной книжки по алгоритмам): Ni = 9<em>2^i - 9</em>2^(i/2) + 1. При этом требуется остановка на значении inc[s-1], если 3*inc[s] > size, где size - размер сортируемого массива. В худшем случае сложность будет порядка 4/3.</p>
5
<p>Улучшение этой последовательности разработал<strong>Роберт Седжвик</strong>(кстати, автор отличной книжки по алгоритмам): Ni = 9<em>2^i - 9</em>2^(i/2) + 1. При этом требуется остановка на значении inc[s-1], если 3*inc[s] > size, где size - размер сортируемого массива. В худшем случае сложность будет порядка 4/3.</p>
6
<p>Для массивов до 4000 элементов лучшей считается<strong>последовательность Циура</strong>: {1, 4, 10, 23, 57, 132, 301, 701, 1750}.</p>
6
<p>Для массивов до 4000 элементов лучшей считается<strong>последовательность Циура</strong>: {1, 4, 10, 23, 57, 132, 301, 701, 1750}.</p>
7
<p>После выбора последовательности расстояний можно приступить к реализации. Как и всегда, в функцию сортируемый массив будем передавать по ссылке. Для примера я буду уменьшать шаг вдвое на каждой итерации.</p>
7
<p>После выбора последовательности расстояний можно приступить к реализации. Как и всегда, в функцию сортируемый массив будем передавать по ссылке. Для примера я буду уменьшать шаг вдвое на каждой итерации.</p>
8
function(&$a){ $sort_length = count($a) - 1; $step = ceil(($sort_length + 1)/2); do{ // тело цикла // конец цикла $step = $step / 2; } while($step > 0) }<p>В теле цикла мы собираем подмассив значений, ключи которых отстоят друг от друга на шаг, указанный в цикле, и сортируем их простой вставкой.</p>
8
function(&$a){ $sort_length = count($a) - 1; $step = ceil(($sort_length + 1)/2); do{ // тело цикла // конец цикла $step = $step / 2; } while($step > 0) }<p>В теле цикла мы собираем подмассив значений, ключи которых отстоят друг от друга на шаг, указанный в цикле, и сортируем их простой вставкой.</p>
9
// тело цикла $i = ceil($step); do { $j=$i-$step; $c=1; do { if($a[$j]<=$a[$j+$step]) { $c=0; } else { $tmp=$a[$j]; $a[$j]=$a[$j+$step]; $a[$j+$step]=$tmp; } $j=$j-1; } while($j>=0 && ($c==1)); $i = $i+1; } while($i<=$sort_length); // конец цикла<p>Вот и всё. Подробности и результат сортировки смотрите в моём<a>гитхабе</a>.</p>
9
// тело цикла $i = ceil($step); do { $j=$i-$step; $c=1; do { if($a[$j]<=$a[$j+$step]) { $c=0; } else { $tmp=$a[$j]; $a[$j]=$a[$j+$step]; $a[$j+$step]=$tmp; } $j=$j-1; } while($j>=0 && ($c==1)); $i = $i+1; } while($i<=$sort_length); // конец цикла<p>Вот и всё. Подробности и результат сортировки смотрите в моём<a>гитхабе</a>.</p>
10
10