Pro: Windows Server 2008, Server Administrator

I managed the Microsoft Exam 70-646 today, so I'm finally a Microsoft Certified IT Professional (MCITP).

PowerShell: Merge Sort

Merge Sort is an sorting algorithm in 1945 by John von Neumann. It's complexity is O(n log n), also called linearithmic (it's a product of the linear term n, and the logarithmic log n).

PowerShell: Insertion Sort

Insertion Sort is in practice slightly more efficient then Selection Sort (And by extension of course Bubble Sort), even though they share the same O(n^2) time complexity.

Insertion Sort have a number of benefits. It'd Adaptive, meaning that it takes less time to run the more sorted the input already is. Stable, meaning that it doesn't change the order of same valued numbers. If we for example sort 1,3,2,2 with Insertion Sort, the 2's won't change place in relation to each other. That can be relevant if we are sorting value-key pairs. In-place meaning that the extra memory needed (in addition to the storage of the array) is constant. Online, meaning that you can start sorting a list even if you haven't received all the values yet.

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.

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
}

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
}

PowerShell: Bubble Sort

As Donald Knuth stated, "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems".
That said, here it is implemented in PowerShell.

Function BubbleSort($arrArray) {
  Do {
    $boolChanged = $false
    for ($i = 0 ; $i -lt $arrArray.length - 1; $i++) {
      if ($arrArray[$i] -gt $arrArray[$i+1]) {
        $arrArray[$i], $arrArray[$i+1] =`
	$arrArray[$i+1], $arrArray[$i]
	$boolChanged = $true
      }
    }
  }
  Until (-not $boolChanged)
  $arrArray
}