ISC Practicals and Theory - Bubble Sort (OOP)

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. This version is written the way ISC expects a class: the array and its size are data members, a constructor creates the array, and separate methods read, sort and display it, called on an object made in 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 must be between 1 and 20. Any value outside this range is rejected with an error message.

Algorithm

1. In main, read the size. If it is less than 1 or more than 20, print an error message and stop.
2. Create an object obj of class BubbleSort; the constructor BubbleSort(int size) stores the size in n and creates the array arr.
3. Call obj.readArray(sc) to read the $n$ elements into arr using a for loop.
4. Call obj.sort() to 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.
5. Call obj.display() to print the sorted elements separated by spaces.

Program

The constructor creates the array, readArray reads the elements, sort applies bubble sort in place, display prints the array and main creates the object and calls the methods.

import java.util.Scanner;

public class BubbleSort
{
    int arr[];    // stores the elements
    int n;        // number of elements

    // Constructor: creates the array of the given size
    BubbleSort(int size)
    {
        n = size;
        arr = new int[n];
    }

    // Reads the n elements into the array
    void readArray(Scanner sc)
    {
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++)
        {
            arr[i] = sc.nextInt();
        }
    }

    // Sorts the array in ascending order using bubble sort
    void sort()
    {
        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;
                }
            }
        }
    }

    // Displays the elements of the array
    void display()
    {
        for (int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // main: reads the size, creates the object and calls the methods
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of elements (1 to 20): ");
        int size = sc.nextInt();
        if (size < 1 || size > 20)
        {
            System.out.println("Invalid input. Size must be from 1 to 20.");
            return;
        }
        BubbleSort obj = new BubbleSort(size);
        obj.readArray(sc);
        obj.sort();
        System.out.println("Sorted array in ascending order:");
        obj.display();
    }
}

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."