Published on April 25, 2019
slide 1: Cal State LA CS5112 Detailed Cost Analysis of Bubble Sort Part I This is a small paper on the Bubble Sort algorithm. This paper presents code samples of different versions of the Bubble Sort algorithm. Regardless how you optimize or code the Bubble Sort algorithm it will always perform in quadratic time for the worst-case runtime. The best-case and average-case runtimes of Bubble Sort are not usually significant from a theoretical standpoint because the behavior of Bubble Sort is not interesting. Focus and understand the worst-case runtime of the Bubble Sort algorithm to gain a deeper appreciation for this simple yet inefficient algorithm. I used several good references for this paper. The references are listed at the end of this paper. Random Useless Facts About Bubble Sort These facts are taught in lectures so that your professors have something to say. The facts are not important to the actual runtime analysis of the Bubble Sort algorithm. • Bubble sort belongs to a family of algorithms known as Simple Sorts. • Bubble sort is notoriously slow. • Bubble sort runs in quadratic time. • Bubble sort algorithm is an easy to understand algorithm. • Bubble sort algorithm is an easy algorithm to implement. • Bubble sort algorithm is inefficient when dealing with large amounts of data. • Bubble sort algorithm uses two for-loops to sort data. • Bubble sort’s two for-loops can be arranged in a variety of ways but they will ultimately perform the same. Ideally name the outer loop with a variable called “outer”. Name the inner loop with a variable called “inner” you’ll see what I mean. • Bubble sort algorithm is ideal for small amounts of data. • Bubble sort algorithm sorts an array by making several passes over the array. • Bubble sort algorithm compares neighboring elements on each pass. • Bubble sort algorithm swaps the pair of elements if they are in the decreasing order assuming Bubble sort is sorting in ascending order. If no swap is required the values remain unchanged because they are already in sorted order within the array. • Bubble sort algorithm takes the largest element within an array and places it in the end of the array after the first pass. The first pass is not the same as the first comparison. • After the second pass the second-to-last element becomes the second largest element in the array. This behavior continues until the final pass with the end result being an array sorted in ascending order. • Bubble sort can also sort arrays in descending order. It would perform the same in terms of a run time analysis and the amount of time required to sort the elements. After these Useless Random Facts What Should I Focus On After reading the above factual statements you should memorize every detail of the Bubble Sort algorithm memorize every step and every assignment. Memorizing everything about the Bubble Sort algorithm will help you understand other sorting algorithms. Memorizing everything about the runtime analysis of the Bubble Sort algorithm will help you understand the run time costs of other sorting algorithms and how to figure them out. slide 2: Illustration of the Bubble sort algorithm Below is an illustration of the Bubble Sort algorithm on an array with the following elements: 2 9 5 4 8 1. The array is represented as as a rectangle and the individual elements fill the inside of the rectangle in individual squares. The following is the array image with the elements unsorted: The array is accessed using the indices. The indices could start at 0 or 1 but for arrays they usually start at 0 unless specified otherwise. For any given array of size N Bubble Sort algorithm will make N-1 passes over the array while sorting. This is the way Bubble sort operates. This behavior will not change. Find the above sorted array explanation at this link → https://github.com/xpqx/UNOFFICIAL-CS5112- Design-and-Analysis-of-Algorithms/blob/master/0_bubble_sort/sample_bubble_sort_on_array.md Bubble Sort Code Samples The following code sample is taken from Lafore’s Object-Oriented Programming in C++ 4 th ed. The code is pasted in the form of screenshots. I have added commenting to make things as easy to understand as possible. C++ uses pointers. The Bubble sort algorithm posted below makes use of pointers. Code sample taken from Chapter 10 Pointers. Analyze the Bubble Sort C++ code below and compare it with other versions of Bubble Sort. You should identify the similarities between all version of Bubble Sort to then be able to understand it and implement the algorithm on your own. slide 3: Main Function of the Bubble Sort Program in C++ Bubble Sort Code Posted Below Bubble Sort “Order” Function Posted Below Output from Bubble Sort Posted Below slide 4: The next version of the Bubble Sort algorithm comes from Liang’s Introduction to Java Programming 10 th ed. This book is pretty the perfect source for your programming needs. Liang’s Bubble Sort example is easy to understand. Liang does provide the runtime analysis of the Bubble Sort but I will provide a different more thorough runtime after I provide the all the different code samples pertaining to the Bubble Sort algorithm. Liang’s Bubble Sort Algorithm First Verion Liang offers an interesting modification to the traditional Bubble Sort algorithm. Namely he states that if no swap takes place in a pass there is no need to perform the next pass because all the elements are already sorted. This property can then be used to improve the Bubble Sort algorithm. Swap Method to Swap the Location of Two Integers Liang’s Bubble Sort Algorithm Second Version slide 5: The second version of Bubble Sort is optimized but very little. The runtime of Bubble Sort will still be quadratic. The second version of Bubble Sort just checks to see if the next pass is needed. See the optimized code below. Main Method of Bubble Sort Output from Liang’s Bubble Sort Posted Below Dale’s Bubble Sort Algorithm Dale’s interpretation of the Bubble Sort algorithm is different from previous examples. Instead of sorting for the maximum value and placing it at the end of the array Dale’s Bubble Sort algorithm finds the minimum in the array and places it in the beginning of the array. This means that instead of having the end of the array sorted with larger values Dale sorts the array from the beginning with smaller values. In the end the array will still be in ascending order assuming we are sorting in ascending order. slide 6: Dale goes on to describe the Bubble Sort algorithm in this manner: • BubbleSort • Set current to the index of the first item in the array • While more items in unsorted part of array • “Bubble up” the smallest item int eh unsorted part o Causing intermediate swaps as needed • Shrink the unsorted part of the array by incrementing the current Dale then sorts using Bubble Sort in a different way than the previous Bubble Sort examples. Despite Dale using this algorithm to sort the array the Bubble Sort will perform the same as if it were sorting the largest element and placing it at the end of the array. Bubble Sort’s performance that is its runtime will be quadratic. I have included Dale’s Bubble Sort algorithm in this example to highlight an important notion about algorithms regardless of how you code the algorithm to perform to sort using the minimum value or to sort using the maximum value Bubble Sort will always perform the same. Its performance will be slow and not as efficient as other more complex algorithms. This does not mean you do not use Bubble Sort in your program. It only means that you use it judiciously. Dale’s Bubble Sort Posted Below Dale’s bubbleUp Function to Sort the Elements that need Swapping As you can see from Dale’s bubbleUp function examines the current element and the element to its left. It then compares these two elements to see if the current element is less than the element to its left. If this is true it means the element to the left is greater than the current element. These two elements would then be swapped with the swap function. slide 7: Dale’s Swap Function Posted Below Output from Dale’s Bubble Sort Posed Below Lafore’s Bubble Sort Algorithm This is one of the versions of the Bubble Sort algorithm that I prefer. The second version I prefer is Liang’s optimized Bubble Sort algorithm. Lafore does an excellent job in describing the variables and loops in the Bubble Sort algorithm. The Bubble Sort will still perform in quadratic time but I found Lafore’s algorithm to be the easiest to understand namely because he names his variables “out” and “in”. Lafore’s Bubble Sort Algorithm Lafore’s Swap Function for Bubble Sort This is the standard swap function that has been used in previous Bubble Sort algorithms that I have listed. slide 8: Lafore’s Bubble Sort Invocation Shown Below Data elements were inserted into the array. The data elements are displayed then sorted with Bubble Sort and displayed again. Lafore’s Bubble Sort Output Posted Below After these Bubble Sort Code Samples What’s Left to Learn The various Bubble Sort algorithms posted in this paper are useful in their own ways. The goal to learn Bubble Sort is to standardized the Bubble Sort algorithm into an algorithm that is easy to understand. Recall that regardless of how you code the Bubble Sort algorithm or how you optimize the Bubble Sort algorithm it will always perform in quadratic time. Quadratic time is known to be notoriously bad because for each element that a quadratic function accepts it squares the element. For example let’s say you have a value such that n 2. If you square the 2 then you get 2 2 which is 2 x 2. This equals 4. slide 9: For a small value such as the integer 2 quadratic time does not appear problematic. For larger values quadratic time is very problematic because for each problem size a quadratic function doubles the size of the problem. How to Find the Quadratic Runtime of Bubble Sort I stated previously that Bubble Sort algorithm runs in quadratic time regardless of how it is coded. To find the running time also called runtime we examine all the steps in the code of the Bubble Sort algorithm and then calculate the cost of each step. There are several ways to calculate the costs. I will provide a detailed explanation of the costs inherit in the Bubble Sort algorithm. Liang’s Pseudocode for Bubble Sort To find the runtime of Bubble Sort algorithm we first examine a standardized version of the Bubble Sort algorithm. This version is presented as pseudocode. This paper assumes you know how to read and write pseudocode. BUBBLESORTArray A for int out 1 out A.length out++ for int in 0 in A.length – out in++ if Ai Ai +1 swap listi with listi+1 slide 10: Another Bubble Sort Pseudocode Example Here is another example of Bubble Sort pseudocode that you may have seen. It is a bit abstract and it is written differently than any code or pseudocode you may have previously seen. Regardless of this the outcome of Bubble Sort’s performance will always be the same and Bubble Sort will always perform the same. As mentioned previously the Bubble Sort algorithm will have two loops an if-statement and a swap operation that involves a variable named “temp”. The pseudocode above although slightly different from all previous Bubble Sort algorithms we have seen it will always perform the same. We can then generalize the calculation of Bubble Sort’s runtime using simple arithmetic. Bubble Sort Pseudocode Runtime Analysis Abstract Version The runtime analysis of Bubble Sort that is posted below is abstract and does not explain much. I will use it for this example. Then I will post a more detailed less abstract analysis of Bubble Sort’s runtime. The abstract explanation is what is used in lectures. Do not let the abstractness of the analysis deter you from learning how to calculate Bubble Sort’s runtime. Once you find a detailed runtime analysis understand and memorize it you will understand an abstract runtime analysis of an algorithm. slide 12: Less-Abstract Analysis of Bubble Sort’s Runtime In order to analyze Bubble Sort algorithm in a less abstract way actual code and all the steps in the code will need to be analyzed. First let’s examine the Bubble Sort algorithm in a less-abstract but not as detailed way. We’ll do this by looking at the passes and subtracting them minus a value of integers “n”. We do not know the value of “n”. “n” is just a placeholder to let us know that it is some number. Thus “n” can be 5 or 10 or another number. n-1 comparison a pass is not the same as a comparison In the first pass of Bubble Sort the number of comparisons that will be performed is some number “n” minus 1. This is usually written as n-1. It is n-1 comparisons because the largest integer in the array will be moved all the way to the end of the array after comparing and sorting as needed. n-2 comparisons a pass is not the same as a comparison In the second pass of Bubble Sort the number of comparisons that will be performed is again some number “n”. This time it is minus 2 because after the second pass there will be two integers that are already sorted at the end of the array towards the right. Since these two integers are already sorted they are excluded from the number “n” to sort. This is why it is n-2 comparisons. The integers that are excluded are the largest integer and the second to largest integer. Thus on the second pass Bubble Sort will make n-2 comparisons and the array will have two integers already sorted. n-3 comparisons a pass is not the same as a comparison On the third pass of Bubble Sort the number of comparisons that Bubble Sort will perform is again some number “n”. On the third pass it is minus 3 comparisons that will be performed. This is because there will be three integers that are already sorted and placed at the end of the array towards the right. Since these three integers are already sorted they are excluded from the number “n” to sort. This is why it is n-3 comparisons. The integers that are excluded are the largest integer and the second largest and third largest. Thus we have n-3 comparisons and on the third pass the Bubble Sort makes n-3 comparisons. Generalizing the Bubble Sort algorithm’s passes we that the Bubble Sort will perform in this manner regardless of how it is coded: − + − + − + ⋯ + + + slide 13: The Bubble Sort’s performance shown above can also be represented using this formula: 2 − This is so because in arithmetic formula 1 is equal to formula 2 and this can be proved through mathematical induction. The proof can be found online or you can try to prove it on your own using mathematical induction. For this lecture which is on the Bubble Sort algorithm we will assume that formula 1 is equal to formula 2 without proving it formally. We now have the following equation: The Bubble Sort algorithm can be said to perform at a rate of The formula above then simplifies to this is read as Big O of n squared which is understood as quadratic time. Quadratic time is the worst-case runtime of the Bubble Sort algorithm. There are other measures of an algorithm’s runtime. These measures are average-case time and best-case time. The average-case and the best-case times of an algorithm are not usually the main focus in algorithm analysis. The main focus is usually the worst-case time because an algorithm’s runtime is more helpful if we know it’s worst-case runtime. Quadratic time means that the algorithm will square in size any number of data items “n” that it must process. Thus in the worst possible case the Bubble Sort algorithm will square any number of data items “n” that it must process. Bubble Sort’s Other Runtimes Bubble Sort’s other runtimes are the average-case runtime and the best-case runtime. The best-case run time happens when the data to sort is already sorted. When is Data already Sorted If data can already be sorted when it is processed by a program then what is the point of having sorting algorithms to sort data This question can be answered by using a ubiquitous object that is familiar to many. That object is an ATM machine. ATM Scenario 1 The Perfect Customer slide 14: A customer drives up to an ATM. The customer intends to make a cash deposit. The customer sorts his dollar bills before depositing them. The ATM the customer is using sorts data items dollar bills in this case using the Bubble Sort algorithm. When the ATM processes the cash deposit by the customer the ATM uses the Bubble Sort algorithm on the items. In this particular case the ATM performs using the best-case runtime. It performs in this manner because the perfect customer sorted their data items before depositing them. ATM Scenario 2 Not Everyone is a Perfect Customer A second customer drives up to the ATM. This customer also intends to make a cash deposit. The customer does not sort their dollar bills before depositing them. Assume the ATM sorts all dollar bills by looking for the largest bill in the deposit and sorting the dollar bills from smallest to largest. The ATM uses an array to store all values of money that were deposited. The values are numbers. Although the ATM may use a physical storage unit for the money something like a small safety deposit box the ATM’s computer uses an array to store the money values that are deposited into the ATM. An array is a simple data structure. For this example the assumption is that the ATM uses an array solely to make things easy. The ATM machine also scans the dollar bills that are deposited. It scans them to determine if the monetary amounts are in sorted order. The Not-so Perfect Customer Deposits all Money in Reverse Order The Not-so Perfect Customer has deposited all of his cash in reverse order. This means that the ATM machine will have to go through all of the dollar bills before it finds the largest one at the beginning of array. The ATM machine requires that the largest dollar bill be at the end because the ATM machine sorts in ascending order using Bubble Sort. This is the worst-case scenario for a sorting algorithm. The runtime of the worst-case Bubble Sort algorithm will be quadratic time. This means that the ATM machine while using Bubble Sort to sort an array that is in reverse order will have a runtime of . Algorithms have a best-case runtime an average-case runtime and a worst-case runtime. In a different paper I will present a more detailed analysis of Bubble Sort’s runtimes as well as the proof of the formula that can be used to prove Bubble Sort’s performance. That formula is the sum of an arithmetic sequence formula which is represented in the following way: slide 15: References Liang Intro to Java Programming 10 th ed. I love this book Lafore Data Structures and Algorithms in Java 2 nd ed. I love this book Cormen Intro to Algorithms 3 rd ed. This is the book used in CS3112 and CS5112. It is also the book used in virtually all algorithm related courses. The book can be abstract so it is good to have other sources that are less abstract. Dale Object-Oriented Data Structures Using Java This book is helpful to a certain degree. Lafore Object-Oriented Programming in C++ 4 th ed. This book is good but it can be abstract. I don’t like the way Bubble sort is presented in this book.