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.
- It starts at the left of the array and inspects the first two items.
- If the items are in the wrong order they are swapped around.
- The algorithm then carries on with the next pair along and so forth.
- When it reaches the end of the array it goes back to the beginning of the array and starts again.
- If it completes a full pass of the array without swapping any items it knows that the array is sorted.
Bubble Sort Demonstration (Using Scratch)
Bubble Sort Python Tutorial