Sunday, May 7, 2023

How to implement Selection Sort in Java? Example Tutorial

Hello guys, if you are wondering how to implement selection sort algorithm in Java then you are at the right place. In the past, I have taught you how to implement Bubble Sort, Quick Sort, Merge Sort, Insertion Sort, Radix Sort, and Counting sort and in this article, I am going to teach you how to implement the Selection sort in Java. Along with above mentioned sorting algorithm, Selection sort is another essential Sorting algorithms which every Programmer should be aware of. This sorting algorithm is a combination of searching and sorting, and its also very intuitive especially if you have sorted things in your daily life. 

As the name suggest, it select the minimum number in the array or list and puts it into its correct position. It repeats the same steps on unsorted part until the whole array or list is sorted. It's an in place algorithm which means there is no additional space is required, but the time complexity of selection sort is O(n^2) which means you cannot use this algorithm to sort a large array.


How the Selection Sort Algorithm works?

Here is a simple explanation of Selection sort algorithms, which is intendent of any programming language:

1) Start with the first element index zero in an array and run through the second last element.
2) Find the smallest number in the array.
3) swap the first number for the smallest one. Now the smallest number is sorted
4) Repeat the process from the next element, this time find the minimum in the list excluding the first element which is already sorted.

The space complexity of the Selection Sort Algorithm is O(1) because its an in place algorithm and no additional space is required. When it comes to time complexity. It takes a quadratic algorithm which means it take O(n^2) time. This also means that as the number of elements (n) in the array increased the time to sort the array also increased exponentially which makes it unsuitable for sorting large arrays.

Here is a nice diagram which explains how Selection sort algorithm works:

how Selection sort algorithm works:





How to implement Selection Sort Algorithm in Java

Here is our complete Java Program which implement selection sort algorithm. You can play around this code to understand how selection sort actually work. Just put the breakpoint at the selectionSort() method and then step slowly to see how it find the minimum element and how it puts into its correct position. 

import java.util.Arrays;

/**
 *
 * @author Javin Paul
 */
public class PrimeFactors {

    public static void main(String args[]) {

        int[] data = getRandomArray(10);
        System.out.println("Integer array before sorting : "
                 + Arrays.toString(data));
        selectionSort(data);
        System.out.println("Integer array after sorting : " 
                 + Arrays.toString(data));

        data = getRandomArray(11);
        System.out.println("Integer array before sorting : "
                 + Arrays.toString(data));
        selectionSort(data);
        System.out.println("Integer array after sorting : " 
               + Arrays.toString(data));

    }

    public static int[] getRandomArray(int length) {
        int[] numbers = new int[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = (int) (Math.random() * 100);
        }
        return numbers;
    }

    /*
     * Sort integer array in ascending order in Java using 
     * selection sort algorithm.
     *
     */
    public static void selectionSort(int[] numbers) {

        for (int i = 0; i < numbers.length - 1; i++) {
            int min 
             = getIndexOfSmallestNumber(numbers, i, numbers.length - 1);
            swap(numbers, i, min);
        }
    }

    /*
     * Utility method to return index of smallest number from array 
     * between start and end index.
     */
    public static int getIndexOfSmallestNumber(int[] array, 
                               int startIndex, int endIndex) {
        int minimum = array[startIndex];
        int minIndex = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (array[i] < minimum) {
                minimum = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

    /*
     * Swap number between index i and j into list or array.
     */
    public static void swap(int[] list, int i, int j) {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }

}

Output:
Integer array before sorting : [69, 34, 45, 23, 86, 71, 76, 85, 16, 14]
Integer array after sorting : [14, 16, 23, 34, 45, 69, 71, 76, 85, 86]
Integer array before sorting : [43, 30, 36, 76, 16, 82, 83, 35, 37, 9, 46]


That's all about how the selection sort algorithm works and how to sort integer array using selection sort in Java. You can use the same algorithm to write a method to sort an object array, just make sure it accepts a Comparable array as input.

Other data structure and algorithm articles you may like

Thanks for reading this article so far. If you like my implementation and explanation of the iterative Quicksort algorithm in Java then please share with your friends and colleagues. If you have any questions or feedback please drop a note.

P. S.- If you want to improve your data structure and algorithm skills  then I suggest you take these best data structure and algorithms courses to quickly revise all important sorting algorithms concepts before your interview.    
By javin paul at May 07, 2023
Labels: Coding Interview Question , data structure and algorithm , Sorting algorithm

No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )