Hire The World’s
Top Talent On Demand
Top Talent On Demand
AI EngineersAndroid DevelopersAngularJS DevelopersBigCommerce DevelopersC# DevelopersC++ DevelopersData Visualization DevelopersDrupal DevelopersFront-end DevelopersHTML5 DevelopersiOS DevelopersJava DevelopersKubernetes DevelopersMagento DevelopersMobile App DevelopersNode.js DevelopersOdoo DevelopersPHP DevelopersPython DevelopersQA EngineersReact.js DevelopersRemote DevelopersRuby on Rails DevelopersSalesforce ConsultantsSalesforce DevelopersShopify DevelopersSoftware DevelopersSquarespace DevelopersSvelte DevelopersTechnical WritersWeb DevelopersWebRTC DevelopersWooCommerce DevelopersWordPress DevelopersWPF Developers
Toptal connects the top 3% of freelance developers all over the world.
Bubble Sort
Animation, code, analysis, and discussion of bubble sort on 4 initial conditions.
How to use: Press “Play all”, or choose the button for the individual row/column to animate.
ALGORITHM
for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
→ invariant: a[1..i] in final position
break if not swapped
end
DISCUSSION
Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).
KEY
- Black values are sorted.
- Gray values are unsorted.
- A red triangle marks the algorithm position.
PROPERTIES
- Stable
- O(1) extra space
- O(n2) comparisons and swaps
- Adaptive: O(n) when nearly sorted