Bubble Sorting Algorithm

Spencer Ingermanson

The bubble sorting method is one of the most basic types of algorithms implemented to accurately place items in either ascending or descending order. According to Astrachan (2003), the algorithm was first introduced in 1959 by the name ‘exchange sort.’ For unknown reasons, a few years later (1962) a computer scientist published a journal article in which he changed the name from ‘exchange sort,’ to ‘bubble sort.’ Throughout the next few decades, many synonyms to the algorithm have been proposed (i.e., ‘sorting by repeated comparisons and exchanging,’ ‘shuttle sort’), however most computer scientists today still use the term bubble sort (Astrachan, 2003).

Bubble sorting is one of the most basic types of sorting methods. The method consists of looking at the first two items (generally starting at the left side) that are next to each other, and switching them if they are in the wrong order relative to an ascending or descending pattern. After the two items have been switched if in the wrong order, or left untouched if in the correct order, the procedure shifts one number to the right and repeats until the entire list has been sorted. The following is an example of the bubble sorting method sorting the numbers in ascending order; given the numbers, 5, 9, 2, 0, 1:

Step 1. 5, 9, 2, 0, 1

The numbers 5 and 9 are compared. Because the number 5 is less than the number 9, the numbers do not switch.

Step 2. 5, 2, 9, 0, 1

The numbers 9 and 2 are compared. Because the number 9 is greater than the number 2, the numbers switch.

Step 3. 5, 2, 0, 9, 1

The numbers 9 and 0 are compared. Because the number 0 is less than the number 9, the numbers switch.

Step 4. 5, 2, 0, 1, 9

The numbers 1 and 9 are compared. Because the number 1 is less than 9, the numbers switch.

At this point we now have 5, 2, 0, 1, 9. Because the highest number is now in the correct position, it can be ignored and the other numbers can be swapped using the same technique until all of the numbers fall in ascending order.

The bubble sorting method can be written as *О*(*n*^{2}), in which *n* represents the total number of items being sorted, whereas O represents how running time grows as *n *grows. Because *n* is squared, which significantly increases running time, bubble sorting is not efficient when dealing with a larger number of items (Hillis, 2015). Furthermore, the bubble sorting method is inefficient if the numbers are in the worst-case scenario (i.e., all the largest numbers are on the left side when sorting in ascending order from left to right), as the method would require numerous steps before all of the items are placed in the correct order. To combat these issues, a number of other algorithms are more efficient and produce the same results. One algorithm, known as the merge sorting, involves a recursion method (Hillis, 2015). The merging method involves dividing the total number of items in half and sorting those two halves in ascending order. Next, combine the two halves back together by successively taking the lowest numbered item on top of the stack and placing it in order. The merge sorting method can be written as n log n. Using the example we used with the bubble sorting method (i.e., using the number 5, 9, 2, 0, 1), here is how the merge sorting method would work:

Step 1. Divide 5, 9, 2 into one stack, and 0, 1 into another stack

Step 2. Assort 5, 9, 2, into ascending order (i.e., 2, 5, 9)

Step 3. Compare the top card of the two stacks. 0 would be compared to 2, so zero would be placed first as it is a lower number. Additionally, 1 is also smaller than 2, so 1 would be placed before 2, which would then be followed by 2, 5, and 9.

As displayed, the bubble method can be easily done manually. Due to the amount of time it takes to put a large number of items in order, and due to the possibility of the worst-case scenario, this algorithm is rarely used in programming. However, the bubble method is occasionally implemented when fixing minute computer graphics that can be adjusted with using only linear complexity (Bubble Sort, 2017).

What makes bubble sorting special and unique is its simplicity. Although it may not be the best and most efficient algorithm to use, it is an ideal technique to teach when introducing algorithms to students who have no background in computer science (e.g., the author of this paper). Many computer scientists have ridiculed teaching this method due to its potential misuse (i.e., using it when *n* is a large value; Astrachan, 2003); however if taught the drawbacks to the method, it can be the initial stepping-stone to delving into the world of algorithms and heuristics.

Switching to a first person perspective, on a personal note, I think the bubble sorting method is useful in teaching the basics to algorithms and heuristics to individuals who have no experience in computer science. Before reading the chapter, I didn’t know what an algorithm even was. However, because Hillis started as simple as possible (and used the sock analogy), I quickly learned their use. As Hillis described, and as we practiced in class, the bubble method was my first step in learning about algorithms.

Prior to writing about the bubble sorting method (perhaps the most simple algorithm out there), I was going to write about an algorithm that found variance. Because I run many ANOVAs on my cognitive psychology research team, I thought it would be very interesting to see how the programs I use (i.e., SPSS, JMP, MATLAB) can analyze variance and regression analyses. After failing to interpret any of the equations, I decided to give up on the topic and go for something more basic. However, what I did learn was that before these computer programs were developed, the job of a psychologists and a mathematician was very similar. Hopefully, once I complete more statistics, I will be able to understand and comprehend algorithms that are more complex than the bubble sorting method.

__ __

References

Astrachan, O. (2003). *Bubble sort: An archaeological algorithmic analysis *(Doctoral Dissertation). Retrieved from https://users.cs.duke.edu/~ola/papers/bubble.pdf

Bubble Sorting Method. (n.d.). In *Wikipedia.* Retrieved February 7, 2017, from https://en.wikipedia.org/wiki/Bubble_sort

Hillis, D. W. (2015). *The pattern on the stone: The simple ideas that make computers work. *New York, NY: Basic Books.