FAQ: Bubble Sort: Python - Bubble Sort: Optimized

This community-built FAQ covers the “Bubble Sort: Optimized” exercise from the lesson “Bubble Sort: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Sorting Algorithms

FAQs on the exercise Bubble Sort: Optimized

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

I threw together the bubble sorts here with the one that is in the A Sorted Tale project and one I made that I called double_bubble(even though it’s not really that, it’s a fun name). I provided them a random list rather than just a reverse order one, so the “flags” have some effect.

import random
nums = [random.randint(0, 100) for num in range(1, 21)]
print("PRE SORT: {0}".format(nums))

def swap(arr, index_1, index_2):
  temp = arr[index_1]
  arr[index_1] = arr[index_2]
  arr[index_2] = temp

def bubble_sort_unoptimized(arr):
  print("bubble_sort_unoptimized")
  print(arr)
  iteration_count = 0
  swap_count = 0
  for el in arr:
    for index in range(len(arr) - 1):
      iteration_count += 1
      if arr[index] > arr[index + 1]:
        swap_count += 1
        swap(arr, index, index + 1)
    print(arr)

  print("ITERATION COUNT: {0}".format(iteration_count))
  print("SWAP COUNT: {0}".format(swap_count))

def bubble_sort(arr):
  print("bubble_sort")
  print(arr)
  iteration_count = 0
  swap_count = 0
  for i in range(len(arr)):
    # iterate through unplaced elements
    for idx in range(len(arr) - i - 1):
      iteration_count += 1
      if arr[idx] > arr[idx + 1]:
        swap_count += 1
        # replacement for swap function
        arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
    print(arr)
        
  print("ITERATION COUNT: {0}".format(iteration_count))
  print("SWAP COUNT: {0}".format(swap_count))
  
def bubble_sort_with_flag(arr):
  print("bubble_sort_with_flag")
  print(arr)
  iteration_count = 0
  swap_count = 0
  sorted = False
  while not sorted:
    sorted = True
    for idx in range(len(arr) - 1):
      iteration_count += 1
      if arr[idx] > arr[idx + 1]:
        sorted = False
        arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
        swap_count += 1
    print(arr)
  print("ITERATION COUNT: {0}".format(iteration_count))
  print("SWAP COUNT: {0}".format(swap_count))
    
def double_bubble(arr):
  print("double_bubble")
  print(arr)
  iteration_count = 0
  comparison_count = 0
  swap_count = 0
  start_point = 0
  end_point = len(arr) - 1
  sorted = False
  while start_point < end_point and not sorted:
      back_idx = end_point
      sorted = True #maybe
      for front_idx in range(start_point, end_point):
        iteration_count += 1
        comparison_count += 1
        if arr[front_idx] > arr[front_idx + 1]:
          swap_count += 1
          sorted = False
          arr[front_idx], arr[front_idx + 1] = arr[front_idx + 1], arr[front_idx]
        comparison_count += 1
        if arr[back_idx] < arr[back_idx - 1]:
          swap_count += 1
          sorted = False
          arr[back_idx], arr[back_idx - 1] = arr[back_idx - 1], arr[back_idx]
        back_idx -= 1
      start_point +=  1
      end_point -= 1
      print(arr)
  
  print("ITERATION COUNT: {0}".format(iteration_count))
  print("COMPARISON COUNT: {0}".format(comparison_count))
  print("SWAP COUNT: {0}".format(swap_count))

  
bubble_sort_unoptimized(nums.copy())
bubble_sort(nums.copy())
bubble_sort_with_flag(nums.copy())
double_bubble(nums.copy())

If you wanted to count how many times the built in sort compares, you could wrap the numbers with your own class that implements less-than which 1) counts how many times it’s called 2) compares the numbers – after sorting the counts can be collected and summed up

class ComparisonCounter:
    def __init__(self, value):
        self.v = value
        self.count = 0

    def __lt__(self, other):
        'this method corresponds to the operator: <'
        self.count += 1
        return self.v < other.v


nums_ = [ComparisonCounter(n) for n in nums]
sorted(nums_)
print('comparisons:', sum(n.count for n in nums_))
1 Like

I love it! Hope you don’t mind if I make use of it. :heart_eyes:

Why can’t I write “for index in arr-1:” instead of “for index in range(len(arr) - 1):”. Tried to look it up , and don’t understand why it doesn’t work; https://stackoverflow.com/questions/19184335/is-there-a-need-for-rangelena

You are looking for something to generate a sequence of integers beginning at zero and ending with two less than the array length, 0,1,2,3… etc, because you are need indexes to tell the list elements how to swap.

The other thing you suggest, for index in arr-1: will throw an TypeError, because arr is a list, and 1 is an int, producing unsupported operand type(s) for -: 'list' and 'int'

If you omit the -1, you just get the elements of the list:

arr = [9, 8, 7]

for index in arr:
    print(index)
# Output:
9
8
7

… so what do you do with the first two, when you see that 9 > 8? Lacking indexes, how do you swap them?

… Or are you just asking why for i in range(len(L)): isn’t the same as for i in L: ? They are two different things.