Home » Array Related Programs » Java Program to Sort an Array using Bubble Sort Algorithm

Java Program to Sort an Array using Bubble Sort Algorithm

Question:

Write a program to input an array of integers and sort it using Bubble Sorting Algorithm.

Theory:

Bubble sort sometimes referred to as sinking sort, is a simple sorting algorithm. This sorting algorithm is comparison based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order. The algorithm is named for the way smaller elements “bubble” to the top of the list. This algorithm is not suitable for large data sets as its average and worst case complexity are of O(n2) where n are no. of elements.

How bubble sort works?

We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we’re keeping short and precise.

bubble_sort_0

Bubble sort starts with very first two elements, comparing them to check which one is greater.

bubble_sort_1

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.

bubble_sort_2

We find that 27 is smaller than 33 and these two values must be swapped.

bubble_sort_3

The new array should look like this −

bubble_sort_4

Next we compare 33 and 35. We find that both are in already sorted positions.

bubble_sort_5

Then we move to next two values, 35 and 10.

bubble_sort_6

We know than 10 is smaller 35. Hence they are not sorted.

bubble_sort_7

We swap these values. We find that we reach at the end of the array. After one iteration the array should look like this −

bubble_sort_8

To be precise, we are now showing that how array should look like after each iteration (steps). After second iteration, it should look like this −

bubble_sort_9

Notice that after each iteration, at least one value moves at the end. After third iteration, it should look like this −

bubble_sort_10

And when there’s no swap required, bubble sorts learns that array is completely sorted. After fourth iteration, it should look like this −

bubble_sort_11

An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

Bubble-sort-example

Programming Code:

/**
* The class BubbleSorting inputs an array and sorts the elements in ascending order
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
*/

import java.util.*;
class BubbleSorting
{
    void BubbleSort(int A[]) // function to sort an array in ASCENDING ORDER implementing bubble sort technique 
    {
        int n = A.length; // finding size of the array
        int c = 0, f = 1;
        for(int i=0; i<n-1 && f==1; i++)
        {
            f = 0;
            for(int j=0; j<n-1-i; j++)
            {
                if(A[j] > A[j+1]) // for descending use if(A[j] < A[j+1])
                {
                    c = A[j];
                    A[j] = A[j+1];
                    A[j+1] = c;
                    f = 1; // setting f = 1 when swapping takes place i.e. when array is not yet sorted
                }
            }
            if(f == 0) // breaking out of the loop when array is sorted
                break;
        }
        System.out.println("The Array Sorted in Ascending order is : ");
        printArray(A);
    }
    
    /* Explanation of the above code:
     * 'i' loop is for denoting the step numbers. 
     * The maximum number of steps in which any array would get sorted is 'n-1'.
     * So if there are 5 elements in the array, then that array will take a maximum of 4 steps to get sorted.
     * f=1 would mean that the array is not sorted.
     * So f==1 condition is to continue sorting till the array is not sorted.
     * f=0 would mean that the array is sorted.
     * 'j' loop is for comparing one element with the next element i.e. element at index 0 with 1, 1 with 2 etc
     * With every step, the highest element of that step settles down at
     * its correct position i.e. the end of the array, so we need not include it in next step.
     * So, the number of comparisons in every step reduces by one.
     * If there are 5 elements then this is how comparisons take place:
     * In step 1 : 0-1, 1-2, 2-3 and 3-4
     * In step 2 : 0-1, 1-2 and 2-3
     * In step 3 : 0-1 and 1-2
     * In step 4 : 0-1
     * For this reason we have 'j<n-1-i' where as 'i' increases in every step, no of comparisons decreases by 1
     * Before the beginning of every step, we are setting f=0, assuming that the array is sorted.
     * If the array is not sorted, we are swapping the elements, and setting f=1, 
     * denoting that the array is not yet sorted and needs sorting.
     * So, if no swapping takes place, that would mean that the array is sorted and the value of f will remain 0.
     * In this case, we are breaking out of the loop and printing the sorted array.
     */

    void printArray(int A[]) // function for printing an array
    {
        int n = A.length;
        for(int i=0; i<n; i++)
        {
            System.out.print(A[i]+ " ");
        }
        System.out.println();
    }
    
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        BubbleSorting ob = new BubbleSorting();
        System.out.print("Enter the number of elements : ");
        int n = sc.nextInt();
        int A[] = new int[n];
        for(int i=0; i<n; i++)
        {
            System.out.print("Enter element "+(i+1)+" : ");
            A[i] = sc.nextInt();
        }
        System.out.println("The Original array is : ");
        ob.printArray(A);
        ob.BubbleSort(A);
    }
}

Output:

Enter the number of elements : 8
Enter element 1 : 6
Enter element 2 : 5
Enter element 3 : 3
Enter element 4 : 1
Enter element 5 : 8
Enter element 6 : 7
Enter element 7 : 2
Enter element 8 : 4
The Original array is :
6 5 3 1 8 7 2 4
The Array Sorted in Ascending order is :
1 2 3 4 5 6 7 8

Check Also

[Question 2] ISC 2017 Computer Practical Paper Solved – Quiz Result

Solution of Program 2 of ISC 2017 Computer Science Paper 2 (Practical) Exam. Java program to input the answers of each participant row-wise and calculate their marks

Leave a Reply

Your email address will not be published. Required fields are marked *