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

Commit78d8a9b

Browse files
authored
Added Heap sort, tests, and documentation. (#36)
Added Heap sort, tests, and documentation.Co-authored-by: Abraham Hernandez <abraham@abranhe.com>
2 parents4cb0741 +ee3e0cc commit78d8a9b

File tree

4 files changed

+90
-2
lines changed

4 files changed

+90
-2
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: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
stooge_sort,
1010
cocktail_shaker_sort,
1111
tree_sort,
12+
heap_sort,
1213
shell_sort,
1314
)
1415

@@ -34,10 +35,15 @@ def test_stooge_sort(self):
3435

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

42+
deftest_heap_sort(self):
43+
array= [7,3,2,19,-44,1]
44+
heap_sort(array)
45+
self.assertEqual([-44,1,2,3,7,19],array)
46+
4147
deftest_shell_sort(self):
4248
self.assertEqual([-44,1,2,3,7,19],shell_sort([7,3,2,19,-44,1]))
4349

0 commit comments

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