Selection Sort in Java (With Intuition + Dry run + Code)

Why the name selection sort ?

Selection sort gets its name from the way it selects the smallest (or largest, depending on the implementation) element from the unsorted portion of the array and moves it to its correct position in the sorted portion of the array. This process is repeated until all elements are sorted.

Algorithm:

1. We start by iterating through the array from index 0 to n-1, where n is the length of the array.
2. For each iteration, we assume that the element at the current index is the smallest (min_index = i).
3. We then iterate through the rest of the array starting from i+1.
4. If we find an element smaller than the current smallest element (A[min_index]), we update min_index to the index of the new smallest element.
5. After completing the inner loop, we swap the element at index i with the smallest element found (A[min_index]).
6. This process repeats until the entire array is sorted.

I will show the working of Selection sort but make sure to dry run using pen & paper

Code

public class SelectionSort {

    public static void main(String[] args) {

        int arr[] = {7, 4, 10, 8, 3, 1};

        int len = arr.length;

        int i=0, j=0;

        for(i=0; i<len-1; i++) {
            int min = i;
            for(j=i; j<len; j++) {
                if(arr[j]<arr[min])
                    min = j;
            }

            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }


        for(int k=0; k<len; k++) {
            System.out.print(arr[k]+" ");
        }
    }

}

Time Complexity:

• Best Case: O(n^2)
• Worst Case: O(n^2)

Space Complexity:

O(1)

Wrapping Up:

Now, congrats, you’ve learnt selection sort
Thanks for reading.
Feel free to comment and like the post
Follow for more && Happy Coding

Don’t forget to check-out my other socials :
Github
Hashnode
Twitter(X)