Functioning as a fundamental sorting algorithm, much like the way you organize playing cards, selection sort virtually divides an array into two distinct segments: a sorted part and an unsorted one. Unlike insertion sort, which focuses on finding the right position for each element, selection sort emphasizes locating the smallest (or largest) element and placing it appropriately within the sorted section.

Selection Sort Algorithm

With each iteration, the algorithm identifies the smallest element from the unsorted portion through a series of comparisons. Once located, it swaps that element with the first one in the unsorted part, effectively expanding the sorted segment. This process persists until the entire array is in its rightful order.

Working of Selection Sort algorithm

Let’s consider the example of this array to understand the working of selection sort;

arr[] = {25, 18, 5, 32, 14, 7}

Pass	Array	Explanation
1	25    18    5    32    14    7	Commencing with the initial state of the array
	5    18    25    32    14    7	The smallest element (5) is selected and swapped with 25
2	5    18    25    32    14    7	Proceeding to the next iteration, where the smallest unsorted element (7) is swapped with 18
	5    7    25    32    14    18	This leads to partial sorting within the array
3	5    7    25    32    14    18	Moving forward, the algorithm focuses on the smallest unsorted element (14), which is swapped with 25
	5    7    14    32    25    18	This results in further progress towards a sorted array
4	5    7    14    18    25    32	In the next phase, the smallest unsorted element (18) is swapped with itself
	5    7    14    18    25    32	Ultimately, the array achieves full sorting

Complexity Analysis

Time Complexity:

One loop to select an element of Array one by one = O(N), Another loop to compare that element with every other Array element = O(N). Therefore, overall complexity = O(N) * O(N) = O(N*N) = O(N²)

• Worst-case time complexity: O(n^2)
• Average-case time complexity: O(n^2)
• Best-case time complexity: O(n^2)

Space Complexity:

• Auxiliary space complexity: O(1)

In conclusion, selection sort provides a basic yet effective way of sorting an array. By consistently selecting the smallest element and placing it in the appropriate position, the algorithm gradually constructs a sorted sequence. Its simplicity makes it suitable for smaller datasets, but its quadratic time complexity can become a limitation for larger datasets. Nonetheless, understanding selection sort can provide valuable insights into sorting algorithms and their various characteristics.

Insertion sort Read More.