Selection Sort – Data Structure and Algorithm

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}

125    18    5    32    14    7Commencing with the initial state of the array
5    18    25    32    14    7The smallest element (5) is selected and swapped with 25
25    18    25    32    14    7Proceeding to the next iteration, where the smallest unsorted element (7) is swapped with 18
5    7    25    32    14    18This leads to partial sorting within the array
35    7    25    32    14    18Moving forward, the algorithm focuses on the smallest unsorted element (14), which is swapped with 25
5    7    14    32    25    18This results in further progress towards a sorted array
45    7    14    18    25    32In the next phase, the smallest unsorted element (18) is swapped with itself
5    7    14    18    25    32Ultimately, 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(N2)

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

Space Complexity:

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.

1 thought on “Selection Sort – Data Structure and Algorithm”

Leave a Comment