Selection Search Algorithm
The Selection Search Algorithm is an important concept in computer science that helps to sort and retrieve elements from a list or an array in a specific order. This algorithm works by repeatedly selecting a minimum or maximum element from the unsorted part of the list and then placing it at the beginning or end of the sorted part. The Selection Search Algorithm can be applied in various applications, such as finding the k-th smallest or largest element in a list, sorting elements in ascending or descending order, and searching for an element with a specific rank or percentile.
The Selection Search Algorithm operates by iterating through the list and identifying the minimum or maximum element during each pass. In the first pass, it selects the minimum or maximum element and swaps it with the first element of the list. In the second pass, it selects the minimum or maximum element from the remaining unsorted portion and swaps it with the second element, and so on until the entire list is sorted. The time complexity of the Selection Search Algorithm is O(n^2), where n is the number of elements in the list, making it inefficient for larger datasets. However, it performs well for smaller datasets and is easy to implement, making it a popular choice for sorting and searching operations in computer science.
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Selection http://en.wikipedia.org/wiki/Selection_algorithm
*
* Worst - O(n^2)
* Best - O(1)
* Average - O(n)
*/
def selectionsearch[A <% Ordered[A]](list: List[A], n: Int): Option[A] = { // quickselect
def search(t: (List[A], A, List[A]), m: Int): Option[A] = t match {
case (Nil, p, Nil) if m == 0 => Some(p)
case (Nil, _, Nil) => None
case (l, p, g) => select(l, p, g, l.length, m)
}
def select(l: List[A], p: A, g: List[A], q: Int, m: Int): Option[A] =
if (m < q) partitionAndSearch(l, m)
else if (m > q) partitionAndSearch(g, m - q - 1)
else Some(p)
/**
* The same as in quicksort.
*/
def partition(as: List[A]): (List[A], A, List[A]) = {
def loop(p: A, as: List[A], l: List[A], g: List[A]): (List[A], A, List[A]) =
as match {
case h :: t => if (h < p) loop(p, t, h :: l, g) else loop(p, t, l, h :: g)
case Nil => (l, p, g)
}
loop(as.head, as.tail, Nil, Nil)
}
def partitionAndSearch(as: List[A], m: Int): Option[A] =
if (as.isEmpty) None
else search(partition(as), m)
partitionAndSearch(list, n)
}
