forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathshell_sort.py
More file actions
47 lines (36 loc) · 1.11 KB
/
shell_sort.py
File metadata and controls
47 lines (36 loc) · 1.11 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
"""
Shell Sort
Shell sort is a generalisation of insertion sort that allows the exchange
of elements that are far apart. The gap between compared elements is
gradually reduced until it becomes 1, at which point the algorithm
behaves like a standard insertion sort.
Reference: https://en.wikipedia.org/wiki/Shellsort
Complexity:
Time: O(n log n) best / O(n^(4/3)) average / O(n^2) worst
Space: O(1)
"""
from __future__ import annotations
def shell_sort(array: list[int]) -> list[int]:
"""Sort an array in ascending order using shell sort.
Args:
array: List of integers to sort.
Returns:
A sorted list.
Examples:
>>> shell_sort([3, 1, 2])
[1, 2, 3]
"""
n = len(array)
gap = n // 2
while gap > 0:
y_index = gap
while y_index < n:
y = array[y_index]
x_index = y_index - gap
while x_index >= 0 and y < array[x_index]:
array[x_index + gap] = array[x_index]
x_index -= gap
array[x_index + gap] = y
y_index += 1
gap //= 2
return array