Friday, September 2, 2011

PowerShell: Selection Sort

The idea behind Selection Sort is really simple. First find the lowest value in the array to sort. Then swap the lowest value with the value in the first position (Postition [0] in PowerShell) in the array. Then find the lowest value in the among the unsorted values in the array, and swap that with the second position (Position [1] in PowerShell) in the array, and so on until the entire array is sorted.

Selection Sort have the same O(n^2) time complexity as Bubble Sort, but it almost always outperform it. Note: Bubble Sorts best case performance is O(n), while Selection Sorts best case performance is O(n^2. Though this can be seen as an advantage for Selection Sort since the time to sort an array will always be the same. As far as advantages go, it's not a great one, but it's worth noting that sometimes being quicker isn't always a good thing. Selection Sort performs rather few swaps compared to say Insertion Sort (Θ(n) vs. Ο(n^2)), which can be a huge benefit where writing is a more costly then reading. For arrays consisting of 10 or more elements, Selection Sort is outperformed by algorithms like Merge Sort, but if the array contains less then 10 elements, Selection Sort will usually be faster.

Selection Sort in PowerShell:
Function SelectionSort($arrArray) {
  $n = $arrArray.length
  for ($intPosition = 0;$intPosition -lt ($n - 1);$intPosition++) {
    $intMinimum = $intPosition
    for ($i = $intPosition + 1;$i -lt $n;$i++) {
      if ($arrArray[$i] -lt $arrArray[$intMinimum]) {
        $intMinimum = $i
      }
    }
    if ($intMinimum -ne $intPosition) {
      $arrArray[$intPosition], $arrArray[$intMinimum] =`
      $arrArray[$intMinimum], $arrArray[$intPosition]
    }
  }
  $arrArray
}

No comments: