**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(n^{2}) where n are no. of elements.

**How bubble sort works?**

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

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

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

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

The new array should look like this −

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

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

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

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

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 −

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

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

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.

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