Step-by-Step Process of Selection Sort Explained

Selection sort is simple comparison based sorting algorithm.

Steps of selection sort:

1. Start with first element of array and assume it is smallest.

2. Compare this element with rest of the unsorted part of array.

3. If you find any smaller element than current smallest element then update that element as current smallest element.

4. After one full pass through unsorted part, swap the smallest element found with first unsorted element.

5. Move the boundary of sorted part to the right and repeat the process for remaining elements.

---

Java code for selection sort:

public class Solution{
    public static void main(String[] args){
        int arr[]={0,3,2,7,1,8};
        Selection_sort(arr);
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+ " ");
        } 
    }

    private static void Selection_sort(int arr[]){

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

}

1. Time Complexity:

   Best, Average and Worst case: O(N²)

   Since it involves nested loops: One for traversing the array and other for finding the minimum element in each pass.

2. Space Complexity:

   Best, Average and Worst case: O(1)

   In place sorting: no extra space needed apart from a few variables.

Why selection sort is unstable sort?

Selection sort is considered as unstable sort because if there are two identical elements in the list, selection sort might not preserve their original relative order after sorting.

During the selection process, when the smallest element is found, it is swapped with the first unsorted element. This swap can disturb the original order of identical elements.

Example:

Consider the array: [4, 5, 3, 4, 2]
Original array: [4 (a), 5, 3, 4(b), 2] (Note: The two 4 s are marked as ‘a’ and ‘b’ to distinguish them)

First Pass:
1. Find the smallest element (2) and swap it with the first element [4(a)].
2. After the first pass: [2, 5, 3, 4(b), 4(a)]
3. Notice how 4(a) was originally before 4(b), but now 4(b) is in front of 4(a).

Even though both 4 s are equal, their relative order has changed. Hence, selection sort is unstable.