Previous Lecture Lecture 13 Next Lecture

Lecture 13, Tue 05/14

Sorting Algorithms

In-class activity: sorting algorithm excerises

[54, 26, 93, 17, 77, 31, 44, 55, 20]

Bubble sort:

Selection sort:

Bubble Sort

def bubbleSort(alist):
  for passnum in range(len(alist)-1, 0, -1):
    printf("{passnum = }")
    for i in range(passnum):
      if i == 3:
        break
      if alist[i] > alist[i+1]:
        temp = alist[i]
        alist[i] = alist[i+1]
        alist[i+1] = temp
    print(alist)

Insertion Sort

def insertionSort(alist):
  for index in range(1, len(alist)):
    print("pass", index)
    currentvalue = alist[index]
    position = index

    while position > 0 and alist[position-1]>currentvalue:
      print("Comparing ", alist[position-1], currentvalue)
      alist[position] = alist[position-1]
      position = position-1

    alist[position] = currentvalue
    print(alist)

Class examples

class Pet:
  def __init__(self, name, animal, rating):
    """
    :param str name: - name of pet
    :param str animal: - type of pet(eg: 'snake' > 'cat' > 'dog')
    :param str rating: - user rating ('meh' < 'ok' < 'ok' < 'nice' < 'awesome')
    """
    self.name = name
    self.animal = animal
    self.rating = rating

  def __repr__(self):
    animal_map = {'snake': 100, 'cat': 90, 'dog': 80}
    rating_map = {'meh': 0, 'ok': 1, 'nice': 2, 'awesome': 3}
    return f"Name {self.name}\nAnimal type: {self.animal} (animal_map[self.animal])\n \
      Rating: {self.rating} (rating_map[self.rating])"

  def __lt__(self, other):
    animal_map = {'snake': 100, 'cat': 90, 'dog': 80}
    rating_map = {'meh': 0, 'ok': 1, 'nice': 2, 'awesome': 3}

    if animal_map[self.animal] < animal_map[other.animal]:
      return True
    return False
  # or
  def __lt__(self, other):
    animal_map = {'snake': 100, 'cat': 90, 'dog': 80}
    rating_map = {'meh': 0, 'ok': 1, 'nice': 2, 'awesome': 3}

    if animal_map[self.animal] == animal_map[other.animal]:
      return rating_map[self.animal] < rating_map[other.animal]
    return animal_map[self.animal] < animal_map[other.animal]

Student Questions