category: 

Every programming language has its own share of sorting algorithms, and C++ is no different. Despite the differences between these algorithms, the need for consistently sorted results is a constant in a wide variety of applications. We will introduce you to bubble sort C++.

Bubble sort C++ is the simplest of all sorting methods. As such, it’s the easiest to implement in the broadest range of contexts.

Learning Bubble Sort in C++ is a crucial step towards gaining familiarity with sorting methods in object-oriented programming and provides a stable framework from which you can learn more advanced sorting methods.

How Does Bubble Sort C++ Work?

Bubble sort is a simple way of sorting numerical items in ascending or descending order. It works by comparing two adjacent elements in an array and then swapping them if they are out of order.

It’s easy to understand why this process is called Bubble Sort. Think of the bubbles in those cool old-timey glass bottles Coca-Cola used to come in. Opening up the bottle creates a pressure difference that forces CO2 out of the liquid beverage. Smaller bubbles fly right to the top while larger, heavier bubbles float slowly.

Bubble sort C++ works in a similar way. When used to sort in descending order, it causes the smallest, lightest list elements to bubble to the top of the list while larger, heavier list elements sink to the bottom. This simple description will help you determine whether your bubble sort code is running correctly in your compiler.

Since Bubble Sort works by moving list items one at a time until they are in the proper order, the algorithm needs to scan the list several times. Each scan is called a loop count (because the algorithm loops around to rescan the list each time). Because of this, bubble sort can become impractical when dealing with large numbers of elements, or multiple arrays.

On the first pass, Bubble Sort compares each element with its neighbors in the array, one at a time, exchanging them if necessary along the way. This way, the smallest element (in descending order) floats immediately to the top of the list on the first pass. On the second pass, the next-smallest element makes it to its proper place, and so on.

Importantly, the algorithm avoids the elements it has already sorted on each pass so that its passes get smaller and smaller until the process is complete.

Example of Bubble Sort C++ in Code

There are multiple ways to code for Bubble Sort. Here is one example of what Bubble Sort looks like in C++. Pay special attention the bolded comments (denoted with //), which tell you what’s going on in that particular part of the code.

    
    #include
    using namespace std; 
    int main(){

     //declaring array

    int array[5]; 
    cout>array[i];
     }

     coutarray[j+1])
          {
            temp=array[j];
            array[j]=array[j+1];
            array[j+1]=temp;
          }
        }
      }

      // Displaying Sorted array
      cout

Example of How Bubble Sort C++ Arranges Elements in an Array

If you enter an input array using the numbers 54, 64, 11, 36, and 25. Your array would like so before the first pass:


Value of 0 at Index: 54
Value of 1 at Index: 64
Value of 2 at Index: 11
Value of 3 at Index: 36
Value of 4 at Index: 25

During each pass, the algorithm compares each individual array element named array(j) and array(j+1) as it moves up the list. Since the code above is designed to sort in ascending order, after the first pass, the array would look like this:


Value of 0 at Index: 54
Value of 1 at Index: 11
Value of 2 at Index: 36
Value of 3 at Index: 25
Value of 4 at Index: 64

As you can see, it swapped 64 with 54 and then dragged 64 all the up to the top value. During this pass, j=0, so it’s the 0 element that floats to the top of the array. After the following pass where j=1, the result would look like this:


Value of 0 at Index: 11
Value of 1 at Index: 36
Value of 2 at Index: 25
Value of 3 at Index: 54
Value of 4 at Index: 64

The next pass, j=2, will be the final one needed for this particular array. Even though the code will continue running, the condition for each iteration will be FALSE because the requiring sorting is complete.

Optimizing the Bubble Sort Algorithm in C++

You can optimize sorting by stopping the algorithm if the inner loop doesn’t cause a swap. Input this code right after the standard namespace and before the main program:

    
        Void arr_sort(int* array, const int arr_size){
        int temp = 0;   //Temporary integer stores the current element if necessary
        int end = 0;    //Runtime condition

        while(end++ != arr_size){ // Maximum of 10 loops

           for(int i = 0; i  array[i + 1]){    //If the current element 
                   temp = array[i];    //is larger than the next
                   array[i] = array[i + 1]; //It will change its position
                   array[i + 1] = temp;    
               }
           }
        }
        }
    

This is one way of improving bubble sort behavior, but it isn’t the only way. This code sorts the array until end has the same value as arr_size. In many situations, the program won’t necessarily need to run that long for sorting to occur.

Boolean functions give you even greater control over the start and stop points of the code. By setting a Boolean function to determine whether the for loop is true or false and verifying the function after each for loop, you can set the program to break out of the loop as soon as sorting is complete.

There are multiple ways to do this, but the most intuitive is this way:

    
        while(end++ != arr_size){ // Maximum of 10 loops

           bool swapped = false;
           for(int i = 0; i  array[i + 1]){    //If the current element 
                   temp = array[i];    //is larger than the next
                   array[i] = array[i + 1]; //It will change its position
                   array[i + 1] = temp;
                   swapped = true;    
               }
           }
           if (!swapped) break;
        }
    

Another, more advanced method for optimizing Bubble Sort in C++ reduces iterations by inserting two variables, i and j, and then using an i=j+1 statement to identify when swapping occurs. For example, with a six-element array:

    
            int main()
            {
                int t;
            
                int c[6] = { 54, 64, 11, 36, 25, 3 };
                int counter = 0;
                for (int i = 0; ic[j])
            
                        {
                            t = c[i];
                            c[i] = c[j];
                            c[j] = t;        
                        }
                    }        
                }
            
                cout 

With this code, the j=i+1 association prevents the loop from running from 0 with every instance of the inner loop, saving the counter from running the otherwise useless 0 iteration.

However, using this optimization requires that the element of the index given by the main loop is at an exact, fixed place every time the inner loop finishes. If the element of at the current index changes position, the program won’t run correctly.

The rest of the code, located inside the body of the if statement, brings the current value to a fixed position and keeps it from moving. If a standard non-optimized code would use 36 iterations to sort 6 array elements, this optimized version will cut that number down to 21.

Another method for optimizing bubble sort in C++ tells the algorithm to remember where it made its last swap:

    
            int main(){

                    int counter = 0;
                
                    int a[6] = { 54, 64, 11, 36, 25, 3 };
                
                    int lastSwap = 6 - 1;
                    for (int i = 1; i  a[j + 1]) {
                                int temp = a[j];
                                a[j] = a[j + 1];
                                a[j + 1] = temp;
                                is_sorted = false;
                                currentSwap = j;
                            }
                        } 
                
                
                        if (is_sorted) 
                        lastSwap = currentSwap;
                    }
                    cout 

This is a practical solution for finding large elements that are already in the correct order, which can save on iterations since any random data set is likely to have some elements already in sorted order purely by chance.

Tags: 

Pin It on Pinterest

Share This