Learn to Code via Tutorials on Repl.it!

← Back to all posts
Bubble sort
h
k9chelsea2 (735)
so apparantly using markdown makes my tutorials better so don't mind the awful markdown your about to witness

Hello there, my last tutorial was a flop so I'm going at it again this time making sure I get all my facts correct and wording properly

Today we are going to learn about Bubble sorts, a sort (commonly known as a 'Sorting Algorithm') is basically an algorithm that arranges elements in a particular order. You will learn more about this in Computer Science.

Some more info on Sorting Algorithms:

  • The input data is commonly stored in an array or list.
  • If the elements fit the main memory it is known as a internal sorting if it exceeds the main memory it is known as external sorting
  • Typically once sorted the smaller elements end up on the left and the higher numbers on the right

A couple of points on a bubble sort:

  • The bubble sort has been around since 1956,
  • Bubble sorts are typically used to sort small, unordered data sets
  • The bubble sort is normally seen as the simplest sorting algorithm.
  • the bubble sort can also be called a sinking sort

So what is a bubble sort and how does it work?

A bubble sort basically sorts all elements from smallest to biggest by comparing two elements next to each-other to compare the value, if the value on right is higher than the one on the left nothing happens and the algorithm moves over to the next pair of numbers, if the one on the left is bigger the numbers swap. Every time the algorithm goes through all the numbers its called a pass the algorithm will keep passing through the list until it can go through the algorithm without swapping any elements.
Wikipedia sums it up as:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Now a bubble sort is not an efficient sort for plenty of reasons and you would be better of using another sort, its also inefficient in sorting large data sets, its performance is not great and is primarily used in education. However the Bubble Sort is great for teaching beginners algorithmic logic.


In example

An unordered list:
[1], [3], [64], [4], [11]
what the sort will do in this example: if number one equals more than number 2 then swap, in this case the value of the second number (3) is higher than the value of the first (1), therefore it mover on to the next set of numbers. Same as last time, the value of the first number (3) being sorted (element 2 on the list) is less than the value of the second value (64) being sorted (element 3), therefore the algorithm moves on. On the contrary to the last two times the first value (64) being compared is higher than the second (4), therefore the values swap and the algorithm move on, now as we know last round the numbers swapped so the value of the first number being compared is 64, same as last time the first number (64) being compared, has a higher value than the second value (11) so the items swap. You may have noticed this is the end of the sort, the algorithm will now go to the start of the list and go through the same process. The first value is less than the second value so we move on to the next two values, same as last time, nothing happens algorithm moves on. And if you haven't noticed already the algorithm was sorted on the first pass so the second pass swaps no elements and once it reaches the end of the list it ends.
The sorted elements now looks like: [1]. [3], [4], [11], [64]

That was a pretty simple example, well in mot cases the list will have a higher count of values (in most basic examples 10 numbers are normally sorted) and the numbers may be more randomized.


In computer terms every time a value is compared it would be a bit like:

if [value1] > [value2] {
    swap [value1] with [value2]
} else {
 swap 0
}

Yes I know thats a terrible example but thats typically the logic behind the
algorithm.

and heres the same example on its own with no explanation:
[1, 3, 64, 4, 11]

[1, 3, 64, 4, 11]

[1, 3, 4, 64, 11]

[1, 3, 4, 11, 64]

Now, nothing happens in the first two value comparisons because as mentioned before they are already in the correct order.


Back at the start of my programming journey I created this bubble sort example, now I didn't understand what was going on with the code because I was literally just doing it as an assignment and to be honest I still don't its been ages since I've used python so :/. But anyways I have linked a bubble sort down bellow (its in C++) and feel free to fork the repl and play around with the code, mess around with the values etc, you can also find many tutorials online on how do create a bubble sort in you preffered language.

In conclusion

A bubble sort is not efficient for big data sets and is not too efficient but it does the job, its also pretty slow compared to other sorts. If you want to learn more simple sorting algorithms the bucket sort or the selection sort are there. Searching algorithms are also good algorithms to learn, specially since its used in everyday programming.

Any feedback is appreciated and I hope you learnt something new

Want to learn more on bubble sorts you can go here, this, this and this might be able to help.

and yes ik it might be a tad bit confusing

Comments
hotnewtop
Bookie0 (6262)

too many lines lmfao

but cool tutorial! :)

k9chelsea2 (735)

thats what happens when I take your advice to add more markdown
jk, thank you lol