Wednesday, August 31, 2011

PowerShell: Bubble Sort Optimization

It's quite easy to optimize bubble sort when you realize that every pass is placing the corresponding highest number in it's right place. For example 5,4,3,2,1 becomes 4,3,2,1,5 after one pass. Then 3,2,1,4,5 and so on. So there really isn't much point in looking at the two last numbers in pass three, since they have already been sorted. That is, after one pass, the last number is already in it's correct place, after two passes the last two numbers are already in their correct places and so on. Taking that into account, the code for a slightly optimized Bubble Sort looks like this in PowerShell:
Function BubbleSort($arrArray) {
  $n = $arrArray.length
  Do {
    $boolChanged = $false
    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]
	$boolChanged = $true
      }
    }
    $n -= 1
  }
  Until (-not $boolChanged)
  $arrArray
}

No comments: