Trusted answers to developer questions

Educative Answers Team

The **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.

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
`i`

with the element at`i`

+1. - If the element at â€‹position
`i`

is greater than the element at`i`

+1, then the elements are swapped.

On average, this algorithm takes $O(n^2)$ time (where *n* is the size of the array). The algorithm can be optimized to take $O(n)$, 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:

#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