Selection Sort

What is Selection Sort?

Selection Sort is a simple comparison-based sorting algorithm. It repeatedly selects the smallest (or largest) element from the unsorted portion of the array and swaps it with the first unsorted element. The process continues until the entire array is sorted.

How Selection Sort Works:

1. Start with the first element of the array.

2. Find the smallest element in the unsorted portion of the array.

3. Swap it with the first unsorted element.

4. Move to the next position and repeat until the array is fully sorted.

Step-by-Step Example:

Consider the array:
[29, 10, 14, 37, 13]

• First Pass:

  • Find the smallest element from [29, 10, 14, 37, 13], which is 10.

  • Swap 10 with 29.

  • The array becomes [10, 29, 14, 37, 13].

• Second Pass:

  • Find the smallest element from [29, 14, 37, 13], which is 13.

  • Swap 13 with 29.

  • The array becomes [10, 13, 14, 37, 29].

• Continue this process until the entire array is sorted.

Here is the Java Code for it

import java.util.Arrays;

//Select Minimum and put in the front of Array

public class SelectionSort {

public static void swap(int nums[],int i,int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j]=temp; }

public static void selectionSort(int nums[]) { int n = nums.length; int min = Integer.MAX_VALUE; for(int i=0;i<n-1;i++) { min=i; for(int j=i+1;j<n;j++) { if(nums[min]>nums[j]) { swap(nums,min,j); } } } }

public static void main(String[] args) { // TODO Auto-generated method stub int nums[] = {13,5,24,55,107,89,8}; selectionSort(nums); System.out.println(Arrays.toString(nums)); }

}

Time Complexity of Selection Sort:

• Best, Average, and Worst Case Time Complexity:

  • O(n²)
    Selection Sort always takes the same amount of time to sort the array, regardless of whether the array is already sorted or not. This is because it always looks through the unsorted portion of the array to find the minimum element.

• Space Complexity:

  • O(1) because it is an in-place sorting algorithm and requires a constant amount of extra memory.

Advantages and Disadvantages:

Advantages:

• Simple to implement and understand.

• Performs well on small arrays or lists.

• No additional memory is required (in-place sorting).

Disadvantages:

• Inefficient for large data sets due to its O(n²) time complexity.

• Not stable; identical elements may not preserve their relative order.