Understanding Selection sort in Java

Introduction:

Sorting algorithms are a fundamental concept in computer science and are used to arrange a collection of elements in a specific order. These algorithms take an input array or list and rearrange its elements according to a predetermined comparison rule.It also makes the easy way to solve the problem.

Table of contents:

1. Why selection sort?.
2. Visual representation of selection sort.
3. Java Code for selection sort.
4. Code explanation.

1. Why selection sort?

Selection sort is one of the easiest sorting algorithms to understand and implement. It has a straightforward logic, making it a good choice for educational purposes or when simplicity is preferred over optimal performance.Selection sort performs reasonably well on small data sets or arrays with a small number of elements. Its time complexity of O(n^2) is not as significant for small input sizes, and the simplicity of the algorithm may outweigh the performance considerations.

2. Visual representation of selection sort.

Before we jump into the code let's understand the algorithm visually so that it will be easy to get a good grasp of the algorithm.

let's assume an unsorted array with the following elements.

Array = {9,1,8,4,7,2,}

Step 1: Select the maximum element in the array, in our array the maximum element id 9.

Step 2: Swap the largest element with the last element in the array

Step 3: After the elements is swapped move the right side pointer one step ahead i.e *Array.length-1 * since the largest element is moved to the end of the array.

Step 4: Repeat the above mentioned process till our window size is down to the one element in the array. Which looks like.

Seven is already in the desired place so no need to change it

Now six is swapped with four

Now four is swapped with two

Now two is swapped with one

Now all the element in the array is sorted. We get,

3. Java Code for selection sort:

The example for the selection sort looks like,

import java.util.Arrays;

public class selectionSort {
    public static void main(String[] args) {
        int[] nums = {9,1,8,4,7,2,6};
        selection(nums);
        System.out.println(Arrays.toString(nums));

    }

    public static void selection(int[] nums){
        for(int i=0;i<nums.length;i++){
            int last = nums.length-i-1;
            int maximum=maximumIndex(nums,0,last);
             swap(nums,maximum,last);
        }

        }
       static int maximumIndex(int[] nums,int start,int end){
        int max=start;
        for(int maxIndex=start;maxIndex<=end;maxIndex++){
            if(nums[max]<nums[maxIndex]){
                max=maxIndex;
            }
        }
        return max;
    }

    static void swap(int[] nums,int maximum,int last){

        int temp=nums[maximum];
        nums[maximum]=nums[last];
        nums[last]=temp;

    }


}

4. Code explanation:

Let's assume an number array with the elements 9,1,8,4,7,2,6

I always prefer writing a separate functions for each repeated task that takes place in my program and it is also a good practice it makes our code looks clean and neat. I suggest you guys to follow the same.

so i created a separate function for the sorting algorithm named as selection which takes the nums array as the argument ,

public static void selection(int[] nums){...}

Now i run a simple for loop to find the maximum element in the array i swap it with the last element in the array and move the pointer one step ahead and return the max.

static int maximumIndex(int[] nums,int start,int end){
        int max=start;
        for(int maxIndex=start;maxIndex<=end;maxIndex++){
            if(nums[max]<nums[maxIndex]){
                max=maxIndex;
            }
        }
        return max;

Again, i created a separate function for swapping the numbers named swap() which takes the nums array , maximum element and the last element of the array as arguments. In the swap array i simply swap them using three variables

static void swap(int[] nums,int maximum,int last){

        int temp=nums[maximum];
        nums[maximum]=nums[last];
        nums[last]=temp;

    }

And i simply call these two methods in the selection method and run till the end of the array using a for loop.

for(int i=0;i<nums.length;i++){
            int last = nums.length-i-1;
            int maximum=maximumIndex(nums,0,last);
             swap(nums,maximum,last);
        }

After completing these simple steps i would have achieved the sorted array and i simply display the nums array by calling the selection in the main method and print the array in the terminal.

public static void main(String[] args) {
        int[] nums = {9,1,8,4,7,2,6};
        selection(nums);
        System.out.println(Arrays.toString(nums));

    }

final Output:

[1, 2, 4, 6, 7, 8, 9]

I hope this post helps you to get a better understanding about selection sort using java.
Happy coding...😉

Comments

[Priyadharshan senthil]

Clearly explained the steps 👍🏻
Very useful