CP 164 Data Structures _ Sorts_array.py Array versions of various sorts.
-------------------------------------------------------
Author: David Brown
ID: 999999999
Email:
[email protected]
Section: CP164 A
__updated__ =
...
CP 164 Data Structures _ Sorts_array.py Array versions of various sorts.
-------------------------------------------------------
Author: David Brown
ID: 999999999
Email:
[email protected]
Section: CP164 A
__updated__ = "2018-11-29"
-------------------------------------------------------
"""
# Imports
from math import log, ceil
from BST_linked import BST
class Sorts:
"""
-------------------------------------------------------
Defines a number of array-based sort operations.
Uses class attribute 'swaps' to determine how many times
elements are swapped by the class.
Use: print(Sorts.swaps)
Use: Sorts.swaps = 0
-------------------------------------------------------
"""
swaps = 0 # Tracks swaps performed.
# The Sorts
@staticmethod
def insertion_sort(a):
"""
-------------------------------------------------------
Sorts an array using the Insertion Sort algorithm.
Use: Sorts.insertion_sort(a)
-------------------------------------------------------
Parameters:
a - an array of comparable elements (?)
Returns:
None
-------------------------------------------------------
"""
n = len(a)
for i in range(1, n):
# Walk through entire array, swap the next value into its
# proper spot in the sorted part of a.
j = i
while j > 0 and a[j - 1] > a[j]:
Sorts._swap(a, j - 1, j)
j = j - 1
return
@staticmethod
def selection_sort(a):
"""
-------------------------------------------------------
Sorts an array using the Selection Sort algorithm.
Use: Sorts.selection_sort(a)
-------------------------------------------------------
Parameters:
a - an array of comparable elements (?)Returns:
None
-------------------------------------------------------
"""
n = len(a)
for i in range(n):
# Walk through entire array
m = i
for j in range(i + 1, n):
# Find smallest value in unsorted part of array
if a[m] > a[j]:
# Track smallest value so far
m = j
if m != i:
# swap elements only if necessary
Sorts._swap(a, m, i)
return
@staticmethod
def bubble_sort(a):
"""
-------------------------------------------------------
Sorts an array using the Bubble Sort algorithm.
Use: Sorts.bubble_sort(a)
-------------------------------------------------------
Parameters:
a - an array of comparable elements (?)
Returns:
None
-------------------------------------------------------
"""
done = False
last = len(a) - 1
while not done:
# assume done is true
done = True
last_swapped = 0
i = 0
while i < last:
if a[i] > a[i + 1]:
# Save the list index swapped.
last_swapped = i
# The pair (a[i], a[i+1]) is out of order.
# Exchange a[i] and a[i + 1] to put them in sorted order.
Sorts._swap(a, i, i + 1)
# If you swapped you need another pass.
done = False
i += 1
last = last_swapped
# Decreases 'last' because everything after last_swapped is already
# in order. done == False iff no pair of keys swapped on last pass.
return
@staticmethod
def bst_sort(a):
"""
-------------------------------------------------------
Sorts an array using the Tree Sort alg
