FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
python-3/algorithms/sorting/tim_sort.py at master · iCodeIN/python-3 · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
iCodeIN
/
python-3
Public
forked from
AllAlgorithms/python
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
python-3
/
algorithms
/
sorting
/
tim_sort.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
90 lines (68 loc) · 2.87 KB
Breadcrumbs
python-3
/
algorithms
/
sorting
/
tim_sort.py
Copy path
File metadata and controls
90 lines (68 loc) · 2.87 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
from
random
import
randint
class
TimSort
:
""" A class to demonstrate Tim Sort """
def
__init__
(
self
,
array
):
self
.
array
=
array
self
.
arrayLength
=
len
(
array
)
self
.
__RUN
=
32
def
insertionSort
(
self
,
arr
):
""" Sorts the given array from given starting index to ending index """
for
i
in
range
(
1
,
len
(
arr
)):
currentElement
=
arr
[
i
]
j
=
i
-
1
while
j
>=
0
and
arr
[
j
]
>
currentElement
:
arr
[
j
+
1
]
=
arr
[
j
]
j
-=
1
arr
[
j
+
1
]
=
currentElement
return
arr
def
mergeRuns
(
self
,
arr1
,
arr2
):
""" Merges the given two arrays: arr1 and arr2 """
newArray
=
list
()
lengthOfArr1
=
len
(
arr1
)
lengthOfArr2
=
len
(
arr2
)
# The variable i is used to keep track of the indices of the first array
# The variable j is used to keep track of the indices of the second array
# The variable k is used to keep track of the indices of the newArray array which is to be returned
i
,
j
,
k
=
0
,
0
,
0
while
i
<
lengthOfArr1
and
j
<
lengthOfArr2
:
if
arr1
[
i
]
<=
arr2
[
j
]:
newArray
[
k
]
=
arr1
[
i
]
k
+=
1
i
+=
1
elif
arr1
[
i
]
>=
arr2
[
j
]:
newArray
[
k
]
=
arr2
[
j
]
k
+=
1
j
+=
1
# The below two loops will append any remaining elements left in any of the two arrays.
while
i
<
lengthOfArr1
:
newArray
.
append
(
arr1
[
i
])
i
+=
1
while
j
<
lengthOfArr2
:
newArray
.
append
(
arr2
[
j
])
j
+=
1
return
newArray
def
changeRun
(
self
,
newRun
):
self
.
__RUN
=
newRun
def
algorithm
(
self
):
""" This function will perfom Tim Sort on the given array """
# Breaking the array into chunks of subarray(RUNS) of size RUN and perfomring insertionSort on them.
for
i
in
range
(
0
,
self
.
arrayLength
,
self
.
__RUN
):
currentRunElements
=
self
.
array
[
i
:
i
+
self
.
__RUN
]
self
.
array
[
i
:
i
+
self
.
__RUN
]
=
self
.
insertionSort
(
currentRunElements
)
temp_runner
=
self
.
__RUN
while
temp_runner
<
self
.
arrayLength
:
for
idx
in
range
(
0
,
self
.
arrayLength
,
temp_runner
*
2
):
firstArray
=
self
.
array
[
idx
:
idx
+
temp_runner
]
secondArray
=
self
.
array
[
idx
+
temp_runner
:
idx
+
temp_runner
*
2
]
self
.
array
[
idx
:
idx
+
temp_runner
*
2
]
=
self
.
mergeRuns
(
firstArray
,
secondArray
)
temp_runner
=
self
.
__RUN
*
2
print
(
f"The sorted array is :
{
self
.
array
}
"
)
def
__repr__
(
self
):
return
f"Array:
{
self
.
array
}
\n
RUN:
{
self
.
__RUN
}
"
myArray
=
[
randint
(
1
,
100
)
for
i
in
range
(
15
)]
demo
=
TimSort
(
myArray
)
print
(
demo
)
demo
.
algorithm
()
Back
|
FazBrowse Home
|
New Git URL