ISC Practicals and Theory - Selection Sort (OOP)

Selection sort arranges an array in order by repeatedly selecting the smallest element of the unsorted part and swapping it into the next position. This version is written in an object-oriented style: the class SelectionSort has a parameterised constructor, and separate methods read the array, find the smallest element, swap two elements, sort and display. It reads 1 to 20 integers, sorts them in ascending order, shows the array after every pass and prints the number of swaps.

Definition

In pass $i$ (counting from 0), the smallest element among arr[i] to arr[n - 1] is found and interchanged with arr[i]. After the pass, arr[0] to arr[i] are in their final places. An array of $n$ elements needs $n - 1$ passes.

Example for 40 30 20 10: pass 1 gives 10 30 20 40, pass 2 gives 10 20 30 40, and pass 3 changes nothing.

Size constraint: the size must be from 1 to 20; main checks this before the object is created.

Order: ascending.

Duplicates: arr[j] < arr[min] is strict, so the first of equal values is chosen, and duplicates are sorted correctly.

Swap count: swap() is called, and swaps increased, only when the smallest element is not already at position $i$.

Algorithm

1. In main, read the size into size. If it is less than 1 or more than 20, print an error message and stop.
2. Create the object ob with new SelectionSort(size). The constructor sets n, creates arr of that size and sets swaps to 0.
3. Call readArray(sc) to read the $n$ elements with a for loop.
4. Call display("Original array: ").
5. Call sort():
   • Outer loop: i from 0 to $n - 2$.
   • Call findMin(i), which scans arr[i + 1] to arr[n - 1] and returns the index of the smallest element; store it in m.
   • If m != i, call swap(i, m), which interchanges the two elements using t and increases swaps.
   • Call display("After pass ...").
6. Call display("Sorted array: ") and showSwaps().

Program

Each method does one job: the constructor sets up the array, readArray() reads it, findMin() returns the index of the smallest element, swap() interchanges two elements, sort() controls the passes, display() prints and showSwaps() reports the count.

import java.util.Scanner;

/**
 * Class SelectionSort stores an integer array and sorts it in
 * ascending order using the selection sort technique.
 */
class SelectionSort
{
    int arr[];      // stores the elements of the array
    int n;          // stores the size of the array
    int swaps;      // counts the number of swaps made while sorting

    /**
     * Parameterised constructor: sets the size and creates the array.
     * size : number of elements of the array
     */
    SelectionSort(int size)
    {
        n = size;
        arr = new int[n];
        swaps = 0;
    }

    /**
     * Reads the n elements of the array from the keyboard.
     * sc : Scanner object used to read the elements
     */
    void readArray(Scanner sc)
    {
        System.out.println("Enter " + n + " elements:");
        for (int i = 0; i < n; i++)             // reads one element per turn
            arr[i] = sc.nextInt();
    }

    /**
     * Displays the array on one line, preceded by the given heading.
     * msg : the heading to be printed before the elements
     */
    void display(String msg)
    {
        System.out.print(msg);
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    /**
     * Finds the smallest element in arr[start] to arr[n-1].
     * start : index from where the search begins
     * Returns the index of the smallest element.
     */
    int findMin(int start)
    {
        int min = start;                        // index of the smallest element found so far
        for (int j = start + 1; j < n; j++)
        {
            if (arr[j] < arr[min])              // strictly smaller, so the first of equal values is kept
                min = j;
        }
        return min;
    }

    /**
     * Interchanges the elements at positions a and b.
     * a, b : the two indices whose elements are swapped
     */
    void swap(int a, int b)
    {
        int t = arr[a];                         // temporary variable for swapping
        arr[a] = arr[b];
        arr[b] = t;
        swaps++;
    }

    /**
     * Sorts the array in ascending order and displays it after every pass.
     */
    void sort()
    {
        for (int i = 0; i < n - 1; i++)         // i is the position to be filled in this pass
        {
            int m = findMin(i);                 // index of the smallest element from i onwards
            if (m != i)                         // swap only when a smaller element was found
                swap(i, m);
            display("After pass " + (i + 1) + ": ");
        }
    }

    /**
     * Displays the number of swaps made.
     */
    void showSwaps()
    {
        System.out.println("Number of swaps: " + swaps);
    }

    /**
     * main reads and validates the size, creates the object
     * and calls the methods in order.
     * args : command line arguments (not used)
     */
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);    // reads input from the keyboard
        System.out.print("Enter the size of the array (1 to 20): ");
        int size = sc.nextInt();                // size entered by the user
        if (size < 1 || size > 20)              // size outside 1 to 20 is invalid
        {
            System.out.println("Invalid size. Size must be between 1 and 20.");
            return;
        }
        SelectionSort ob = new SelectionSort(size);     // object of the class
        ob.readArray(sc);
        ob.display("Original array: ");
        ob.sort();
        ob.display("Sorted array: ");
        ob.showSwaps();
    }
}

Variable description table

Sample input and output

Enter the size of the array (1 to 20): 6
Enter 6 elements:
64 25 12 22 11 25
Original array: 64 25 12 22 11 25 
After pass 1: 11 25 12 22 64 25 
After pass 2: 11 12 25 22 64 25 
After pass 3: 11 12 22 25 64 25 
After pass 4: 11 12 22 25 64 25 
After pass 5: 11 12 22 25 25 64 
Sorted array: 11 12 22 25 25 64 
Number of swaps: 4

Enter the size of the array (1 to 20): 5
Enter 5 elements:
10 20 30 40 50
Original array: 10 20 30 40 50 
After pass 1: 10 20 30 40 50 
After pass 2: 10 20 30 40 50 
After pass 3: 10 20 30 40 50 
After pass 4: 10 20 30 40 50 
Sorted array: 10 20 30 40 50 
Number of swaps: 0

Enter the size of the array (1 to 20): 4
Enter 4 elements:
40 30 20 10
Original array: 40 30 20 10 
After pass 1: 10 30 20 40 
After pass 2: 10 20 30 40 
After pass 3: 10 20 30 40 
Sorted array: 10 20 30 40 
Number of swaps: 2

Enter the size of the array (1 to 20): 1
Enter 1 elements:
15
Original array: 15 
Sorted array: 15 
Number of swaps: 0

Enter the size of the array (1 to 20): 25
Invalid size. Size must be between 1 and 20.

Dry run

Input: size = 4, elements 40 30 20 10.

The sorted array is 10 20 30 40 with 2 swaps, which matches the third sample run.

Variations

1. Descending order "Sort an integer array in descending order using the selection sort technique."
2. Strings "Sort an array of names in alphabetical order using the selection sort technique."
3. Largest element method "Sort an array in ascending order by selecting the largest element in each pass and placing it at the end."