Trusted answers to developer questions
How to implement Bubble sort
Educative Answers TeamThe Bubble sort is a simple sorting algorithm that continues to swap adjacent values, if they are in the incorrect order, until all the values are sorted.
The steps in the algorithm
To sort an array of size n in ascending order, it performs n-1 iterations and in each iteration:
- It scans through the entire array.
- It compares element at index
iwith the element ati+1. - If the element at ​position
iis greater than the element ati+1, then the elements are swapped.
On average, this algorithm takes time (where n is the size of the array). The algorithm can be optimized to take , if an array is already sorted in the required order, by breaking the outer for-loop if no element is swapped in the inner for-loop.
The following illustration shows the algorithm in action:
1 of 20
Implementation
#include <iostream>
using namespace std;
int main() {
int arrayA[] = {3, 2, 1, 0};
// Finding the size of the array
auto n = end(arrayA) - begin(arrayA);
// Sorting array_A in ascending order
for(int it = 0; it < (n - 1); it++){
int flag = 0;
for(int i = 0; i < (n - 1); i++){
// Comparing adjacent elements
if(arrayA[i] > arrayA[i + 1]){
// Since the element at i is greater,
//swap elements at index i and i+1
int temp = arrayA[i];
arrayA[i] = arrayA[i + 1];
arrayA[i + 1] = temp;
flag = 1;
}
}
// Optimization. Break the outer for loop
// if no element is swapped in the inner for loop.
if(flag == 0){
break;
}
}
// Printing the sorted array
for(int i = 0; i < n; i++){
cout<< arrayA[i] << " ";
}
return 0;
}RELATED TAGS
sort
algorithms
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
