CIS3355:
Business Data Structures
Fall, 2008
|
|
|
What is a
Bubble Sort ? How Does it Work? A bubble sort is an internal exchange sort. It is considered one of the simplest methods to sort an array of objects. It is also known as a sinking sort (because the smallest items "sink" to the bottom of the array). Instead of searching an array as a whole, the bubble sort works by comparing adjacent pairs of objects in the array. If the objects are not in the correct ordered, they are swapped so that the largest of the two moves up. This process continues until the largest of the objects, eventually "bubbles" up to the highest position in the array. After this occurs, the search for the next largest object begins. The swapping continues until the whole array is in the correct order. For example: We have ten elements in an array. That means we need to make 9 comparisons so that the largest element will bubble to the top of the array. Why 9 comparisons? n = the number of elements in the array n - 1 = the number of times the comparison takes place Therefore: 10 - 1 = 9. Step 1: Compare the first two elements '4' and '7'. No switch is necessary because '4' is smaller than '7'.
Step 2: Compare second and third elements '7' and '1'.
Switch, because '7' is larger than '2'. Step 3: Compare third and fourth elements '7' and '1'.
They had to switch.
Step 4: Compare fourth and fifth elements '7' and '10'.
No switch, because they are in order.
Step 5: Compare fifth and sixth elements '10' and '8'.
They had to switch. Step 6: Compare sixth and seventh elements '10' and '3'.
They had to switch.
Step 7: Compare seventh and eighth elements '10' and '5'.
They had to switch. Step 8: Compare eighth and ninth elements '10' and '6'.
They had to switch. Step 9: Compare ninth and tenth elements '10' and '9'.
They had to switch. So, now you see that '10', the largest element has "bubbled" to the last place in the array. Now, we have to compare the remaining 9 elements until all are in order. Disadvantages: It's the slowest type of sort... Imagine comparing and swapping a list of 300 elements, analyzing pair by pair. The process gets long! Experts advise against the use of the bubble sort for repetitive sorts or sorts that contain more than a few hundred objects.
If you would like more information, use these references: 1. Bubble Sort
Would you like a challenge? Answer these questions. 1. A Bubble sort is: a) An external sort b) An algorithm c) An internal sort d) a and b are correct e) b and c are correct Answer: e 2. What are the advantages and disadvantages of using a bubble sort? Answer: Advantage: It's Simple. Disadvantages: Very time-consuming, not recommended for long searches. 3. How do you determine how many comparisons will be needed to sort the array? Answer: Use the formula n-1. Where n = the number of elements in the array. So, if you have 55 elements, you will have to compare 55-1 times.
|
