Bubble Sort (original) (raw)
Published on 02 December 2018 (Updated: 16 April 2025)
Welcome to the Bubble Sort page! Here, you'll find a description of the project as well as a list of sample programs written in various languages.
This article was written by:
- Jeremy Grifski
- Ron Zuckerman
Description
Bubble sort is a sorting algorithm that repeatedly cycles through a list of elements and swaps adjacent elements if they are not in order. It works as follows:
- Identify the next two adjacent elements in the list (start with the 1st and 2nd, then 2nd and 3rd, 3rd and 4th, and so on)
- If the elements are not in order swap them.
- If the end of this list has not been reached, repeat steps 1-3 again
- If any elements were swapped in the above pass, repeat steps 1-4 again
Performance
The performance of sorting algorithms is generally defined in "Big O notation". If you are not familiar with such notations, please refer to the relevant article by Rob Bell or the Wikipedia entry listed in further readings below.
Cases | Big O Notatation |
---|---|
Best case | O(n) |
Average case | O(n2) |
Worst case | O(n2) |
Bubble sort is generally not an efficient sorting algorithm; however, it does have one advantage. When the elements are already sorted, bubble sort will only pass throught the list once; whereas, most other algorithms will still perform their complete sorting process.
Example: "4, 5, 3, 1, 2"
In the example below, "pass" refers to one pass through the list (steps 1-4 one time). Each row in the pass shows a single comparison (steps 1-2 one time). The elements in bold on each line are the two being compared. If the row is labeled "swap," a swap will occur after the comparison.
Pass 1
- 4 5 3 1 2
- 4 5 3 1 2 -> swap
- 4 3 5 1 2 -> swap
- 4 3 1 5 2 -> swap
Pass 2
- 4 3 1 2 5 -> swap
- 3 4 1 2 5 -> swap
- 3 1 4 2 5 -> swap
- 3 1 2 4 5
Pass 3
- 3 1 2 4 5 -> swap
- 1 3 2 4 5 -> swap
- 1 2 3 4 5
- 1 2 3 4 5
Pass 4
- 1 2 3 4 5
- 1 2 3 4 5
- 1 2 3 4 5
- 1 2 3 4 5
Note that although the elements were sorted at the end of pass 3, the algorithm needs an additional pass without any swapping in order to know that the elements are sorted.
Requirements
Write a sample program that takes a list of numbers in the format "4, 5, 3, 1, 2". It should then sort the numbers and output them:
$ ./bubble-sort.lang "4, 5, 3, 1, 2"
1, 2, 3, 4, 5
The solution should handle duplicate elements
$ ./bubble-sort.lang "4, 5, 3, 1, 4, 2"
1, 2, 3, 4, 4, 5
In addition, there should be some error handling for situations where the user doesn't supply correct input.
Testing
Every project in the Sample Programs repo should be tested. In this section, we specify the set of tests specific to Bubble Sort. In order to keep things simple, we split up the testing as follows:
- Bubble Sort Valid Tests
- Bubble Sort Invalid Tests
Bubble Sort Valid Tests
Description | Input | Output |
---|---|---|
Sample Input | "4, 5, 3, 1, 2" | "1, 2, 3, 4, 5" |
Sample Input: With Duplicate | "4, 5, 3, 1, 4, 2" | "1, 2, 3, 4, 4, 5" |
Sample Input: Already Sorted | "1, 2, 3, 4, 5" | "1, 2, 3, 4, 5" |
Sample Input: Reverse Sorted | "9, 8, 7, 6, 5, 4, 3, 2, 1" | "1, 2, 3, 4, 5, 6, 7, 8, 9" |
Bubble Sort Invalid Tests
Description | Input |
---|---|
No Input | |
Empty Input | "" |
Invalid Input: Not A List | "1" |
Invalid Input: Wrong Format | "4 5 3" |
All of these tests should output the following:
Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5"
Articles
There are 30 articles:
- Bubble Sort in Algol68
- Bubble Sort in Awk
- Bubble Sort in Bash
- Bubble Sort in Beef
- Bubble Sort in C
- Bubble Sort in C#
- Bubble Sort in C++
- Bubble Sort in Clojure
- Bubble Sort in Commodore Basic
- Bubble Sort in Dart
- Bubble Sort in Elixir
- Bubble Sort in Erlang
- Bubble Sort in Euphoria
- Bubble Sort in Go
- Bubble Sort in Haskell
- Bubble Sort in Java
- Bubble Sort in Javascript
- Bubble Sort in Julia
- Bubble Sort in Kotlin
- Bubble Sort in Lua
- Bubble Sort in Mathematica
- Bubble Sort in Octave
- Bubble Sort in Perl
- Bubble Sort in Php
- Bubble Sort in Python
- Bubble Sort in Ruby
- Bubble Sort in Rust
- Bubble Sort in Scala
- Bubble Sort in Typescript
- Bubble Sort in Visual Basic