CP 164 Data Structures _ Sorts_array.py

CP 164 Data Structures _ Sorts_ CP 164 Data Structures _ Sorts_ Array versions of various sorts. ------------------------------------------------------- Author: David Brown ID: Email: Section: CP 164 A __updated__ = "" ------------------------------------------------------- """ # 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(S) Use: S = 0 ------------------------------------------------------- """ swaps = 0 # Tracks swaps performed. # The Sorts @staticmethod def insertion_sort(a): """ ------------------------------------------------------- Sorts an array using the Insertion Sort algorithm. Use: Stion_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: Stion_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: Se_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