Skip to content

Added Heap sort, tests, and documentation. #36

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Oct 6, 2019
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
1 change: 1 addition & 0 deletions allalgorithms/sorting/__init__.py
Original file line number Diff line number Diff line change
Expand Up @@ -6,3 +6,4 @@
from .stooge_sort import stooge_sort
from .cocktail_shaker_sort import cocktail_shaker_sort
from .tree_sort import tree_sort
from .heap_sort import heap_sort
48 changes: 48 additions & 0 deletions allalgorithms/sorting/heap_sort.py
Original file line number Diff line number Diff line change
@@ -0,0 +1,48 @@
# -*- coding: UTF-8 -*-
#
# Heap Sort Algorithm
# The All ▲lgorithms library for python
#
# Contributed by: DatHydroGuy
# Github: @DatHydroGuy
#


def build_heap(array_to_sort, array_length, index):
"""
Build a heap, where each node has two child nodes, and a root node is greater than both child nodes.
"""
largest = index # Flag the largest element as the last (root) element
left = 2 * index + 1 # Calculate index of left child node
right = 2 * index + 2 # Calculate index of right child node

# See if left child of root exists and is greater than root
if left < array_length and array_to_sort[index] < array_to_sort[left]:
largest = left

# See if right child of root exists and is greater than root
if right < array_length and array_to_sort[largest] < array_to_sort[right]:
largest = right

# If a larger element than root was found, swap with root so that root holds the new largest value
if largest != index:
array_to_sort[index], array_to_sort[largest] = array_to_sort[largest], array_to_sort[index] # swap

# Re-build the heap under the new largest root node
build_heap(array_to_sort, array_length, largest)


def heap_sort(array_to_sort):
"""
Builds a max-heap, then continuously removes the largest element and re-builds the heap until sorted
"""
array_length = len(array_to_sort)

# Build a max-heap to sort the elements into order
for index in range(array_length // 2 - 1, -1, -1):
build_heap(array_to_sort, array_length, index)

# One by one extract elements
for index in range(array_length - 1, 0, -1):
array_to_sort[index], array_to_sort[0] = array_to_sort[0], array_to_sort[index] # swap
build_heap(array_to_sort, index, 0)
33 changes: 33 additions & 0 deletions docs/sorting/heap-sort.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,33 @@
# Heap Sort

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.

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.

## Install

```
pip install allalgorithms
```

## Usage

```py
from allalgorithms.sorting import heap_sort

arr = [77, 2, 10, -2, 1, 7]
heap_sort(arr)

print(arr)
# -> [-2, 1, 2, 7, 10, 77]
```

## API

### heap_sort(array)

> Performs an in-place sort of the passed-in array

##### Params:

- `array`: Unsorted Array
10 changes: 8 additions & 2 deletions tests/test_sorting.py
Original file line number Diff line number Diff line change
Expand Up @@ -9,6 +9,7 @@
stooge_sort,
cocktail_shaker_sort,
tree_sort,
heap_sort,
shell_sort,
)

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

def test_cocktail_shaker_sort(self):
self.assertEqual([-44, 1, 2, 3, 7, 19], cocktail_shaker_sort([7, 3, 2, 19, -44, 1]))
def tree_sort(self):

def test_tree_sort(self):
self.assertEqual([-44, 1, 2, 3, 7, 19], tree_sort([7, 3, 2, 19, -44, 1]))

def test_heap_sort(self):
array = [7, 3, 2, 19, -44, 1]
heap_sort(array)
self.assertEqual([-44, 1, 2, 3, 7, 19], array)

def test_shell_sort(self):
self.assertEqual([-44, 1, 2, 3, 7, 19], shell_sort([7, 3, 2, 19, -44, 1]))

Expand Down