Bubble Sort in Every Language

Published on 29 November 2018 (Updated: 18 May 2022)

Bubble Sort in Every Language

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.

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:

  1. 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)
  2. If the elements are not in order swap them.
  3. If the end of this list has not been reached, repeat steps 1-3 again
  4. 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

Pass 2

Pass 3

Pass 4

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. To keep things simple, we split up testing into two subsets: valid and invalid. Valid tests refer to tests that occur under correct input conditions. Invalid tests refer to tests that occur on bad input (e.g., letters instead of numbers).

Valid Tests

Description List 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

Invalid Tests

Description Input
No Input
Empty Input ""
Invalid Input: Not a List "1"
Invalid Input: Wrong Format "4 5 3"

All invalid tests should spit out a usage statement in the following form:

Usage: please provide a list of at least two integers to sort in the format "1, 2, 3, 4, 5"

Articles