 C++ Tutorials

# C++ Tutorials

## Bubble Sort In C++ With Examples

Bubble Sort Technique In C++. Bubble Sort is the simplest of the sorting techniques. that works by repeatedly swapping the adjacent elements if they are in the wrong order.

``````#include<bits/stdc++.h>
#include<iostream>

using namespace std;

int main(){
int n;
cout<<"Enter number of array: ";
cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cout<<"Enter "<<i+1<<" number of element in the bubble sort: ";
cin>>arr[i];
}

int counter=1;
while(counter<n){
for(int i=0; i<n-counter; i++){
if(arr[i]>arr[i+1]){
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
counter++;
}
for(int i=0; i<n; i++){
cout<<arr[i]<<", ";
}
cout<<endl;

return 0 ;
}``````

## Bubble Sort In C++ with function

``````#include<bits/stdc++.h>
#include<iostream>

using namespace std;

int bubbleSort(int arr[], int n){
//N-1 large element to the end
for(int i=0; i<n-1; i++){
//Pariwise Swapping in thee unsorted of the array
for(int j=0; j<=(n-i-1); j++){
if(arr[j]>arr[j+1]){
swap(arr[j], arr[j+1]);
}
}
}
}

int main(){
int n;
cout<<"Enter number of array: ";
cin>>n;
int arr[n];
for(int i=0; i<n; i++){
cout<<"Enter "<<i+1<<" number of element in the bubble sort: ";
cin>>arr[i];
}

bubbleSort(arr, n);
for(int i=0; i<n; i++){
cout<<arr[i]<<", ";
}
cout<<endl;

return 0 ;
}``````

In a bubble sort the heaviest item sinks to the bottom of the list while the lightest one floats to the top you can imagine this process as bubbles floating to the surface of a liquid.

You can use index cards to simulate the bubble sort algorithm to create a bubble sort and C++ you will need an array to sort remember an array is a finite set of values of a single data type.

You will also need a looping structure so that you can comb through the array as many times as needed until the list is organized in order to rearrange the array elements by size you will need a conditional statement to make a size comparison between two numbers the comparison will swap numbers.

If they are out of order you will need to test each pair of adjacent numbers at least once to sort them all this could take many loop cycles for this reason bubble sort is not considered to be a very efficient sorting algorithm in order to stop the algorithm once a list is sorted.

You will need some way to let the computer know when to terminate the loop here are some code segments for you to try the array contains six elements to be sorted the boolean variable terminates the program algorithm once a loop cycle completes and no swaps are made in M is a for loop count k increments each time a swap is made during a for loop cycle.

Once a for loop cycle is completed k is reset to 0 if K remains 0 through an entire for loop ordered becomes true and a looping terminates x and y are placeholders for numbers that need to be swapped the while loop will run as long as swaps are made during one four loop cycle if a number is greater than successor if swap is made and k increments by one after six comparisons are completed k is reset to zero you.

``````// C++ program for implementation of Bubble sort
#include <bits/stdc++.h>
using namespace std;

void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)

// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
``````

C++ Bubble Sort is a very naive sorting algorithm, not one we probably want to use in the real world. But what it does is just walk through the array and every time we see elements that are out of order it just swaps that. And so if we do this enough times then we’ll eventually get our array to be sorted.

So we walk through the array swapping all the out-of-order elements and then we walk through it, and so it’s a little more sorted than it was, and then we walked through it again, swapping all the elements that are out of order, and eventually the elements kind of bubble around to where they should actually be.

Unfortunately, bubble sort is pretty slow. We could have to do as many as O of n passes through the array and each pass takes O of n time. So that’ll give us a runtime of n squared but we don’t need any extra memory to run this algorithm. So now let’s look at the implementation of it. To implement C++ Bubble Sort what we want to do is keep walking through the array as long as it’s unsorted and swap elements.

So let’s first just write out, we’re going to walk through as long as the array is not sorted. So I’m gonna have a boolean is sorted, and I’m gonna start this off as false presuming potentially that it’s not sorted initially. Now I need to walk through the array. So this is one sweep of the array and walkthrough, this from up through length -1.

Now I’m going to talk in a second about why I have this written instead of just array. length. And then if the elements are out of order if array of I is bigger than the next element, then swap those values, swap array, and plus one, ok. So the reason why I have this array -1 here is because array of i is actually going look at the next element so if I had this be array just go up to array dot length, then I’m going to get an out of bounds error on the very last element. So I need to make sure that this is array dot length -1.

And so if I did have to swap the elements then I know that my array is not sorted, so I’m gonna set that to be false again. And then I’ll exit, or I’ll enter the for a loop when is sorted is true. So basically I assume it’s sorted here and then I walk through the array. If anything is out of order, swap those elements, and then I indicate hey it’s still not sorted quite yet. And then when I exit this while loop my whole array will be sorted. So there’s one other little optimization we can make.

One thing we can notice is that at the end of the first pass the very last element in the array will actually be the correct maximum value in the array. So it will be the very last element, will be in place. And so in the next sweep, I don’t actually need to walk through the entire array, I can stop just before the last element. So what I can do here is I can say, I can say you know last unsorted, and I can set this initially equal to array dot length -1. And then after I enter them in my for loop, I just shrink the last unsorted size. Because once, as I said, once I get to the very end of the array at that first sweep, the last element will be in place. On the second sweep, the second-to-last element will be in place, on the third sweep, the third to last element.

So I can basically shrink that unsorted portion each time because these sweeps are actually pushing the last max element along in the array. So that’s how we implement bubble sort. Again, it’s a pretty inefficient algorithm and you’d rarely ever implement this although maybe in particular circumstances it could be useful.

For example, you have an array that’s sorted and one element in the array gets incremented, you might then, 1 walkthrough a bubble sort could then sort the array efficiently. But generally speaking, you probably wouldn’t use this algorithm a whole lot. But now that you’ve seen the basics of C++ Bubble Sort, why don’t you try out either implementing from scratch or applying a new sorting algorithm into a different problem.