Bubble sort in C/C++ (Algorithm, Pseudocode and output)
Whenever we need to arrange data in a specific order how you sort the data provided is of the utmost importance. However, in C, C++ we use many different types of Sorting Techniques to do this job and today we are going to understand one of the popular sorting techniques i.e " Bubble Sort ".
So let's get started...
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs and swaps them if they are in the wrong order. In this technique, the pass through the list is repeated until the list is sorted rather while compared with other Sorting Techniques like Merge Sort, Shell Sort, Insertion Sort, Quick Sort, Bucket Sort and Selection Sort which we have already discussed earlier. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list. Although the algorithm is simple, it is too slow and impractical for most problems even when compared to insertion sort. Bubble sort can be practical if the input is in mostly sorted order with some out-of-order elements nearly in position.
How Bubble Sort Works?
Let's take an unsorted array for our example.
Bubble sort takes Ο(n2) time so we're keeping it short and precise.
Bubble sort starts with very first two elements, comparing them to check which one is greater.
In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.
We find that 27 is smaller than 33 and these two values must be swapped.
The new array should look like this −
Next, we compare 33 and 35. We find that both are in already sorted positions.
Then we move to the next two values, 35 and 10.
We know then that 10 is smaller 35. Hence they are not sorted.
We swap these values. We find that we have reached the end of the array. After one iteration, the array should look like this −
To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.
And when there's no swap required, bubble sorts learns that an array is completely sorted.
Now let's take a look into the practical aspects of bubble sort.
Algorithm
We assume the list is an array of n elements. We further assume that the swap function swaps the values of the given array elements.
Begin
for i := 0 to size-1 do
flag := 0;
for j:= 0 to size –i – 1 do
if array[j] > array[j+1] then
swap array[j] with array[j+1]
flag := 1
done
if flag ≠ 1 then
break the loop.
done
EndPseudocode
We observe in the algorithm that Bubble Sort compares each pair of array element unless the whole array is completely sorted in ascending order. This may cause a few complexity issues like what if the array needs no more swapping as all the elements are already ascending.
To ease-out the issue, we use one flag variable swapped which will help us see if any swap has happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of the loop.
Pseudocode of BubbleSort algorithm can be written as follows −
procedure bubbleSort( list : array of items ) loop = list.count; for i = 0 to loop-1 do: swapped = false for j = 0 to loop-1 do: /* compare the adjacent elements */ if list[j] > list[j+1] then /* swap them */ swap( list[j], list[j+1] ) swapped = true end if end for /*if no number was swapped that means array is sorted now, break the loop.*/ if(not swapped) then break end if end for end procedure return list
Program of Bubble Sort in C
/* Bubble sort in C*/ #include <stdio.h> int main () { int array[100], n, c, d, swap; printf ("Enter number of elements : \n"); scanf ("%d", &n); printf ("Enter %d integers\n", n); for (c = 0; c < n; c++) scanf ("%d", &array[c]); for (c = 0; c < n - 1; c++) { for (d = 0; d < n - c - 1; d++) { if (array[d] > array[d + 1]) /* For decreasing order use '<' instead of '>' */ { swap = array[d]; array[d] = array[d + 1]; array[d + 1] = swap; } } } printf ("Sorted list in ascending order:\n"); for (c = 0; c < n; c++) printf ("%d\n", array[c]); return 0; }
Output :
Enter number of elements :
5
Enter 5 integers
15
23
56
87
12
Sorted list in ascending order:
12
15
23
56
87
...Program finished with exit code 0Program of Bubble Sort in C++
Let's say we have to sort an array in ascending order using bubble sort in C++ programming, you have to ask the user to enter the array size then ask to enter array elements, now start sorting the array elements using the bubble sort technique and display the sorted array on the screen as shown here in the following program.
Following C++ program sort the array using bubble sort technique:
/* C++ Program - Bubble Sort */ #include<iostream> using namespace std; void swapping(int &a, int &b) { //swap the content of a and b int temp; temp = a; a = b; b = temp; }
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bubbleSort(int *array, int size) {
for(int i = 0; i<size; i++) {
int swaps = 0; //flag to detect any swap is there or not
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //when the current item is bigger than next
swapping(array[j], array[j+1]);
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // No swap in this pass, so array is sorted
}
}int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
bubbleSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
Output :
When the above C++ program is compiled and executed, it will produce the following result:
Enter the number of elements: 6 Enter elements: 56 98 78 12 30 51 Array before Sorting: 56 98 78 12 30 51 Array after Sorting: 12 30 51 56 78 98
No comments
If you have any doubts, please let us Know.