Search

Sorting Algorithms: Bubble sort



The bubble sort is super simple. Got to love it, even though it's slow. It is called the bubble sort because it takes the largest elements and bubbles them up to the top of the list. Pretty simple. Here is a pretty visualization:



Thank you https://emre.me for the beautiful animation.


Let's jump into the code.


first, we need a swap function so we can swap items easily.


void swap(vector<int>& vector, int indecy1, int indecy 2){
    int holder = vector[indecy1]; //holds value at 1 in holder
    vector[indecy1] = vector[indecy2] //puts value at 2 into 1
    vector[indecy2] = holder; //puts holder value into 2
 }

If we are in c++ we can actually generalize this a little bit by using a template:

template <class Collection>
void swap (Collection& vector, int indecy1, int indecy 2){
    int holder = vector[indecy1]; //holds value at 1 in holder
    vector[indecy1] = vector[indecy2] //puts value at 2 into 1
    vector[indecy2] = holder; //puts holder value into 2
 }

but for this tutorial, we don't need to worry about that as we are just going to use a vector of integers.


Next, we need to create our bubble sort function which will compare each number with the number to the right of it and see if it's bigger. If it is, it will swap the values till we get the biggest number at the end. It could look something like this:


void bubbleSort(vector<int>& sort){
    //for the amount of items in vector
    for(int i = 0; i < sort.size(); i++){
        //for all numbers up till already sorted -1
        for(int j = 0; j < sort.size() - j - 1; j++){ 
            //if the value at j is bigger than j+1 
            if(sort[j] > sort[j + 1]){
                //switch the values
                swap(sort, j, j + 1);
             }
          }
       }
    }
    
   
                

As far as efficiency, as previously stated, it's not very fast. If you are familiar with big O notation, its speed complexity is O(n^2), but it is an easy solution to a complex problem!!


Thanks for reading!!

-Jimmy







0 views0 comments

Recent Posts

See All
follow me
  • YouTube
  • patreon
  • thingiverse
  • Instagram
Meet Jimmy
HI!! i'm jimmy, I like making things! I am a mechanical engineering student at the colorado school of mines. Welcome to my Projects site!

If you can, donations are appreciated In order to keep this page up :)

Thank You!