Bubble Sort Algorithm

Bubble sort is one of the simplest sorting algorithms. To sort an array using bubble sort,  we will compare every two elements of the array, If these two are already sorted, we will do nothing, otherwise swap them. After doing this length times array will be sorted.

Bubble Sort is a simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order. The algorithm gets its name from how smaller elements “bubble” to the top of the list during each pass.

Here’s how the algorithm works:

1. Compare the first two elements of the list. If the first element is greater than the second, swap them.
2. Compare the second and third elements of the list. If the second element is greater than the third, swap them.
3. Continue this process for the entire list until no more swaps are needed.

The algorithm makes several passes over the list until it is sorted. In each pass, it compares adjacent elements and swaps them if they are in the wrong order. After the first pass, the largest element will be at the end of the list. After the second pass, the second largest element will be in the second to last position, and so on. This process repeats until the list is fully sorted.

Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the list. This makes it inefficient for large lists, and it is generally not used in production code. However, it is a useful exercise for learning about sorting algorithms and their implementation.

Bubble sort Explanation with Example

Let the array is,

[4, 2, 3, 5, 1]

We are going to sort this array using Bubble sort.
For every iteration from 1 to 4, we will check if adjacent elements are sorted or not. If not then we will swap them.

Bubble Sorting using C

This is a C program that implements the bubble sort algorithm to sort an array of integers in ascending order.

#include <stdio.h>
int main() {
    int arr[5]={4, 2, 3, 5, 1};
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<5;j++)
        {
            if(arr[j]<arr[j-1])
            {
                int tmp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=tmp;
            }
        }
    }
    for(int i=0;i<5;i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

Here are the steps of the program:

1. Declare an integer array of size 5 and initialize it with unsorted integers: int arr[5]={4, 2, 3, 5, 1};
2. Start the outer loop with i=1 and loop through the array till i is less than 5.
3. Start the inner loop with j=1 and loop through the array till j is less than 5.
4. Compare the current element with the previous element. If the current element is smaller than the previous element, swap the elements. This is done using the if statement: if(arr[j]<arr[j-1]) { int tmp=arr[j]; arr[j]=arr[j-1]; arr[j-1]=tmp; }
5. After the inner loop completes, the largest element is placed at the end of the array. Since the largest element is now in its correct position, we can reduce the size of the inner loop by 1 for the next iteration.
6. After the outer loop completes, the array is sorted in ascending order.
7. Finally, print the sorted array using a for loop:
   for(int i=0;i<5;i++) {
printf("%d ", arr[I]);
}

The output of this program will be:

 1 2 3 4 5

Bubble Sorting using C++

This program implements the bubble sort algorithm in C++ to sort an array of 5 integers in ascending order.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5]={4, 2, 3, 5, 1};
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<5;j++)
        {
            if(arr[j]<arr[j-1])
            {
                int tmp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=tmp;
            }
        }
    }
    for(int i=0;i<5;i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}

A step-by-step explanation of the program:

1. Declare an integer array of size 5 and initialize it with some values.
   int arr[5]={4, 2, 3, 5, 1};
2. Loop through the array using two nested loops. The outer loop runs from index 1 to index 4 and the inner loop runs from index 1 to index 4.
   
   for(int i=1;i<5;i++) {
for(int j=1;j<5;j++) {
// …
}
}
3. Compare each adjacent pair of elements in the array. If the element at index j is smaller than the element at index j-1, swap the two elements.
   
   if(arr[j]<arr[j-1]) {
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}

4. After the inner loop completes, the largest element will be moved to the last index of the array. Repeat the above steps for all other elements by decrementing the limit of the outer loop by 1 each time.
   
   for(int i=1;i<5;i++) {
for(int j=1;j<5;j++) {
if(arr[j]<arr[j-1]) {
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
}
}

5. Finally, print the sorted array.
   
   for(int i=0;i<5;i++) {
   cout<<arr[i]<<” “;
   }
6. Exit the program.

Output:

 1 2 3 4 5

Bubble Sorting using Python

This is an implementation of the bubble sort algorithm in Python.

arr=[4, 2, 3, 5, 1]
for _ in range(len(arr)):
    for i in range(len(arr)-1):
        if(arr[i+1]<arr[i]):
            arr[i+1], arr[i]=arr[i], arr[i+1];

print(arr)

The code first initializes an array called arr with five elements. Then, a loop runs for the length of the array (which is 5 in this case). In each iteration of the outer loop, another loop runs from the first element to the second to the last element of the array. This inner loop compares adjacent elements of the array and swaps them if they are in the wrong order (i.e. if the second element is smaller than the first). This is done using a tuple assignment in Python.

After all the iterations of the inner loop are completed, the array should be sorted in ascending order. Finally, the sorted array is printed using the print statement.

Bubble Sorting in Java

This is a Java program that sorts an array of integers using a bubble sort algorithm.

import java.util.Arrays;
class Sort{
    public static void main(String[] args) {
        int[] arr={4, 2, 3, 5, 1};
        for(int i=0;i<5;i++)
        {
            for(int j=1;j<5;j++)
            {
                if(arr[j]<arr[j-1])
                {
                    int tmp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=tmp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

Here’s what the code does step by step:

1. Declare an integer array arr and initialize it with some unsorted values.
2. Start a nested loop to iterate over each element of the array.
3. In the outer loop, use i to keep track of the number of passes over the array. Since bubble sort requires n-1 passes to sort n elements, we will loop 5 times, which is the size of the array.
4. In the inner loop, use j to compare each adjacent pair of elements in the array and swap them if they are not in the correct order. In the first pass, the largest element will “bubble up” to the end of the array.
5. After each pass, the largest element is guaranteed to be at the end of the array, so we can shorten the inner loop by decrementing its upper bound j by i.
6. Print the sorted array using Arrays.toString().

Here’s the sorted array printed by the code:

[1, 2, 3, 4, 5].

Bubble Sorting in Javascript

This is an implementation of the bubble sort algorithm in JavaScript.

var arr=[4, 2, 3, 5, 1];
for(var i=0;i<5;i++)
{
    for(var j=1;j<5;j++){
        if(arr[j]<arr[j-1])
        {
            [ arr[j], arr[j-1] ]=[ arr[j-1], arr[j] ];
        }
    }
}
console.log(arr)

The algorithm starts with an array arr of integers to be sorted. It uses a nested loop to repeatedly compare adjacent elements and swap them if they are in the wrong order. The outer loop iterates n times, where n is the length of the array. The inner loop iterates n-1 times, because the last element of the array is already in its final position after n-1 comparisons.

Inside the inner loop, there is an if statement that checks whether the element at index j is smaller than the element at index j-1. If it is, the two elements are swapped using a destructuring assignment. The destructuring assignment is a shorthand way of swapping two variables without needing a temporary variable.

After the two loops are complete, the sorted array is printed to the console using console.log().