Bubble sorting


Last week, I was teaching how to randomly pick lotto numbers using MATLAB.  The problem was that some of the numbers that were getting picked were identical.  We solved this by using comparisons until the current number picked is different from the previously selected numbers.  We blogged on this a few months ago.  But there is still an aesthetic problem of how the numbers are presented.  The numbers are not in an ascending or descending order.  This is a good time to show how to do this using the simplest (if not the most efficient) procedure called the bubble sort.

Let’s suppose someone asks you to put [8 7  9  5   4] in an ascending order.  

Starting from the first number, you compare the number with the next number, and see if it is greater.  If it is, you swap the numbers.  You continue to do this with the second number, third number and so on until the second last number.  What this does is bubble the largest number to the end. 

[8  7  9  5  4 ] -> [7  8  9  5  4]  (as 8>7) -> [7  8  9  5  4]  (as 8 is not > 9)-> [7  8  5   9   4]  (as 9 is >5) -> [7  8   5  4  9]  (as 9>4).  See how the largest number is at the end. 

Now repeat this.  [7  8   5  4  9]  -> [7  8  5  4  9] (as 7 is not >8] -> [7   5  8  4  9] (as 8>5) -> [7  5  4  8 9]  (as 8>4) ->  [7  5  4  8  9 ] (as 8 is not >9)

Now repeat this.  [ 7  5  4  8  9] -> [5  7  4  8  9] -> [ 5  4  7  8  9] -> [ 5  4  7  8  9]  -> [  5  4  7  8  9]

Now repeat this.  [5  4  7  8  9] -> [ 4  5  7  8  9] -> [ 4  5  7  8 9] -> [ 4  5  7  8   9]  -> [  4 5  7  8  9]

It looks like we are done.  If n is the number of the numbers in the array, it takes (n-1) swaps within each of the (n-1) repetitions.  So we do not have to guess how many swaps it takes or how many repetitions it takes. 

To make the bubble sort efficient, we can do the following: 1) Since with each repetition the largest number bubbles up, we may need to do less swaps.  For the first repetition, we will do (n-1) swaps, for the next repetition, we do the first (n-2) swaps, and so on.  2) We can also keep track of number of swaps taking place in a repetition.  If no swaps take place in a repetition, no more repetitions are needed.

_______________________________________________________

This post is brought to you by Holistic Numerical Methods: Numerical Methods for the STEM undergraduate at http://numericalmethods.eng.usf.edu, the textbook on Numerical Methods with Applications available from the lulu storefront, and the YouTube video lectures available at http://numericalmethods.eng.usf.edu/videos and http://www.youtube.com/numericalmethodsguy

Subscribe to the blog via a reader or email to stay updated with this blog. Let the information follow you.

Advertisements

Published by

Autar Kaw

Autar Kaw (http://autarkaw.com) is a Professor of Mechanical Engineering at the University of South Florida. He has been at USF since 1987, the same year in which he received his Ph. D. in Engineering Mechanics from Clemson University. He is a recipient of the 2012 U.S. Professor of the Year Award. With major funding from NSF, he is the principal and managing contributor in developing the multiple award-winning online open courseware for an undergraduate course in Numerical Methods. The OpenCourseWare (nm.MathForCollege.com) annually receives 1,000,000+ page views, 1,000,000+ views of the YouTube audiovisual lectures, and 150,000+ page views at the NumericalMethodsGuy blog. His current research interests include engineering education research methods, adaptive learning, open courseware, massive open online courses, flipped classrooms, and learning strategies. He has written four textbooks and 80 refereed technical papers, and his opinion editorials have appeared in the St. Petersburg Times and Tampa Tribune.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s