The Bubble Sort Algorithm

Bubble sort is a simple and basic sorting algorithm used to arrange elements in a specific order, commonly in ascending order (from smallest to largest). It's named "bubble sort" because the elements "bubble" to the top of the list as the algorithm iterates through the data.

The parameters for the algorithm are

  • SCREEN: (int,int) - The dimensions of the screen given in pixels, representing the width and the height
  • N_BLOCKS: int - Total number of blocks that will be included in the array
  • MAX_HEIGHT: SCREEN[1] - Maximum height of the screen
  • W: int - Constant width of every BLOCKs in the screen
  • BLOCK: Block() - Rectangle with a constant base and variable height, and which position in the x axis reflects the BLOCK's position in the LIST_OF_BLOCK
  • LIST_OF_BLOCK: [BLOCK, ..., N_BLOCKS] - Collection of all BLOCK in the screen 
# MODULES
import random
import pygame
# DD

SCREEN = (800, 800)
display = pygame.display.set_mode(SCREEN)
N_BLOCKS = 100
MAX_HEIGHT = SCREEN[1]
W = SCREEN[0]//N_BLOCKS

# DD. BLOCK
# block = Block()
# interp. a block with a given height


class Block():
    def __init__(self, c):
        self.c = c
        self.r = 0
        self.x = self.c * W
        self.y = SCREEN[1]
        self.h = random.randint(0, MAX_HEIGHT)
        self.rect = pygame.Rect(self.x, self.y, W, self.h)

    def draw(self):
        self.rect.bottomleft = self.x, self.y
        pygame.draw.rect(display, "green", self.rect)


# DD. LIST_OF_BLOCKS
# lob = [BLOCk, ...., n=N_BLOCKS]
# interp. a collection of unsorted blocks
lob = []
for c in range(N_BLOCKS):
    block = Block(c)
    lob.append(block)

# TEMPLATE FOR LIST_OF_BLOCKS
# for block in lob:
#   ... block

The Algorithm

  • For every integer j in N_BLOCKS:
    • For every integer i in (N_BLOCKS - n - 1):
      • Is the BLOCK's height at position i BIGGER than BLOCK's height at position i+1?
        • T: Swap the position of BLOCK i and BLOCK i+1

Here's a visualization of the Travel Salesman Problem!
Let's take a look at the algorithm in action! 
# MODULES
import random
import pygame
# DD

SCREEN = (800, 800)
display = pygame.display.set_mode(SCREEN)
N_BLOCKS = 100
MAX_HEIGHT = SCREEN[1]
W = SCREEN[0]//N_BLOCKS

# DD. BLOCK
# block = Block()
# interp. a block with a given height


class Block():
    def __init__(self, c):
        self.c = c
        self.r = 0
        self.x = self.c * W
        self.y = SCREEN[1]
        self.h = random.randint(0, MAX_HEIGHT)
        self.rect = pygame.Rect(self.x, self.y, W, self.h)

    def draw(self):
        self.rect.bottomleft = self.x, self.y
        pygame.draw.rect(display, "green", self.rect)


# DD. LIST_OF_BLOCKS
# lob = [BLOCk, ...., n=N_BLOCKS]
# interp. a collection of unsorted blocks
lob = []
for c in range(N_BLOCKS):
    block = Block(c)
    lob.append(block)

# TEMPLATE FOR LIST_OF_BLOCKS
# for block in lob:
#   ... block

# CODE


def draw():
    for block in lob:
        block.draw()
    pygame.display.flip()


def swap(ia,ib):
    placeholder = lob[ia]
    lob[ia] = lob[ib]
    lob[ib] = placeholder
    lob[ia].x = ia * W
    lob[ib].x = ib * W

for j in range(len(lob)):
    for i in range(len(lob)-j-1):
        if lob[i].h > lob[i+1].h:
            swap(i, i+1)
            display.fill("#1e1e1e")
            draw()

def update():
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()

while True:
    draw()
    update()