Bubble Sort

Published on 02 December 2018 (Updated: 08 October 2024)

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(n²)
Worst case	O(n²)

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 29 articles: