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 if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7