Selection Sort

Selection Sort Java Program

public class KboatSelectionSort
{
    public static void displayArray(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String args[]) {
        int arr[] = {9, 5, 2, 3};
        int n = arr.length;
        
        //Selection Sort
        for (int i = 0; i < n - 1; i++) {
            System.out.println("\nPass Number: " + (i + 1));
            int idx = i;
            for (int j = i + 1; j < n; j++) {
                System.out.println("\nComparing "+ arr[j] 
                                    + " and " + arr[idx]);
                if (arr[j] < arr[idx]) {
                    System.out.println(arr[j] 
                                       + " is less than "
                                       + arr[idx]);
                    System.out.println("Setting index of minimum element to " 
                                       + j);
                    idx = j;
                }
            }
            
            int t = arr[i];
            arr[i] = arr[idx];
            arr[idx] = t;
            
            System.out.println("\nArray After Pass Number: " + (i + 1));
            displayArray(arr);
        }
        
        System.out.println("\nSorted Array:");
        displayArray(arr);
    }
}

Output

Like Bubble Sort program, here too I have added this displayArray method and a few additional print statements to get a detailed output explaining each step of Selection Sort process. After going over the program, I will remove these print statements and show you the program to give just the sorted array as the output.

int arr[] = {9, 5, 2, 3};
int n = arr.length;

We start the main method by declaring and initializing the array arr and storing its size in int variable n. Notice that it is the same array that we used for Bubble Sort.

for (int i = 0; i < n - 1; i++) {
    System.out.println("\nPass Number: " + (i + 1));
    int idx = i;
    for (int j = i + 1; j < n; j++) {
        System.out.println("\nComparing "+ arr[j] 
                            + " and " + arr[idx]);
        if (arr[j] < arr[idx]) {
            System.out.println(arr[j] 
                                + " is less than "
                                + arr[idx]);
            System.out.println("Setting index of minimum element to " 
                                + j);
            idx = j;
        }
    }
    
    int t = arr[i];
    arr[i] = arr[idx];
    arr[idx] = t;
    
    System.out.println("\nArray After Pass Number: " + (i + 1));
    displayArray(arr);
}

After this the core Selection Sort logic starts. The outer loop controls the number of passes we make through the array. To sort an array of size n, we need to make n – 1 passes through it. Size of arr is 4 so it will take at the most 3 passes to sort it completely. So, the outer loop runs from 0 which is the starting index of the array and keeps iterating as long as i is less than n – 1. We print the pass number and then we declare an int variable idx and initialize it with i. This variable idx will hold the index of the smallest element in the unsorted part of the array. Initializing it with i means that we start the pass by assuming that the first element of the unsorted part of the array is the smallest element. Then as we will look over other elements in the inner loop, we will update the value of idx if we find an element which is smaller than the element at idx.

In the inner loop, we go over each element of the unsorted part of the array and check if it is smaller than the smallest element that we have found so far. Here, j is initialized to i + 1. The reason for this is, in each pass, the length of the sorted part increases by 1. Recall from the cards example that as we were making our passes through the cards, they were getting sorted from left to right. So, we compare the cards from i + 1 till the end of the array using the condition j < n. If the if check — if (arr[j] < arr[idx]) is true, it means that arr[j] is the smallest element we have seen so far, and we update idx accordingly.

At the end of the inner loop, we have the index of the smallest element in idx. We swap the element at index idx with the element at index i. Then we print the array just before the outer loops ends.

System.out.println("\nSorted Array:");
displayArray(arr);

Once these nested loops complete executing, our array is sorted, and we display the final sorted array as the output of the program. And with this, our Selection Sort program completes.

Don’t worry if you are still feeling a bit uncomfortable with Selection Sort. Next, we will do a dry run of the program which will make its working clear.

The int variable n gets the value of 4 as there are 4 elements in arr. The outer for loop starts by initializing i to 0. At this point the entire array is unsorted so the size of our sorted sub-array is 0. Condition of outer loop is true, so we start our first pass through the array. idx gets the value of 0. Remember, idx will hold the index of the smallest element of the unsorted sub-array. After that the inner loop starts and j is initialized to 1. arr[j] is five, arr[idx] is nine, the two are compared and as five is less than nine, we update the index of the minimum element to 1. Program control goes back to the beginning of inner for loop to compare next element. j becomes 2, condition of inner for is true. arr[j] is now two and arr[idx] is five, the two are compared and as two is less than five, we again update the index of the minimum element to 2. Next iteration of inner for loop starts, j becomes 3, condition is true so arr[3] which is 3 is compared to arr[2] which is 2. idx is not updated as 3 is greater than 2 so the condition is false. We don’t want to update idx this time as it is already pointing to the smallest element. Program control goes back to the beginning of inner for loop. j is incremented to 4. This time the condition is false so program control jumps to the statement after the inner for. The next three statements swap the values of 9 and 2. Next, we print the updated array after the swap. With this, our first pass through the array completes and we have sorted the first element of the array. Length of the sorted sub-array is now 1.

Program control goes back to the beginning of the outer for. i becomes 1. Condition is true, we start our second pass through the array. This time idx is set to 1, the index of first element of our unsorted sub-array. Inner loop starts, j becomes 2. Condition is true. arr[j] which nine is compared to arr[idx] which is five. The if condition is false so idx is not updated. In the next iteration of inner for, j becomes 3, condition is true. arr[j] is three, arr[idx] is five like before. The if condition becomes true and idx is updated to 3. Program control goes back to the beginning of inner for and increments j to 4. Loop condition becomes false and program control comes to this statement after the inner for. 5 and 3 are swapped. Its first two elements are sorted. Length of the sorted sub-array is now 2.

Program control again goes back to the beginning of the outer for. i becomes 2. Loop condition is true, we start our third pass through the array. idx is set to 2. Inner for loop begins and j is initialized to 3. Condition is true. arr[j] is five and arr[idx] is nine. Both are compared and the condition is found true. idx is updated to 3. Program control goes back to the beginning of inner for, j is incremented to 4. Condition becomes false. Inner for loop is not executed and program control comes here. 9 and 5 are swapped. These two statements again print the updated array to the console.

Program control goes back to the beginning of outer for loop and increments i to 3. This time the condition is false. Outer loop stops executing. Program control comes to the statement after the outer for loop. The sorted array is printed to the console and our program completes.

Now that we have the complete understanding of Selection Sort program, lets remove all the extra print statements and the displayArray method we added for this detailed output and just look at the Selection Sort program only.

public class KboatSelectionSort
{    
    public static void main(String args[]) {
        int arr[] = {9, 5, 2, 3};
        int n = arr.length;
        
        //Selection Sort
        for (int i = 0; i < n - 1; i++) {
            int idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[idx])
                    idx = j;
            }
            
            int t = arr[i];
            arr[i] = arr[idx];
            arr[idx] = t; 
        }
        
        System.out.println("Sorted Array:");
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output

This table summarizes the Selection Sort steps of sorting the array arr which we discussed just now. You can use this as a reference.

Bubble Sort v/s Selection Sort

Let’s conclude our discussion of sorting by comparing Bubble Sort and Selection Sort.

1. Both Bubble Sort and Selection Sort need the same number of passes through the array to sort it completely.
2. Bubble Sort compares adjacent elements and swaps them if they are in wrong order. Selection Sort selects the smallest element from unsorted sub-array and swaps it with the leftmost unsorted element.
3. Selection Sort makes fewer swaps compared to Bubble Sort which makes it a little bit faster.
4. In Bubble Sort, array is sorted from last element to first element whereas in Selection Sort, array is sorted from first element to the last element.