CIS3355: Business Data Structures
Fall, 2008
 

What is a bubble Sort and How does it work?

The Basics First.

•         "Bubble Sort" is an algorithm used to sort. (Obviously since the name contains the word Sort in it)

•         The Reason it is named "Bubble Sort" is because of the way the elements sorted raise to the top of the  list.  (Like Bubbles in the Beer!!!)  

•          The Elements will be compared to their adjacent ones, substituting them in case they are larger:

In this case, 3 and 6 are adjacent elements 

    Each element will compare itself to the adjacent element, moving up the ladder in case it is larger.  In our following Matrix, I will show how the elements move

    ROUND 1    

3    6    1    0    4    2    5

                                                      [3    6]    1    0    4    2    5 - -  We ask ourselves, is 3 > 6?

                                                                                                                since 3 < 6, it stays where it's at.

                                                                                                                           We go to the following element.

    ROUND 2    

3    6    1    0    4    2    5

                                                            3    [6    1]    0    4    2    5 - - since 6 > 1, we switch places.

                                                                  3    1    [6    0]    4    2    5 - - again, 6 > 0, so we switch places.

We keep doing this until there are no more elements to switch with.

So the Final Result after our Second Round will be:

                                                                            3    1    0    4    2    5    6 - - Making 6 the largest element in this Matrix

We get ready to Start the Following Round, but at the end of every round we need to start checking from the beginning.

    ROUND 3   

 3    1    0    4    2    5    6

                      [3    1]    0    4    2    5    6 - - Is 3 > 1?

                                                                                                            since 3 > 1, we switch places.

So forth and so on.......

1    [3    0]    4    2    5    6

                                                                    1    0    [3    4]    2    5    6 - - once again we stop because 3 < 4.

1    0    3    4    2    5    6

    ROUND 4  

1    0    3    4    2    5    6

[1    0]    3    4    2    5    6

0    [1    3]    4    2    5    6

0    1    3    4    2    5    6

    ROUND 5  

0    1    3    4    2    5    6

0    1    3    [4    2]    5    6

0    1    3    2    [4    5]    6

0    1    3    2    4    5    6

    ROUND 6  

0    1    3    2    4    5    6

0    1    [3    2]    4    5    6

                                                        0    1    2    3    4    5    6 - -  BINGO!!!! Our list of Elements

                                                                Is Sorted

AND THIS IS HOW A BUBBLE SORT WORKS!!!!!!!!!

-- APPLAUSE --

REFERENCES ON THE WWW:

• http://mathbits.com/MathBits/CompSci/Arrays/Bubble.htm
• http://www-ee.eng.hawaii.edu/Courses/EE150/Book/chap10/subsection2.1.2.2.html
• http://www.scism.sbu.ac.uk/law/Section5/chap2/s5c2p13.html