0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Как и в случае с<a>сортировкой выборкой</a>,<strong>алгоритм сортировки вставками</strong>выполняет сегментацию списка на 2 части: сортированную и несортированную. Далее алгоритм перебирает 2-й сегмент, вставляя текущий элемент в правильную позицию 1-го сегмента.</p>
1
<p>Как и в случае с<a>сортировкой выборкой</a>,<strong>алгоритм сортировки вставками</strong>выполняет сегментацию списка на 2 части: сортированную и несортированную. Далее алгоритм перебирает 2-й сегмент, вставляя текущий элемент в правильную позицию 1-го сегмента.</p>
2
<h2>Описание алгоритма</h2>
2
<h2>Описание алгоритма</h2>
3
<p>По умолчанию предполагается, что 1-й элемент списка отсортирован. Следовательно, можно переходить к следующему элементу, обозначив его х. Когда х больше первого, всё остаётся на своих местах. Когда меньше, первый элемент копируется на 2-ю позицию, а в качестве первого элемента устанавливается, соответственно, х.</p>
3
<p>По умолчанию предполагается, что 1-й элемент списка отсортирован. Следовательно, можно переходить к следующему элементу, обозначив его х. Когда х больше первого, всё остаётся на своих местах. Когда меньше, первый элемент копируется на 2-ю позицию, а в качестве первого элемента устанавливается, соответственно, х.</p>
4
<p>Таким образом, при переходе к другим элементам неотсортированного сегмента, происходит перемещение более крупных элементов по списку вверх, пока не закончится список или не встретится элемент, который меньше x. В последнем случае x будет помещено на правильную позицию.</p>
4
<p>Таким образом, при переходе к другим элементам неотсортированного сегмента, происходит перемещение более крупных элементов по списку вверх, пока не закончится список или не встретится элемент, который меньше x. В последнем случае x будет помещено на правильную позицию.</p>
5
<h2>Реализация алгоритма</h2>
5
<h2>Реализация алгоритма</h2>
6
<p>Реализация алгоритма на языке программирования Python выглядит следующим образом:</p>
6
<p>Реализация алгоритма на языке программирования Python выглядит следующим образом:</p>
7
def insertion_sort(nums): # Сортировка начинается со 2-го элемента, так как по умолчанию считается, что 1-й элемент уже отсортирован for i in range(1, len(nums)): item_to_insert = nums[i] # Сохраняется ссылка на индекс предыдущего элемента j = i - 1 # Элементы сортированного сегмента перемещаются вперёд, если они больше, чем элемент для вставки while j >= 0 and nums[j] > item_to_insert: nums[j + 1] = nums[j] j -= 1 # Вставляется элемент nums[j + 1] = item_to_insert # Происходит проверка работоспособности random_list_of_nums = [9, 1, 15, 28, 6] insertion_sort(random_list_of_nums) print(random_list_of_nums)<h2>Время сортировки вставками</h2>
7
def insertion_sort(nums): # Сортировка начинается со 2-го элемента, так как по умолчанию считается, что 1-й элемент уже отсортирован for i in range(1, len(nums)): item_to_insert = nums[i] # Сохраняется ссылка на индекс предыдущего элемента j = i - 1 # Элементы сортированного сегмента перемещаются вперёд, если они больше, чем элемент для вставки while j >= 0 and nums[j] > item_to_insert: nums[j + 1] = nums[j] j -= 1 # Вставляется элемент nums[j + 1] = item_to_insert # Происходит проверка работоспособности random_list_of_nums = [9, 1, 15, 28, 6] insertion_sort(random_list_of_nums) print(random_list_of_nums)<h2>Время сортировки вставками</h2>
8
<p>Время сортировки с использованием этого алгоритма, как правило, равняется O(n2), где n - число элементов списка.</p>
8
<p>Время сортировки с использованием этого алгоритма, как правило, равняется O(n2), где n - число элементов списка.</p>
9
<p><em>Источник - "<a>Sorting Algorithms in Python</a>".</em></p>
9
<p><em>Источник - "<a>Sorting Algorithms in Python</a>".</em></p>
10
10