Learn Tech Skills from Scratch @ Scaler EDGE

- Courses
- Programming
- Arrays
- Bubble Sort

TUTORIAL

1. Introduction To Pointers In C/C++

2. Arrays In Programming Fundamentals

3. Pointers And Arrays

4. Pointers And 2 D Arrays

5. Array Implementation Details

6. Sorting Algorithms

7. Insertion Sort Algorithm

8. Merge Sort Algorithm

9. Quick Sort Algorithm

10. Sort Implementation Details

11. Selection Sort

12. Bubble Sort

Bubble sort is one of the simplest sorting algorithms and really intuitive to understand. We compare adjacent elements and see if their order is wrong (a[i] > a[j] for 1 <= i < j <= size of array; if array is to be in ascending order, and vice-versa). If yes, then swap them.

Let us say, we have an array of length ‘n’. To sort this array we do the above step(swapping) for n - 1 passes. In simple terms, in the ith pass, the ith largest element goes at its right place in the array by swappings. First, the largest element goes at its right place then, second largest and so on.

In a bit of mathematical terms, in ith pass, at least one element from (n - i + 1) elements from start will go at its right place. That element will be the ith (for 1 <= i <= n - 1) largest element of the array. Because in the ith pass of the array, in the jth iteration (for 1 <= j <= n - i), we are checking if a[j] > a[j + 1], and a[j] will always be greater than a[j + 1] when it is the largest element in range [1, n - i + 1]. Now we will swap it. This will continue until ith largest element is at the (n - i + 1)th position of the array.

**Let us understand the working of Bubble Sort with the help of the following example.**

**Consider the following unsorted array named Arr[ ]:**

We proceed with the first and second element i.e., Arr[0] and Arr[1]. Check if 14 > 33 which is false. So, no swapping happens and the array remains the same.

We proceed with the second and third element i.e., Arr[1] and Arr[2]. Check if 33 > 27 which is true. So, we swap Arr[1] and Arr[2].

Thus the array becomes:

We proceed with the third and fourth element i.e., Arr[2] and Arr[3]. Check if 33 > 35 which is false. So, no swapping happens and the array remains the same.

We proceed with the fourth and fifth element i.e., Arr[3] and Arr[4]. Check if 35 > 10 which is true. So, we swap Arr[3] and Arr[4].

Thus, after swapping the array becomes:

Thus, marks the end of the first pass, where the Largest element reaches its final(last) position.

Now starts the second pass.

We proceed with the first and second element i.e., Arr[0] and Arr[1]. Check if 14 > 27 which is false. So, no swapping happens and the array remains the same.

We now proceed with the second and third element i.e., Arr[1] and Arr[2]. Check if 27 > 33 which is false. So, no swapping happens and the array remains the same.

We now proceed with the third and fourth element i.e., Arr[2] and Arr[3]. Check if 33 > 10 which is true. So, we swap Arr[2] and Arr[3].

Now, the array becomes

Thus, marks the end of the second pass, where the Second Largest element reaches its final(second last) position.

Similarly,

After the third pass, the third largest element will be at the third last position in the array.

.

.

After the ith pass, the ith largest element will be at the ith last position in the array.

.

.

After the nth pass, the nth largest element(smallest element) will be at nth last position(1st position) in the array, where ‘n’ is the size of the array.

After doing all the passes, we can easily see the array will be sorted.

Thus, the sorted array will look like this:

bubbleSort( Arr[], totat_elements) for i = 0 to total_elements - 1 do: swapped = false for j = 0 to total_elements - i - 2 do: /* compare the adjacent elements */ if Arr[j] > Arr[j+1] then /* swap them */ swap(Arr[j], Arr[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

```
Implementation of bubble sort in C
#include<stdio.h>
int main()
{
int arr[] = {5, 6, 2 ,6, 9, 0, -1}, n = 7, i, j;
for(i = 0; i < n - 1; ++i)
{
int swapped = 0;
for(j = 0; j < (n - i - 1); ++j)
if(arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = 1;
}
if(!swapped)
break;
}
printf("\nArray after sorting: ");
for(i = 0; i < n; ++i)
printf("%d ", arr[i]);
return 0;
}
```

```
Implementation of Bubble sort in C++
#include <iostream>
#include <vector>
using namespace std;
void BubbleSort (vector<int> &arr, int n)
{
for (int i = 0; i < n - 1; ++i)
{
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j)
{
if (arr[j] > arr[j+1]) //check if adjacent element is
//not in order
{
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// Value at n-i-1 will be maximum of all the values below this index.
if(!swapped)
break;
}
}
int main()
{
vector<int> arr = {5, 6, 2, 6, 9, 0, -1};
int n = 7;
BubbleSort(arr, n);
// Display the sorted data.
cout << "\nSorted Data: ";
for (i = 0; i < n; i++)
Cout << arr[i] << “ “;
return 0;
}
```

```
Implementation of Bubble Sort in Java:
import java.util.Scanner;
class BubbleSort {
public static void main(String []args) {
int n;
Scanner in = new Scanner(System.in);
System.out.println("Input number of integers to sort");
n = in.nextInt();
int array[] = new int[n];
System.out.println("Enter " + n + " integers");
for (int i = 0; i < n; i++)
array[i] = in.nextInt();
for (int i = 0; i < n - 1; i++) {
Boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j+1]) /* For descending order use < */
{
int temp = array[j];
array[j]= array[j+1];
array[j+1] = temp;
swapped = true;
}
}
if(!swapped)
break;
}
System.out.println("Sorted list of numbers:");
for (int i = 0; i < n; i++)
System.out.println(array[i]);
}
}
```

```
Implementation of bubble sort in python
def bubble_sort(arr):
for i in range(len(arr) - 1):
swapped = False
for j in range(0, len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
return
arr = [int(x) for x in input(‘Enter numbers: ’).split()]
bubble_sort(arr)
print('Sorted list: ', end='')
print(arr)
```

- Scaler Academy Review
- System Design Interview Questions
- Google Interview Questions
- Facebook Interview Questions
- Amazon Interview Questions
- Microsoft Interview Questions
- SQL Interview Questions
- Python Interview Questions
- Javascript Interview Questions
- MVC Interview Questions
- React Interview Questions
- Angular Interview Questions
- Directi Interview Questions
- Yahoo Interview Questions
- LinkedIn Interview Questions
- VMware Interview Questions
- eBay Interview Questions
- Flipkart Interview Questions

Log In using

or