21 lines
1.8 KiB
Markdown
Executable File
21 lines
1.8 KiB
Markdown
Executable File
Усовершенствованный вариант сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. [Сложность алгоритма](Оценка%20сложности%20алгоритма) $O(n^2)$
|
||
#### Алгоритм
|
||
При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии $d$. После этого процедура повторяется для некоторых меньших значений $d$, а завершается сортировка Шелла упорядочиванием элементов при $d=1$. Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места.
|
||
#### Пример
|
||
![[sort_shell.gif]]
|
||
#### В виде кода
|
||
```python
|
||
def shell_sort(data: list[int]) -> list[int]:
|
||
last_index = len(data)
|
||
step = len(data)//2
|
||
while step > 0:
|
||
for i in range(step, last_index, 1):
|
||
j = i
|
||
delta = j - step
|
||
while delta >= 0 and data[delta] > data[j]:
|
||
data[delta], data[j] = data[j], data[delta]
|
||
j = delta
|
||
delta = j - step
|
||
step //= 2
|
||
return data
|
||
``` |