ISC Practicals and Theory - Selection Sort

Selection sort is a sorting technique that arranges the elements of an array in order by repeatedly selecting the smallest element of the unsorted part and placing it at the front of that part. After each pass one more element is in its final position. This program, written in the main method of the class SelectionSort, reads an integer array of 1 to 20 elements, sorts it in ascending order, shows the array after every pass and prints the number of swaps made.

Definition

In selection sort, the array is divided into a sorted part at the left and an unsorted part at the right. 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.

For an array of $n$ elements:

• Number of passes: $n - 1$ (the last element is automatically in place).
• Comparisons: pass $i$ makes $n - 1 - i$ comparisons, so the total is $\frac{n(n - 1)}{2}$ whatever the order of the data.
• Swaps: at most $n - 1$. This program swaps only when the smallest element is not already at position $i$.

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 $n$ must be from 1 to 20. Any other value is rejected with a message.

Order: the program sorts in ascending order.

Duplicates: the comparison arr[j] < arr[min] is strict, so the first of several equal values is chosen as the smallest. Duplicates are sorted correctly (see the first sample).

Swap count: a swap is counted only when min != i.

Algorithm

1. Read the size n. If it is not from 1 to 20, print an error message and stop.
2. Read the n elements into the array arr and set swaps = 0. Print the original array.
3. For i from 0 to n - 2, i is the position to be filled in this pass:
   • set min = i, the index of the smallest element found so far;
   • for j from i + 1 to n - 1, if arr[j] < arr[min], set min = j. The comparison is strictly smaller;
   • if min != i, swap arr[i] and arr[min] using the temporary variable t and add 1 to swaps;
   • print the array after this pass.
4. Print the sorted array and the number of swaps.

Program

In main, the outer for loop fills one position in each pass and the inner for loop finds the smallest element of the unsorted part. A small for loop prints the array each time it is shown.

import java.util.Scanner;
class SelectionSort
{
    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 n = sc.nextInt();                       // the size of the array
        if (n < 1 || n > 20)                        // size outside 1 to 20 is invalid
        {
            System.out.println("Invalid size. Size must be between 1 and 20.");
        }
        else
        {
            int arr[] = new int[n];                 // the elements of the array
            System.out.println("Enter " + n + " elements:");
            for (int i = 0; i < n; i++)             // reads one element per turn
                arr[i] = sc.nextInt();
            int swaps = 0;                          // counts the number of swaps made while sorting
            System.out.print("Original array: ");
            for (int k = 0; k < n; k++)
                System.out.print(arr[k] + " ");
            System.out.println();
            for (int i = 0; i < n - 1; i++)         // i is the position to be filled in this pass
            {
                int min = i;                        // index of the smallest element found so far
                for (int j = i + 1; j < n; j++)     // scans the unsorted part
                {
                    if (arr[j] < arr[min])          // strictly smaller, so equal elements keep their order of finding
                        min = j;
                }
                if (min != i)                       // swap only when a smaller element was found
                {
                    int t = arr[i];                 // temporary variable for swapping
                    arr[i] = arr[min];
                    arr[min] = t;
                    swaps++;
                }
                System.out.print("After pass " + (i + 1) + ": ");
                for (int k = 0; k < n; k++)
                    System.out.print(arr[k] + " ");
                System.out.println();
            }
            System.out.print("Sorted array: ");
            for (int k = 0; k < n; k++)
                System.out.print(arr[k] + " ");
            System.out.println();
            System.out.println("Number of swaps: " + swaps);
        }
    }
}

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: n = 4, elements 40 30 20 10.

The outer loop runs for i = 0, 1 and 2, that is $n - 1 = 3$ passes for 4 elements. After the last pass (i = 2) the 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."
4. Count swaps and comparisons "Sort an array using selection sort and display the number of comparisons and swaps made."