Sort & Search

Sort & Search You have been provided a code for creating a deck of cards: deck_of_cards.py. In addition you have been given a few different codes for sorting elements in a list: quick_sort.py, bubble_sort.py, insert_sort.py, and selection_sort.py. What you have been tasked to do is:

- Utilize one of the above sorting algorithms to sort the cards in the deck

-Both by suit and by value.

-The suits should be ordered in the same order in which the deck is created (see line 6 of deck_of_cards.py)

- Create a property that determines whether or not the deck is sorted.

- Create a search method that allows a user to describe a card and will return the location (array index) of the card.

- This search can easily be made to be high intelligent

- What can you do to make this search a constant time look up?

deck_of_cards.py

from random import shuffle as s

class Deck:

_suits = ["Diamonds", "Clubs", "Hearts", "Spades"]

def __init__(self):

cards = []

for s in self._suits: # Fill the deck with standard playing cards

for val in range(1, 14):

cards.append(self._Card(s, val))

self.cards = cards

def __iter__(self):

return self.cards.__iter__()

def __str__(self): #TODO Fix this to state whether or not the deck is sorted or shuffled;

return 'A deck of {self.size} cards'.format(self=self)

@property # Property to get the length of the cards list

def size(self):

return len(self.cards)

@property #TODO Implement a method to determine if the cards are sorted;

def is_sorted(self):

pass

def sort(self): #TODO Implement a method to sort cards by suit and value;

pass

def shuffle(self): # Method to put cards list in random order

shuffled_deck = s(self.cards)

return shuffled_deck

def search(self): #TODO Implement a public search method;

card = self._describe_card()

def _describe_card(self): # User facing private function to create a card to search for

print("What suit is the card?") # Pick a suit

prompt = ""

i = 1

for suit in self._suits: # Build prompt to pick suit

prompt +='{}. {} '.format(i, suit)

i += 1

while True:

s = int(input(prompt)) # Collect user info for suit

v = int(input("Enter a number from 1 to 13 (1 = Ace, 11 = Jack, 12 = Queen, 13 = King): ")) # Collect user info for value

if s in [1, 2, 3, 4] and v in [x for x in range(1, 14)]:

card = self._Card(self._suits[s - 1], v)

print(card) #TODO Remove this; only here for debugging.

break

print("Invalid card, try again") # If invalid try again

return card

class _Card: # Private inner class to create a Card

def __init__(self, suit, value): # Need a suit and a value. Will be two integers. 0-3 for suit and 1-13 for value

self.suit = suit

self.value = value

def __str__(self): # Print override

return '{self.value_name} of {self.suit}'.format(self=self)

def __eq__(self, card): # Equals override

if self.suit != card.suit:

return False

if self.value != card.value:

return False

return True

@property # Get proper suit name

def suit_name(self):

if self.suit == _suits[0]:

return 0

elif self.suit == _suits[1]:

return 1

elif self.suit == _suits[2]:

return 2

elif self.suit == _suits[3]:

return 3

else:

raise ValueError()

@property # Get proper value name

def value_name(self):

if self.value == 1:

return "Ace"

elif self.value == 11:

return "Jack"

elif self.value == 12:

return "Queen"

elif self.value == 13:

return "King"

else:

return self.value

if __name__ == '__main__': # Main method

deck = Deck() # Create empty Deck object

deck.shuffle()

deck.search()

-------------------------------------------------------------------------------------------------------

quick_sort.py

def partition(unsorted_array, first_index, last_index):

pivot = unsorted_array[first_index]

pivot_index = first_index

index_of_last_element = last_index

less_than_pivot_index = index_of_last_element

greater_than_pivot_index = first_index + 1

while True:

while unsorted_array[greater_than_pivot_index] < pivot and greater_than_pivot_index < last_index:

greater_than_pivot_index += 1

while unsorted_array[less_than_pivot_index] > pivot and less_than_pivot_index >= first_index:

less_than_pivot_index -= 1

if greater_than_pivot_index < less_than_pivot_index:

temp = unsorted_array[greater_than_pivot_index]

unsorted_array[greater_than_pivot_index] = unsorted_array[less_than_pivot_index]

unsorted_array[less_than_pivot_index] = temp

else:

break

unsorted_array[pivot_index] = unsorted_array[less_than_pivot_index]

unsorted_array[less_than_pivot_index] = pivot

return less_than_pivot_index

def quick_sort(unsorted_array, first, last):

if last - first <= 0:

return

else:

partition_point = partition(unsorted_array, first, last)

quick_sort(unsorted_array, first, partition_point-1)

quick_sort(unsorted_array, partition_point+1, last)

my_array = [43, 3, 77, 89, 4, 20]

print(my_array)

quick_sort(my_array, 0, 5)

print(my_array)

-----------------------------------------------------------------------------------------------------

insert_sort.py

def insertion_sort(unsorted_list):

for index in range(1, len(unsorted_list)):

search_index = index

insert_value = unsorted_list[index]

while search_index > 0 and unsorted_list[search_index-1] > insert_value:

unsorted_list[search_index] = unsorted_list[search_index-1]

search_index -= 1

unsorted_list[search_index] = insert_value

my_list = [10, 11, 12, 1, 2, 3]

print(my_list)

insertion_sort(my_list)

print(my_list)

----------------------------------------------------------------------

selection_sort.py

def selection_sort(unsorted_list):

size_of_list = len(unsorted_list)

for i in range(size_of_list):

for j in range(i+1, size_of_list):

if unsorted_list[j] < unsorted_list[i]:

temp = unsorted_list[i]

unsorted_list[i] = unsorted_list[j]

unsorted_list[j] = temp

a_list = [3, 2, 35, 4, 32, 94, 5, 7]

selection_sort(a_list)

print(a_list)

---------------------------------------------------------------------------------------------------

bubble_sort.py

unordered_list = [5, 2]

i = 0

first_element = unordered_list[0]

second_element = unordered_list[1]

temp = unordered_list[0]

unordered_list[0] = unordered_list[1]

unordered_list[1] = temp

print(unordered_list)

"""################################################################"""

def bubble_sort(unordered_list):

iteration_number = len(unordered_list)-1

for i in range(iteration_number,0,-1):

for j in range(i):

if unordered_list[j] > unordered_list[j+1]:

temp = unordered_list[j]

unordered_list[j] = unordered_list[j+1]

unordered_list[j+1] = temp

my_list = [4,3,2,1]

bubble_sort(my_list)

print(my_list)

my_list = [1,12,3,4]

bubble_sort(my_list)

print(my_list)