CP 164 Data Structures _ Sorts_array.py

Document Content and Description Below

CP 164 Data Structures _ Sorts_array.py Array versions of various sorts. ------------------------------------------------------- Author: David Brown ID: 999999999 Email: [email protected] Section: CP... 164 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 [Show More]

Last updated: 1 year ago

Preview 1 out of 14 pages