Algorithm

Bubble Sort

**DISCLAIMER: This code is in C++, but the logic applies to other languages**

1) What is bubble sort?

Bubble sort is a sorting algorithm that checks adjacent numbers and swaps them if the number being checked is larger than the number ahead of it. The numbers are ordered from the bottom (end) of the list to the top (beginning). Kinda reminds me of the way bubbles rise to the surface of water *gasp!*

Visual Example:

2) An example problem:

  • Sort the numbers in the array [23, 123, 234, 54, 44, 2, 1432, 123, 8, 0].
  • Create a bubble sorting algorithm to order the numbers from least to greatest.

3) How I attempted to solve it:

  • I knew I needed to make a for-loop to iterate through the array.
  • I knew I also needed an if-statement to check if the indexed number was larger than the indexed number adjacent to the right of it.
  • My code logic* looked like this:

4) What happened?

  • This is what I got: [23, 123, 54, 44, 2, 234, 123, 8, 0, 1432, ]
  • So it seems like 1432 is in the correct position (based on the definition of bubble sort), but everything else seems to be off. I couldn’t figure out what was wrong.

5) What I ended up realizing:

  • After writing and rewriting the list and solving the sorting by hand 100 times, I realized I hadn’t even been following the structure of my own logic.
  • Once the if statement is complete, the loop iterates to the next index in the array. Therefore the number at index 0 of the array will always stay at the position. Hmm, if only there was a way to reset the loop to index 0 and run it again and again until the list was sorted…………….

6) THE FIX!!

  • There is! Another loop! I created an outer for-loop. The code now looks like this:

(I took this screenshot w/ more white space on the right so it looks better. The first screenshot is really in your face. Don’t worry, I know.)

  • I printed all the numbers returned after every iteration. This is the result:
      1. [23, 123, 54, 44, 2, 234, 123, 8, 0, 1432]
      2. [23, 54, 44, 2, 123, 123, 8, 0, 234, 1432]
      3. [23, 44, 2, 54, 123, 8, 0, 123, 234, 1432]
      4. [23, 2, 44, 54, 8, 0, 123, 123, 234, 1432]
      5. [2, 23, 44, 8, 0, 54, 123, 123, 234, 1432]
      6. [2, 23, 8, 0, 44, 54, 123, 123, 234, 1432]
      7. [2, 8, 0, 23, 44, 54, 123, 123, 234, 1432]
      8. [2, 0, 8, 23, 44, 54, 123, 123, 234, 1432]
      9. [0, 2, 8, 23, 44, 54, 123, 123, 234, 1432]

(I took out the end comma, added brackets, and numerically listed them to make it easy for y’all to read so don’t @ me. :D )

Hope this helped! Thanks for reading :)

7) Summary and run-time:

  1. Iterate through the array (inner for-loop).
  2. Check to see if the current number is greater than the one on its right (if-statement inside inner for-loop).
  3. Restart the for-loop over and over again until the list is sorted (outer for-loop).
  4. Run times:
    1. Worst Case: O(n^2)
    2. Best Case: O(n)
    3. Average Case: O(n^2)

*I wrote this code, but this isn’t the problem I was assigned. I wrote this code replaying my thought process in figuring out the solution. That is why this is an example problem.

*Also, I make lots of mistakes. There may very well be mistakes in my code even though it produces the correct output. Kindly correct me so misinformation isn’t spread. Thanks! :)

———————————— EDIT ——————————————-

This optimization for the bubble sort was provided by https://purple-slippers.tumblr.com/

“There are no mistakes in your code that I’ve noticed, but it could be optimized.

Each iteration on the inner loop (the one with the ‘i’ variable) goes through the whole array. The outer loop makes it go through the whole array multiple times. There’s no need to check the whole array every time.

Why? The largest number ALWAYS ends up at the end after first iteration. The second largest ends up before the largest one after the first iteration. It’s how bubble sorting works. The biggest ones rise to the end of the array.

Therefore, it is not necessary to check the whole array 9 times.
After ‘x’ iteration you’ll have ‘x’ largest numbers on the end of the array in the correct order.
1st iteration: largest number on end.
2nd iteration: 2 largest numbers on end in correct order.
3rd iteration: 3 largest numbers on end in correct order.

The outer loop could be used to skip these last, sorted out of sure places so it doesn’t make unnecessary comparisons.

Don’t want to take away the pleasure for solving it from you if you want to, but the answer is in the tag. :^)

Source:

chaipluscode

#oops wrong blog

#the answer ->

#for (i=0; i<10-j; i++)

#please dont take it like critique

#i just think its worth knowing

#your code and explanation are very good and understandable”

——————————————-——————————————–