from math import log from Deque_linked import Deque class Sorts: """ ------------------------------------------------------- Defines a number of linked 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 gnome_sort(a): """ ------------------------------------------------------- Sorts a Deque using the Gnome Sort algorithm. Use: gnome_sort(a) ------------------------------------------------------- Parameters: a - a linked structure of comparable elements (Deque) Returns: None ------------------------------------------------------- """ # your code here return # Sort Utilities @staticmethod def sort_test(a): """ ------------------------------------------------------- Determines whether a linked deque is sorted or not. Use: sort_test(a) ------------------------------------------------------- Parameters: a - a linked deque of comparable elements (?) Returns: returns is_sorted - True if contents of a are sorted, False otherwise. ------------------------------------------------------- """ is_sorted = True # Test forward links current = a._front while is_sorted and current is not None and \ current._next is not None: if current._value = current._prev._value: current = current._prev else: is_sorted = False return is_sorted

Gnome Sort would be difficult to implement for a singly linked list as there is no easy way to move to the left in the list. However, we have the linked Deque data structure (Deque_linked.py) which gives us those reverse links. Write and test a linked Gnome Sort using a linked Deque. @staticmethod def gnome_sort(a): Sorts a Deque using the Gnome Sort algorithm. Use: gnome_sort(a) Parameters: a - a linked structure of comparable elements (Deque) Returns: None Add the sort to the module Sorts Deque linked.py. Put the sorts_Deque_linked.py module in your login_data_structures project. Test the sort from t04.py, using a Deque. Gnome Sort would be difficult to implement for a singly linked list as there is no easy way to move to the left in the list. However, we have the linked Deque data structure (Deque_linked.py) which gives us those reverse links. Write and test a linked Gnome Sort using a linked Deque. @staticmethod def gnome_sort(a): Sorts a Deque using the Gnome Sort algorithm. Use: gnome_sort(a) Parameters: a - a linked structure of comparable elements (Deque) Returns: None Add the sort to the module Sorts Deque linked.py. Put the sorts_Deque_linked.py module in your login_data_structures project. Test the sort from t04.py, using a Deque