Selection Sort Algorithm
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.
Working of Selection Sort
Selection Sort works by repeatedly finding the smallest (or largest) element from the unsorted part of the array and placing it at the beginning of the sorted part.
Step-by-Step Working:
- Start from the first element.
- Find the minimum element in the entire array.
- Swap it with the first element.
- Now, the first element is sorted.
- Move to the second element and repeat the process for the remaining unsorted part of the array.
- Continue this process until the whole array is sorted.
Example of Selection Sort (According to Image Values)
Given Array:[5, 3, 8, 4, 1, 12, 7]
Pass 1:
Find smallest in [5, 3, 8, 4, 1, 12, 7] → 1
Swap with first element (5)
Result: [1, 3, 8, 4, 5, 12, 7]
Pass 2:
Find smallest in [3, 8, 4, 5, 12, 7] → 3
Already in correct place
Result: [1, 3, 8, 4, 5, 12, 7]
Pass 3:
Find smallest in [8, 4, 5, 12, 7] → 4
Swap with 8
Result: [1, 3, 4, 8, 5, 12, 7]
Pass 4:
Find smallest in [8, 5, 12, 7] → 5
Swap with 8
Result: [1, 3, 4, 5, 8, 12, 7]
Pass 5:
Find smallest in [8, 12, 7] → 7
Swap with 8
Result: [1, 3, 4, 5, 7, 12, 8]
Pass 6:
Find smallest in [12, 8] → 8
Swap with 12
Result: [1, 3, 4, 5, 7, 8, 12]
Final Sorted Array:
[1, 3, 4, 5, 7, 8, 12]
Selection Sort Java code:
public class SelectionSort {
// Function to perform Selection Sort
public static void selectionSort(int[] arr) {
int n = arr.length;
// Move boundary of unsorted subarray
for (int i = 0; i < n - 1; i++) {
// Assume current index is minimum
int minIndex = i;
// Find minimum element in remaining unsorted array
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap found minimum element with first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
// Function to print array
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
// Main method
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Before Sorting:");
printArray(arr);
selectionSort(arr);
System.out.println("After Sorting:");
printArray(arr);
}
}
Time Complexity of Selection Sort:
| Case | Time Complexity | Explanation |
| Best Case | O(n²) | It still scans the entire array to find the minimum, even if sorted. |
| Average Case | O(n²) | Always performs n(n−1)/2 comparisons regardless of input. |
| Worst Case | O(n²) | No optimization based on input ordering. |
Space Complexity:
- O (1) (in-place sorting, no extra memory used)
Note:
Selection Sort is more efficient than Bubble Sort in terms of swaps (does at most n-1 swaps), but time complexity remains quadratic, making it unsuitable for large datasets.