Selection sort is a simple comparison-based sorting algorithm that works by dividing the input list into two parts: a sorted sublist and an unsorted sublist. The algorithm continuously selects the smallest (or largest, depending on the order) element from the unsorted sublist and moves it to the end of the sorted sublist.
Various Sorting Algorithm
- Bubble sort
- Modified Bubble Sort
- Selection sort
- Insertion sort
- Quick sort
- Merge sort
- Heap sort
Selection sort
0 1 2 3 4 5 6 7 8
38 90 47 69 52 88 71 18 20
18 20 38 38 90
18 20 38 69 52 88 71 47 90
18 20 38 47 52 88 71 69 90
69 71 88 90
The main steps of the selection sort algorithm are as follows:
- Find the Smallest Element: Find the smallest element in the unsorted sublist.
- Swap with the First Unsorted Element: Swap the smallest element found with the first element of the unsorted sublist.
- Expand the Sorted Sublist: Expand the sorted sublist by moving the boundary one element to the right.
Algorithm
The Selection Sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. Here is the algorithm for Selection Sort:
selectionSort(arr)
n = length of arr
for i from 0 to n-2
min_idx = i
for j from i+1 to n-1
if arr[j] < arr[min_idx]
min_idx = j
Swap arr[min_idx] and arr[i]
Working of Selection sort Algorithm
Certainly! Let’s walk through the Selection Sort algorithm step by step with an example and corresponding diagrams. Consider the following unsorted array:
64,25,12,22,11
- Initial Array: 64,25,12,22,11
First Pass:
- Find the minimum element in the array (11).
- Swap it with the first element (64).
- Updated array: 11,25,12,22,64
Second Pass:
- Find the minimum element in the remaining array (12).
- Swap it with the second element (25).
- Updated array: 11,12,25,22,64
Third Pass:
- Find the minimum element in the remaining array (22).
- Swap it with the third element (25).
- Updated array: 11,12,22,25,64
Fourth Pass:
- Find the minimum element in the remaining array (25).
- Swap it with the fourth element (25) (no change).
- Array remains: 11,12,22,25,64
Fifth Pass:
- The array is now fully sorted as no more swapping is required.
The following diagram illustrates the step-by-step process of the Selection Sort algorithm:
Initial Array: [64, 25, 12, 22, 11]
Pass 1: [11, 25, 12, 22, 64]
Pass 2: [11, 12, 25, 22, 64]
Pass 3: [11, 12, 22, 25, 64]
Pass 4: [11, 12, 22, 25, 64]
Pass 5: [11, 12, 22, 25, 64]
Selection sort complexity
The time complexity of the Selection Sort algorithm is as follows
| Case | Time Complexity |
|---|---|
| Best Case | O(n2) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
Best Case Time Complexity: O(n^2)
- The best case occurs when the array is already sorted. However, even in this case, the algorithm requires scanning the entire array for each element, resulting in a time complexity of O(n^2).
Average Case Time Complexity: O(n^2)
- On average, Selection Sort requires scanning the entire array for each element, resulting in a time complexity of O(n^2). This makes Selection Sort inefficient for large datasets.
Worst Case Time Complexity: O(n^2)
- The worst case occurs when the array is sorted in reverse order. In this case, the algorithm still requires scanning the entire array for each element, resulting in a time complexity of O(n^2).
Implementation of selection sort
Certainly! Below is a simple implementation of the Selection Sort algorithm in Java:
import java.util.Arrays;
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11};
System.out.println("Original array: "
+ Arrays.toString(arr));
selectionSort(arr);
System.out.println("Sorted array: "
+ Arrays.toString(arr));
}
}
