ISC Practicals and Theory - Bubble Sort

Bubble sort is a sorting technique that arranges array elements in ascending or descending order by repeatedly comparing adjacent elements and swapping them if they are in the wrong order. With each complete pass through the array, the largest unsorted element settles into its correct final position at the end, much like a bubble rising to the surface of water. This program reads an integer array of 1 to 20 elements, sorts it in ascending order and displays the sorted result, all inside main.

Definition

In bubble sort, adjacent elements are compared in pairs: arr[0] with arr[1], arr[1] with arr[2], and so on up to arr[n - 1 - i]. If the earlier element is greater than the later element (arr[j] > arr[j + 1]), they are interchanged using a temporary variable.

For an array of $n$ elements:

• Number of passes: at most $n - 1$ passes are needed to sort the array completely.
• Comparisons per pass: in pass $i$ (where $i$ goes from 0 to $n - 2$), exactly $n - 1 - i$ adjacent comparisons are made, because the last $i$ elements are already in their correct places.
• Total comparisons: $(n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2}$

For $n = 5$ elements, the total number of comparisons is $\frac{5 \times 4}{2} = 10$ and the number of passes is $5 - 1 = 4$.

Size constraint: the array size $n$ must be between 1 and 20. Any value outside this range is rejected with an error message.

Algorithm

1. Read the integer $n$. If $n < 1$ or $n > 20$, print an error message and stop.
2. Create the integer array arr of size $n$ and read $n$ integers using a for loop.
3. Sort the array in ascending order:
   • Outer loop: run i from 0 to $n - 2$ (the pass number).
   • Inner loop: run j from 0 to $n - 2 - i$:
     • If arr[j] > arr[j + 1], swap the two elements:
       • Set temp = arr[j].
       • Set arr[j] = arr[j + 1].
       • Set arr[j + 1] = temp.
4. Traverse the array with a for loop and print the sorted elements separated by spaces.

Program

The whole program is written in main: it reads the input, sorts the array with two nested loops and then prints it.

import java.util.Scanner;

public class BubbleSort
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of elements (1 to 20): ");
        int n = sc.nextInt();
        if (n < 1 || n > 20)
        {
            System.out.println("Invalid input. Size must be from 1 to 20.");
            return;
        }
        int[] arr = new int[n];
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++)
        {
            arr[i] = sc.nextInt();
        }

        // Bubble sort: after each pass the largest unsorted element reaches the end
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < n - 1 - i; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    // swap the adjacent elements using a temporary variable
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        System.out.println("Sorted array in ascending order:");
        for (int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Variable description table

Sample input and output

Enter the number of elements (1 to 20): 5
Enter the elements:
25 12 7 40 18
Sorted array in ascending order:
7 12 18 25 40 

Enter the number of elements (1 to 20): 4
Enter the elements:
40 30 20 10
Sorted array in ascending order:
10 20 30 40 

Enter the number of elements (1 to 20): 1
Enter the elements:
15
Sorted array in ascending order:
15 

Enter the number of elements (1 to 20): 25
Invalid input. Size must be from 1 to 20.

Dry run

Initial array: n = 5, elements [25, 12, 7, 40, 18].

After Pass 3 (4 passes and 10 comparisons in all), the array is sorted: 7 12 18 25 40. This matches the output of the first sample run.

Variations

1. Descending order "Sort an integer array in descending order using the bubble sort technique."
2. Optimised bubble sort "Modify bubble sort using a boolean flag to stop early if the array becomes sorted before all passes are complete."
3. Alphabetical string sorting "Sort an array of names in alphabetical order using the bubble sort technique."
4. Sort by frequency "Sort the elements of an array based on their frequencies using bubble sort."