Bubble Sort

Introduction

Bubble Sort – O(n²)

Bubble sort is a very easy to code Sorting Algorithm that sorts items in an array into some order.

It could be used for :

  • Numerical Order
  • Alphabetical Order
  • Time Order

Although it is simple to code it is incredibly slow, especially for larger arrays, and so is hardly ever used. You can tell it is really efficient by looking at the n squared part of the Big 0 value above, it shows an exponential relationship!!!

  • 10 items – n² = 100
  • 100 items – n² = 10,000
  • 1000 items – n² = 1,000,000

How does Bubble Sort work?

AS & A Level – You are required to know how it works and be able to write Code / Pseudocode for the algorithm

The bubble sort algorithm works by sorting through the array in pairs.

  1. It starts at the left of the array and inspects the first two items.
  2. If the items are in the wrong order they are swapped around.
  3. The algorithm then carries on with the next pair along and so forth.
  4. When it reaches the end of the array it goes back to the beginning of the array and starts again.
  5. If it completes a full pass of the array without swapping any items it knows that the array is sorted.

Demonstration

Bubble Sort Demonstration (Using Scratch)

You can find the Scratch project page here

Python Tutorial

Bubble Sort

Bubble Sort Python Tutorial

 

Python Code

Python Code

import time,random

l = [5,7,1,4,6,2,3,5,44]

def bubble_sort(l):
    while True:
        swapped = False
        for index in range(len(l)-1):
            if l[index] > l[index+1]:
               l[index], l[index+1] = l[index+1], l[index]
               swapped = True 
            
        if swapped == False:
            return

bubble_sort(l)

print(l)

Pseudocode

 PseudoCode