Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf60068d

Browse files
committed
Added Heap sort, tests, and documentation.
Fixed test call for tree sort.
1 parent4305a29 commitf60068d

File tree

4 files changed

+91
-3
lines changed

4 files changed

+91
-3
lines changed

‎allalgorithms/sorting/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,3 +6,4 @@
66
from .stooge_sortimportstooge_sort
77
from .cocktail_shaker_sortimportcocktail_shaker_sort
88
from .tree_sortimporttree_sort
9+
from .heap_sortimportheap_sort

‎allalgorithms/sorting/heap_sort.py‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# -*- coding: UTF-8 -*-
2+
#
3+
# Heap Sort Algorithm
4+
# The All ▲lgorithms library for python
5+
#
6+
# Contributed by: DatHydroGuy
7+
# Github: @DatHydroGuy
8+
#
9+
10+
11+
defbuild_heap(array_to_sort,array_length,index):
12+
"""
13+
Build a heap, where each node has two child nodes, and a root node is greater than both child nodes.
14+
"""
15+
largest=index# Flag the largest element as the last (root) element
16+
left=2*index+1# Calculate index of left child node
17+
right=2*index+2# Calculate index of right child node
18+
19+
# See if left child of root exists and is greater than root
20+
ifleft<array_lengthandarray_to_sort[index]<array_to_sort[left]:
21+
largest=left
22+
23+
# See if right child of root exists and is greater than root
24+
ifright<array_lengthandarray_to_sort[largest]<array_to_sort[right]:
25+
largest=right
26+
27+
# If a larger element than root was found, swap with root so that root holds the new largest value
28+
iflargest!=index:
29+
array_to_sort[index],array_to_sort[largest]=array_to_sort[largest],array_to_sort[index]# swap
30+
31+
# Re-build the heap under the new largest root node
32+
build_heap(array_to_sort,array_length,largest)
33+
34+
35+
defheap_sort(array_to_sort):
36+
"""
37+
Builds a max-heap, then continuously removes the largest element and re-builds the heap until sorted
38+
"""
39+
array_length=len(array_to_sort)
40+
41+
# Build a max-heap to sort the elements into order
42+
forindexinrange(array_length//2-1,-1,-1):
43+
build_heap(array_to_sort,array_length,index)
44+
45+
# One by one extract elements
46+
forindexinrange(array_length-1,0,-1):
47+
array_to_sort[index],array_to_sort[0]=array_to_sort[0],array_to_sort[index]# swap
48+
build_heap(array_to_sort,index,0)

‎docs/sorting/heap-sort.md‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#Heap Sort
2+
3+
Heap sort is a comparison-based sorting algorithm which operates on a Binary Heap data structure. It can be regarded as a version of Selection sort which is improved by use of the heap data structure rather than a linear-time search.
4+
5+
Heap sort is typically slower than Quicksort, but it does have a better worst-case scenario of O(n log n). It is an in-place algorithm, but does not produce a stable sort.
6+
7+
##Install
8+
9+
```
10+
pip install allalgorithms
11+
```
12+
13+
##Usage
14+
15+
```py
16+
from allalgorithms.sortingimport heap_sort
17+
18+
arr= [77,2,10,-2,1,7]
19+
heap_sort(arr)
20+
21+
print(arr)
22+
# -> [-2, 1, 2, 7, 10, 77]
23+
```
24+
25+
##API
26+
27+
###heap_sort(array)
28+
29+
>Performs an in-place sort of the passed-in array
30+
31+
#####Params:
32+
33+
-`array`: Unsorted Array

‎tests/test_sorting.py‎

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,8 @@
88
pigeonhole_sort,
99
stooge_sort,
1010
cocktail_shaker_sort,
11-
tree_sort
11+
tree_sort,
12+
heap_sort
1213
)
1314

1415

@@ -33,10 +34,15 @@ def test_stooge_sort(self):
3334

3435
deftest_cocktail_shaker_sort(self):
3536
self.assertEqual([-44,1,2,3,7,19],cocktail_shaker_sort([7,3,2,19,-44,1]))
36-
37-
deftree_sort(self):
37+
38+
deftest_tree_sort(self):
3839
self.assertEqual([-44,1,2,3,7,19],tree_sort([7,3,2,19,-44,1]))
3940

41+
deftest_heap_sort(self):
42+
array= [7,3,2,19,-44,1]
43+
heap_sort(array)
44+
self.assertEqual([-44,1,2,3,7,19],array)
45+
4046

4147
if__name__=="__main__":
4248
unittest.main()

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp