In the previous article, we explored the algorithm of Bubble, Insertion, and Quick Sort and how they can improve your efficiency in sorting.

In the second part of this sorting article, we will delve deeper into the selection algorithm and discuss its specific implementation, strengths, and weaknesses.

Similar to the types of sorting algorithms we previously discussed, the selection sorting algorithm is not exceptional in terms of trade-offs when compared to other types of sorting algorithms. We will explore its underlying logic and sorting capabilities. Would it be safe to delve right into this sorting algorithm?

---

Introduction:

The Selection Sort algorithm is a simple and efficient approach to sorting data items from a practical perspective. The algorithm works by repeatedly finding the smallest or largest element in the unsorted portion of the data set, and placing it in its correct position. This process is repeated until all items in the data set are sorted. Selection Sort has a time complexity of O(n²), making it suitable for small to medium-sized data sets.

Do not be confused! It is as simple as it sounds…

Implementation Algorithm:

Due to the simplicity of the selection sorting algorithm, it is arguably the most commonly used sorting algorithm that I have seen. However, its time complexity does not make it the best choice for sorting large data sets, assuming we have an array with members [5, 6, 2, 1, 3], we would pick the item index in the array with the smallest value for every pass to swap with the kth position of the pass, and this is repeatedly done until all the elements are completely sorted.

It’s important to know that the selection sorting algorithm’s time and space complexity is similar to that of the bubble and insertion sorting algorithm

So from the above explanation, the first pass result would be swapping items in index 0 (item = 5) and 3 (item = 1) and this is because item 1 is our smallest item in the entire data set for the first pass, the next pass will start from index 1 and up until we get to index 4, which result to [1, 6, 2, 5, 3]. Let’s look at the visual representation of the first pass:

The second pass of the algorithm will start from index 1 since index 0 is correctly sorted, and we would continue to increment the index until we reach the index of the last item in the array. Below is the sample code for the selected sorting algorithm:

//Java
public int[] selectionSort(int[] array) {
  for(int i = 0; i < array.length; i++) {
      int j = i + 1;
      int smallestIndex = i;
      while(j < array.length) {
        if(array[smallestIndex] > array[j]) {
            smallestIndex = j;
        }
        j++;
      }
      int temp = array[smallestIndex];
      array[smallestIndex] = array[i];
      array[i] = temp;
   }
   return array;
}


//Swift
func selectionSort(_ array: inout [Int]) -> [Int] {
    for i in 0 ..< array.count {
        var j = i + 1
        var smallestIndex = i
        while(j < array.count) {
            if(array[smallestIndex] > array[j]) { 
                smallestIndex = j 
            }
            j += 1  
        }
        array.swapAt(i, smallestIndex)
    }
    return array
}


//Javascript
function selectionSort(array) {
    let i = 0;
    const length = array.length;
    while(i < length) {
      let smallestIndex = i;
      let j = i + 1;
      while(j < length){
        if(array[smallestIndex] > array[j]) { 
              smallestIndex = j; 
        }
        j++;
      }
      [array[smallestIndex], array[i]] = [array[i], array[smallestIndex]];
      i++;
    }
    return array;
}


// C#
public static int[] SelectionSort(int[] array) {
   for(int i = 0; i < array.Length; i++) {
       int smallestIndex = i;
       int j = i + 1;
       while(j < array.Length){
          if(array[smallestIndex] > array[j]) { smallestIndex = j; }
          j++;
       }
       int temp = array[smallestIndex];
       array[smallestIndex] = array[i];
       array[i] = temp;
   }
   return array;
}

At the end of the algorithm, our output should now be [1, 2, 3, 5, 6].

---

Strengths of the Selection Algorithm:

1. Efficiency: Selection algorithms provide efficient solutions for finding the kth smallest or largest element in an unsorted list or array. They offer improved time complexity compared to sorting the entire list, especially when only a few elements are required.

2. Flexibility: Selection algorithms are adaptable and can be used in a variety of scenarios, such as finding medians, order statistics, or identifying elements based on their rank. They provide a versatile toolset for solving different problems related to element selection.

3. Deterministic: Some selection algorithms, like the Median of Medians algorithm, provide a deterministic approach with guaranteed worst-case time complexity. This ensures consistent and predictable performance across various inputs.

---

Weaknesses of the Selection Algorithm:

1. Complexity: While selection algorithms offer improved time complexity compared to sorting the entire list, their implementations can be more complex. Algorithms like QuickSelect require careful consideration of partitioning and recursion, making them slightly more challenging to implement correctly.

2. Data Distribution Sensitivity: Some selection algorithms, like QuickSelect, can be sensitive to the initial distribution of data. In certain cases, an unlucky choice of pivot can lead to degraded performance, resulting in worst-case time complexity scenarios.

3. In-Place Modifications: Many selection algorithms operate by modifying the input list or array in place during the selection process. This can be a drawback if the original order of elements needs to be preserved or if the input data is read-only.

4. Limited to Single Dimension: Selection algorithms are primarily designed for finding order statistics in a single dimension. They might not be directly applicable to more complex data structures or higher-dimensional problems.

In case you’re wondering what QuickSelect is, first and foremost, QuickSelect isn’t the same as QuickSort, but they share and use the same partitioning approach to sorting. QuickSelect is a type of selection sorting algorithm that uses a partitioning approach to find the smallest or largest item in a list, while QuickSort uses a partitioning approach to sort items in a list based on the chosen pivot element.

---

Let’s wrap this up!

It provides a practical solution for selecting elements in linear time, making it a go-to algorithm in various scenarios. Selection algorithms find applications in diverse areas, including statistics, data analysis, order statistics, and algorithms for large-scale datasets (if you do not mind the ugly time complexity it brings to the table). They are widely utilized in fields like finance, healthcare, data mining, and machine learning, where identifying specific elements based on rank or finding the kth-order statistic is essential.

In the next article, we would be discussing the Merge Sorting algorithm, stay tuned!