Thursday, September 1, 2011

PowerShell: Bubble Sort Optimization 2

There is a final optimization that can be done to bubble sort. If we think about it, all numbers after the last swap, will be sorted. Taking that into account, the PowerShell code is:
Function BubbleSort($arrArray) {
  $n = $arrArray.length
  Do {
    $intNotSorted = 0
    for ($i = 0 ; $i -lt ($n-1); $i++) {
      if ($arrArray[$i] -gt $arrArray[$i+1]) {
        $arrArray[$i], $arrArray[$i+1] =`
        $arrArray[$i+1], $arrArray[$i]
        $intNotSorted = $i+1
      }
    }
    $n = $intNotSorted
  }
  Until ($n -eq 0)
  $arrArray
}

No comments: