Click here to Skip to main content
14,028,377 members
Click here to Skip to main content
Add your own
alternative version

Stats

14.4K views
5 bookmarked
Posted 14 Jul 2016
Licenced CPOL

The Simplest Sorting Algorithm Example - Why Would Someone Use It?

, 14 Jul 2016
Rate this:
Please Sign up or sign in to vote.
Bubble Sort is great...and terrible at the same time.

Ahh Sorting Algorithms...

Such a simple problem, yet so hard to do quickly... let me rephrase that, such a simple problem, yet so hard to do quickly given large quantities of things that need sorting. There are simple solutions to this problem, and then there are complex ones, but you are going to learn about the simpliest of all sorting algorithms, Bubble Sort.

The Bubble Sort algorithm is always an interesting (sometimes painful) topic of discussion. You have some people who are new to programming, algorithms, and data structures and have no idea what Bubble Sort is, some who believe that Bubble Sort is "an abomination to the computer programming world and should never be used in any situation, so help me God!"...and then there is everyone inbetween. Whichever area of that spectrum you find yourself residing in, I welcome you to my breif discussion of this fascinating and fascinatingly simple sorting method. 

So for you newcomers, what is Bubble Sort? Bubble Sort is one of the oldest and simpliest algorithms for sorting a given set of information. In this algorithm, you compare two adjacent values in an array, if the second value is less than the first, you flip the positions of the two values. In essence, the small values will "bubble" their way to the top/front of the array, and the larger values will "sink". Do you remember in 3rd/4th grade science class when the teacher took a bunch of different liquids of varrying viscosities, put them in a container, and then shook it up? Bubble Sort works just like that. The lighter values/liquids float to the top while the heavier values/liquids sink. This process of comparing and flipping values will continue in the Bubble Sort algorithm until you have a nicely sorted list.

Sounds great, right? Well there is a reason there is a group of people that hate it more than Windows ME. Bubble Sort is the worst performing sorting algorithm, by far. I won't go into details about time complexities, but in case you are ever asked this question in Team Trivia, Bubble Sort has a time complexity of O(n^2). That is bad. When you think about what Bubble Sort is doing, like previously discussed, it is fairly easy to see why this isn't the best way to sort a list. But before you shun Bubble Sort completey, this algorithm does have some great uses, but first, lets look at this beast of an example program:

Boom, there she is. A whopping eight lines of beauty. If you are new to programming, this may seem foreign to you, so I will give you a breif rundown. The arrayToSort array is pretty straightforward in what that is and the temporaryInt variable is what we use to hold one of the values that will be swtiched when needed. The outer for loop keeps track of how many times the program has looped through the data. In this implementation of Bubble Sort, the number of times we loop through the data will always be the length of the array we are sorting - 1 (given this many iterations, we know the array will be sorted...Why? Well, just trust me on that). The inner for loop is where we iterate through the array we want sorted, starting at index 0 (first value in array), all the way to the second to last value. This loop goes to the second to last value because if went to the last value, then when we compare the last value to the next value...well there is no next value, right? Right. That is why we do that. Inside the inner for loop, we have where all the true work is done for Bubble Sort. The if statement says that if the value at index i is less than the value at index i + 1, we switch them. This is where the temporaryInt variable comes into play and it is easy to see why this is needed. In the programs given state, there is no output, but if there were, it would look something like this:

What a good looking list! So, that begs the question, when would you use this besides in your first undergrad data structures or algorithms class? The beauty of this sorting algorithm is that is simple, short, and incredibly easy to implement. I can write a Bubble Sort program in ten seconds with my eyes closed. One situationI have used Bubble Sort extensively is in testing segments of larger programs. Rather than spend a large amount of time getting a more complex sorting algorithm to work with my data, I code up Bubble Sort quickly and continue working on more pertinent sections of a program. This allows me to build prototypes and test code segments quicker. When I get the program working, I go back and change it to a quicker sorting algorithm. Since the output of a sorting algorithm is always the same, given it works correctly, it really doesn't matter if it is fast to start with. Similar to the saying, "Rome wasn't build in a day", it can be very benefitial to start simply, sacrifice efficiency, and after you get your program working, polish it off with more efficient sorting algorithms. Trust me, this can save you many headaches, especially when working on large projects.

Besides that, Bubble Sort can also be beneficial in situations where you know you will always have a small number of elements to sort, or where you know the elements will always be almost sorted. A faster sorting algorithm may still be faster in these situation, but it is rather pointless to implement them when given that information. It either won't be worth the program space, programmer time, or you would never notice the time difference. Think about it this way...if you lived a block away from the store, would you buy a Ferrari just to make your drive there shorter? No, you wouldn't (the normal person wouldn't anyway). Even though your Honda Civic is significantly slower than a Ferrari, it just wouldn't be worth the investment...and let's be honest, you wouldn't really notice a time difference either. 

There can be a lot of beauty in simply things, and Bubble Sort is no exception. I have been programming for years, and still find many situations where Bubble Sort can be beneficial. Even though it isn't the most efficient sorting algorithm there is, it is still important to understand it and know how you can apply it.

If you have made it this far, thank you. This is my first article of many to come. Topics include, algorithms, machine learning, computer vision, and the like. I appreciate all feedback and I always love have great conversations with new people.

 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

dcmuggins
Student
United States United States
Current graduate student at Southern Methodist University in the Computer Science program (Go Mustangs).
Undergraduate degree in Computer Science with a focus on Biometrics from Davenport University (Go Panthers).

You may also be interested in...

Comments and Discussions

 
QuestionIf you are going to do this. Pin
leon de boer9-Nov-16 8:50
memberleon de boer9-Nov-16 8:50 
QuestionAbout the interest of such algorithms Pin
richard.guzik26-Jul-16 5:21
memberrichard.guzik26-Jul-16 5:21 
GeneralMy vote of 5 Pin
Oshtri Deka20-Jul-16 22:44
professionalOshtri Deka20-Jul-16 22:44 
QuestionGood article, regardless Pin
Member 1081603819-Jul-16 4:37
memberMember 1081603819-Jul-16 4:37 
QuestionNice to review the basics Pin
Bob100018-Jul-16 9:56
professionalBob100018-Jul-16 9:56 
QuestionAuthor needs to learn how to use a spell checker Pin
Member 1172588118-Jul-16 7:55
memberMember 1172588118-Jul-16 7:55 
GeneralMy vote of 3 Pin
Member 1172588118-Jul-16 7:54
memberMember 1172588118-Jul-16 7:54 
GeneralMy vote of 2 PinPopular
Rob Grainger14-Jul-16 22:15
memberRob Grainger14-Jul-16 22:15 
GeneralRe: My vote of 2 Pin
SteveHolle15-Jul-16 4:01
memberSteveHolle15-Jul-16 4:01 
GeneralRe: My vote of 2 PinPopular
Rob Grainger15-Jul-16 5:09
memberRob Grainger15-Jul-16 5:09 
GeneralRe: My vote of 2 Pin
chaz-chance18-Jul-16 3:07
memberchaz-chance18-Jul-16 3:07 
GeneralRe: My vote of 2 Pin
dcmuggins18-Jul-16 3:22
professionaldcmuggins18-Jul-16 3:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web05 | 2.8.190419.4 | Last Updated 15 Jul 2016
Article Copyright 2016 by dcmuggins
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid