Selection Sort

• Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.
• The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted part. This process is repeated for the remaining unsorted portion until the entire list is sorted.

Advantages of Selection Sort Algorithm:

• Simple and easy to understand.
• Works well with small datasets.

Disadvantages of the Selection Sort Algorithm:

• Selection sort has a time complexity of O(n^2) in the worst and average case.
• Does not work well on large datasets.
• Does not preserve the relative order of items with equal keys which means it is not stables.

Working of Selection sort Algorithm:

Let’s take an unsorted array. It will be easier to understand the Selection sort with an example.

Step 1:

At present, 12 is stored at the first position, after searching the entire array, it is found that 8 is the smallest value.

Step 2:

So, swap 12 with 8. After the first iteration, 8 will appear at the first position in the sorted array.

Step 3:

For the second position, where 29 is stored presently, we again sequentially scan the rest of the items of unsorted array. After scanning, we find that 12 is the second lowest element in the array that should be appeared at second position

Step 4:

Now, swap 29 with 12. After the second iteration, 12 will appear at the second position in the sorted array. So, after two iterations, the two smallest values are placed at the beginning in a sorted way.

Step 5:

The same process is applied to the rest of the array elements.

Now, the array is completely sorted.

Selection Sort Code in Java:

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("Original array:");
        printArray(arr);
        
        selectionSort(arr);
        
        System.out.println("Sorted array:");
        printArray(arr);
    }

    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in unsorted array
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Output:

Original array:
12 11 13 5 6 
Sorted array:
5 6 11 12 13 

Complexity Analysis of Selection Sort:

The time complexity and space complexity of the Selection Sort algorithm are as follows:

1. Time Complexity:
   • The time complexity of Selection Sort is O(n^2), where n is the number of elements in the array.
   • This is because the algorithm consists of two nested loops. The outer loop runs n – 1 times, and the inner loop runs (n – 1), (n – 2), (n – 3), …, 2, 1 times.
   • The number of comparisons made by the algorithm is roughly n*(n-1)/2, which simplifies to O(n^2) when considering the dominating terms.
2. Space Complexity:
   • The space complexity of Selection Sort is O(1), meaning it requires constant extra space.
   • This is because the algorithm sorts the array in-place, without requiring additional data structures proportional to the input size.
   • Regardless of the size of the input array, the amount of extra space used by the algorithm remains constant. Therefore, the space complexity is O(1).