Skip to content

Instantly share code, notes, and snippets.

@jarhill0
Created November 5, 2017 04:36
Show Gist options
  • Select an option

  • Save jarhill0/9cf61fc2a20beaca6842684bb6c3ec8c to your computer and use it in GitHub Desktop.

Select an option

Save jarhill0/9cf61fc2a20beaca6842684bb6c3ec8c to your computer and use it in GitHub Desktop.
Solving the complexity of bubblesort
class BubbleSort:
def __init__(self, items):
self.items = items
self.operations = 0
def sort(self):
while not self.sorted():
for i in range(1, len(self.items)):
self.operations += 1
a, b = self.items[i - 1:i + 1]
if a > b:
self.items[i - 1] = b
self.items[i] = a
return self.items
def sorted(self):
last = self.items[0]
for item in self.items[1:]:
if item < last:
return False
last = item
return True
def count_worst_complexity(case):
items = list(range(case - 1, -1, -1))
sort = BubbleSort(items)
sort.sort()
return sort.operations
def main():
for n in range(2, 21):
print(n, count_worst_complexity(n))
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment