A simple comparison sort that repeatedly steps through a list, swapping adjacent elements that are out of order, so that larger elements bubble toward the end; easy to explain but quadratic in time, so mostly a teaching example rather than a production sort.
Facts
Time Complexity
Time Complexity (category)Quadratic Time -- O(n^2) 1 Classification
Design Technique Credited ToEdward Harry Friend (earliest description, 1956) 2 Connections
In Field
Uses Design Technique
Sources
1. Bubble Sort (Wikipedia)
Wikipedia infobox: time complexity quadratic
quadratic
Wikipedia: design technique brute-force
brute-force
View the Source2. Wikipedia, Bubble sort
History
The earliest description of the bubble sort algorithm was in a 1956 paper by mathematician and actuary Edward Harry Friend, Sorting on electronic computer systems, published in the third issue of the third volume of the Journal of the Association for Computing Machinery (ACM), as a "Sorting exchange algorithm."
In Group: Comparison Sorting Algorithms, Lead section
comparing the current element with the one after it
View the SourceWikidata: Bubble Sort
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.